quickSort

今天闲来无事，复习了一下快排

首先写了一个partition

 1 int partition(int __toSort[], int __low, int __high) {
 2     int pivokey__ = __toSort[__low];
 3     while(__low < __high) {
 4         
 5         while(__low < __high && __toSort[__high] >= pivokey__) {
 6             __high--;
 7         }
 8         swap(__toSort, __low, __high);
 9         
10         
11         while(__low < __high && __toSort[__low] <= pivokey__) {
12             __low++;
13         }
14         swap(__toSort, __low, __high);
15         
16     }
17 
18     return __low;
19 }

再写quickSort()

1 void quickSort(int __toSort[], int __low, int __high) {
2     
3     int midium__ = partition2(__toSort, __low, __high);
4     quickSort(__toSort, __low, midium__ -1);
5     quickSort(__toSort, midium__ +1, __high);
6         
7 }

运行，怎么运行错误？

开始怀疑是Partition()写错了，后来发现忘记写递归退出条件了，悲哀！

改过来

1 void quickSort(int __toSort[], int __low, int __high) {
2     if(__low < __high) {
3         int midium__ = partition2(__toSort, __low, __high);
4     quickSort(__toSort, __low, midium__ -1);
5     quickSort(__toSort, midium__ +1, __high);
6     }
7     
8 }

运行成功。

之后将partition升级

 1 int partition2(int __toSort[], int __low, int __high) {
 2     int pivokey__ = __toSort[__low];
 3     while(__low < __high) {
 4         
 5         while(__low < __high && __toSort[__high] >= pivokey__) {
 6             __high--;
 7         }
 8         __toSort[__low] = __toSort[__high];
 9         
10         
11         while(__low < __high && __toSort[__low] <= pivokey__) {
12             __low++;
13         }
14         __toSort[__high] = __toSort[__low];
15         
16     }
17     __toSort[__low] = pivokey__;
18 
19     return __low;
20 }

运行成功