今天写一下快排，最经典的排序算法：
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 阅读(248)
评论(0) 编辑 收藏 引用 所属分类:
杂