クイックソートは、同じO(N*logN)のソート方法の中でも効率が高いため、よく採用されます。さらに、クイックソートの考え方である分割統治法は実際に実用的です。そのため、多くのソフトウェア企業の筆記試験や面接（テンセントやマイクロソフトなどの有名IT企業を含む）で好んで出題され、また大小様々なプログラミング関連の試験（軟考や大学院入試など）でもクイックソートがよく登場します。

=a

クイックソートは、C.R.A.Hoareが1962年に提案した分割交換ソートです。分割統治戦略を採用しており、一般に分割統治法（Divide-and-ConquerMethod）と呼ばれます。

この方法の基本的な考え方は次のとおりです。

• 1. まず数列から1つの数を取り出し、基準数とします。
• 2. 分割処理では、この数より大きい数をすべて右側に置き、この数以下の数をすべて左側に置きます。
• 3. 左右の区間に対して2番目のステップを、各区間が1つの数だけになるまで繰り返します。

クイックソートは分割統治法と呼ばれますが、「分割統治法」の3文字だけではクイックソートの全手順をうまく説明できません。そこで、クイックソートについてさらに詳しく説明します。穴掘り・数埋め法＋分割統治法です。

まず実例を見てみましょう。定義は後で示します（定義を自分の言葉でまとめると、コードの実装に役立ちます）。

 

配列を例として、区間の最初の数を基準数とします。

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初期状態では、i = 0; j = 9; X = a[i] = 72

すでにa

jから前へ、X以下またはXと等しい数を探します。j=8のとき条件を満たすので、a

 

配列は次のようになります：

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 

i = 3;   j = 7;   X=72

上記の手順を繰り返します。まず後ろから前へ探し、次に前から後ろへ探します。

jから前へ探し、j=5のとき条件を満たすので、a

iから後へ探し、i=5のとき、i==jとなるため終了します。

このとき、i = j = 5 であり、a

配列は次のようになります：

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

a

 

穴掘り・数埋め法をまとめると：

• 1. i = L; j = R; 基準数を掘り出して最初の穴a[i]を作ります。
• 2. j-- で後ろから前へそれより小さい数を探し、見つけたらその数を掘り出して前の穴a[i]に埋めます。
• 3. i++ で前から後ろへそれより大きい数を探し、見つけたらその数を掘り出して前の穴a[j]に埋めます。
• 4. i==jになるまで2と3の手順を繰り返し、基準数をa[i]に埋めます。

このまとめに従えば、穴掘り・数埋めのコードを簡単に実装できます：

int AdjustArray(int s[], int l, int r) //調整後の基準数の位置を返す { int i = l, j = r; int x = s[l]; //s[l]すなわちs[i]が最初の穴です while (i < j) { // 右から左へxより小さい数を探してs[i]を埋める while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //s[j]をs[i]に埋めると、s[j]が新しい穴になります i++; } // 左から右へx以上の数を探してs[j]を埋める while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //s[i]をs[j]に埋めると、s[i]が新しい穴になります j--; } } //終了時、iとjは等しい。xをこの穴に埋める。 s[i] = x; return i; }

次に分割統治法のコードを書きます：

void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);//まず穴掘り・数埋め法でs[]を調整する quick_sort1(s, l, i - 1); //再帰呼び出し quick_sort1(s, i + 1, r); } }

このコードは明らかに簡潔ではないので、整理してまとめます：

//クイックソート void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); //中央の数と最初の数を交換する 注1を参照 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) // 右から左へxより小さい最初の数を探す j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) // 左から右へx以上の最初の数を探す i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); //再帰呼び出し quick_sort(s, i + 1, r); } }

クイックソートには多くの改良版があります。例えば、基準数をランダムに選んだり、区間内のデータが少ない場合は別のソート方法を直接使って再帰の深さを減らしたりします。興味がある方はさらに深く研究してみてください。

注1：一部の書籍では中央の数を基準数にしています。これを実装するのはとても簡単で、中央の数と最初の数を交換するだけです。

著者：MoreWindows

原文：https://blog.csdn.net/morewindows/article/details/6684558