クイックソートの詳細
1001 ワード
高速ソートは非常に重要なアルゴリズムであり,ビッグデータのソートではバブルソートや挿入ソートなどのアルゴリズムよりも効率的に高いため,プログラマーが把握しなければならないアルゴリズムである.アルゴリズムの構想高速ソートアルゴリズムは実は簡単で、分治戦略を採用している.手順は次のとおりです. 基準要素(pivot) を選択 pivotより小さいものはpivotの左側に、pivotより大きいものはpivotの右側 に置く. pivotの左のシーケンスと右のシーケンスをそれぞれ再帰的に実行するステップ1とステップ2 .
具体的なコードは以下の である.
/*
* l：
* r：
* a：
*/
void quickSort(int *a, int l, int r) {
if (l < r) {
int i,j,x;
i = l;
j = r;
x = a[i];
while (i < j) {
while(i < j && a[j] > x) {
j--; // x
}
if(i < j)
a[i++] = a[j]; // i++
while(i < j && a[i] < x) {
i++; // x
}
if(i < j)
a[j--] = a[i];
}
a[i] = x;
quickSort(a, l, i-1); /* */
quickSort(a, i+1, r); /* */
}
}