個性を分かち合うのはSTLのsortよりもっと良い速い列です

前言
落谷で問題を書くときは自分で速く書く必要があり、時間と空間の制限に一定の要求があります.私が問題解をもう一度調べたとき、大物が書いたコードを見つけました.分かりやすくて、性能がいいので、共有したいと思います(コードは私の習慣によって少し変更されました).
タイトルリンク
このコードは二分と速排の思想を結合している.

は、左の中間数より大きい要素を右の中間数より小さい要素と交換するたびに、左の領域の数が中間数より小さくなり、右の領域の数が中間数より大きくなるまで交換する.

は、左、右の各領域について、それぞれ第1のステップを実行する.

すべての数が

に並ぶまで
具体的なコードは以下の通りです.

#include

using namespace std;

int a[100001], n;

void QuickSort(int l, int r){
	if (l >= r) return;
	int i = l, j = r;
	//        0   
	a[0] = a[(i + j) / 2];
	//               
	while (i <= j){
		while (a[i] < a[0]) i++;  //                  
		while (a[j] > a[0]) j--;  //                  
		//       ,                
		if (i <= j) swap(a[i++], a[j--]);
	}
	// 【  】       j          ，i      
	if (l < j) QuickSort(l, j);  //        
	if (r > i) QuickSort(i, r);  //        
}

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}

	QuickSort(1, n);

	for (int i = 1; i <= n; i++){
		cout << a[i];
		if (i == n) cout << endl;
		else cout << " ";
	}
	return 0;
}