QuickSort(クイックソート)の原理とC++コードの実現

迅速なソートは最も重要なソートと言えるが、その中で伸びた思想とテクニックは私たちが学ぶ価値がある.
クイックソートも分治の考え方を用いており、原理は以下の通りである.
分解:配列A[p..r]は、A[p..q-1]とA[q+1..r]の2つの(空の可能性がある)サブ配列A[p..q-1]とに分割され、A[p..q-1]の各要素がA[q]以下であり、A[q]もA[q+1..r]の各要素以下である.ここで、下付きqの計算も分割プロセスの一部である.
解決:サブ配列A[p..q-1]とA[q+1..r]を再帰的に呼び出してソートします.
マージ:サブ配列はすべて元のアドレスでソートされているため、マージ操作は必要なく、配列A[p..r]は秩序化されています.
分割が極端でない限り,高速ソートの時間的複雑度はO(nlgn)であり,そうでない場合,時間的複雑度はO(nlgn)である.θ(n2).
ランダム化思想(ランダム選択メタ)を用いて,高速ソートの所望時間複雑度をO(nlgn)に達させることができる.
高速ソートは安定したソートではありません.
コードは次のとおりです(参考まで).

 1 int Partition(int * const begin, int * const end) { //lomuto  
 2     int i = -1;
 3     for (int j = 0; j < (end - begin); ++j) {
 4         if (*(begin + j) <= *(end - 1)) {       //            
 5             ++i;
 6             swap(*(begin + i), *(begin + j));
 7         }
 8     }
 9     return i;
10 }
11 
12 void QuickSort(int * const begin, int * const end) {
13     if (begin >= end - 1)
14         return ;
15     int mid = Partition(begin, end);
16     QuickSort(begin, begin + mid);    //    lomute  ，  lomuto      
17     QuickSort(begin + mid + 1, end);  //mid          
18 }

1 void QuickSort(int * begin, int * const end) {  //   
2     while (begin < end - 1) {
3         int mid = Partition(begin, end);
4         QuickSort(begin, begin + mid);    //    lomute  
5         begin = begin + mid + 1;
6     }
7 }

もう1つの区分方法:

 1 int Partition(int * const begin, int * const end) { //hoare  
 2     int key = *begin;         //           
 3     int i = -1, j = end - begin;  //i, j      
 4     while (1) {
 5         for (++i; *(begin + i) < key; ++i); //   do{}while；
 6         for (--j; *(begin + j) > key; --j);
 7         if (i < j)
 8             swap(*(begin + i), *(begin + j));
 9         else
10             return j;
11     }
12 }
13 
14 void QuickSort(int * const begin, int * const end) {
15     if (begin >= end - 1)
16         return ;
17     int mid = Partition(begin, end);
18 
19     QuickSort(begin, begin + mid + 1);   //  hoare  ，  hoare      
20     QuickSort(begin + mid + 1, end);     //mid(  mid）         mid     
21 }