今天寫一下快排，最經典的排序算法：
1 int partition(int *a, int low, int high)
2 {
3 int pivot = a[low]; //設定a[low]為樞軸
4 int i = low, j = high + 1;
5
6 while (1)
7 {
8 do { //從右向左找到一個比pivot小的數
9 --j;
10 } while (i < j && a[j] >= pivot);
11
12 do { //從左向右找到一個比pivot大的數
13 ++i;
14 } while (i < j && a[i] <= pivot);
15
16 if (i < j)
17 { //把這兩個數交換
18 a[i] = a[i] ^ a[j];
19 a[j] = a[i] ^ a[j];
20 a[i] = a[i] ^ a[j];
21 }
22 else //說明a[i]左邊的數字全部比pivot小，而a[j]右邊的數字全部比pivot大，則說明找到了pivot應該在的位置，跳出循環
23 {
24 break;
25 }
26 }
27
28 if (i > j)
29 {
30 --i;
31 }
32
33 a[low] = a[low] ^ a[i];
34 a[i] = a[low] ^ a[i];
35 a[low] = a[low] ^ a[i];
36 return i; //返回pivot的位置
37 }
38
39 void Qsort(int *a, int low, int high)
40 {
41 if (low < high)
42 {
43 int mid = partition(a, low, high);
44 Qsort(a, low, mid - 1);
45 Qsort(a, mid + 1, high);
46 }
47 }
48
其中，還是要屬partition為核心，關鍵就看怎么分。一種典型的效果比較好的分法就是：
1、選定某個元素為pivot(假定選a[low])，則設i = low, j = high + 1；
2、對數組從j開始自右向左掃描，找到第一個比pivot小的數，假定為a[j]；然后從i開始自左向右掃描，找到第一個比pivot大的數，假定為a[i]；
3、若i < j，則將a[i]與a[j]交換位置，重復步驟2；否則執行步驟4；
4、仔細觀察執行步驟不難發現，極端情況下i會大于j，但是i最大也就只能是j + 1(可以參考下面的說明)，因此若i > j，則--i。然后交換pivot與a[i]的值，返回i值。極端情況下可能會有以下情況：
也就是i在j后面一個位置，因此應該判斷i是否大于j，如果大于則交換a[--i]與a[low](也就是pivot)的值，然后返回i。
posted on 2011-04-21 00:50
myjfm 閱讀(279)
評論(0) 編輯 收藏 引用 所屬分類:
雜