剑指Offer上的快速排序的Partition函数与我在数据结构书上学到的不一样，因此就想要探索下这两种不同的处理方式。

1.基本思想

快速排序的基本思想是基于分治法。在待排序表L[1...n]中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于pivot，L[k+1...n]中所有元素大于或等于pivot，则pivot放在了其最终位置L(k)上。而后递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

2.剑指Offer上的Partition实现

 1 // Partition为分割函数, length表示data数组的长度
 2 int Partition(int data[], int length, int low, int high) {
 3     if (data == nullptr || length <= 0 || low < 0 || high >= length) {
 4         return 1;
 5     }
 6     
 7     // 在[low, high]区间中随机取一个基准值，并将其换到区间最末尾
 8     int index = RandomInRange(low, high);
 9     Swap(&data[index], &data[high]);
10     
11     // small在low的前面一位
12     int small = low - 1;
13        
14     for (index = low; index < high; ++index) {
15         if (data[index] < data[high]) {
16             // ++small后表示大于基准值的第一个数的下标
17             // 如果不存在大于基准值的数，则表示当前比较的数字下标
18             ++small;
19 
20             // 交换后的small表示小于基准值的最后一个数字的下标
21             if (small != index) {
22                 Swap(&data[index], &data[small]);
23             }
24         }
25     }
26     
27     // ++small后表示大于基准值的第一个数的下标
28     ++small;
29     Swap(&data[small], &data[high]);
30     
31     return small;
32     
33 }

 

快速排序其它函数实现如下:

 1 // 生成一个随机数，范围在[low，high)，是一个前闭后开的区间
 2 int RandomInRange(int low, int high) {
 3     return rand() % (high - low) + low;
 4 }
 5 
 6 // 交换两个整数
 7 void Swap(int* left, int* right) {
 8     int temp  = *left;
 9     *left = *right;
10     *right = temp;
11 }
12 
13 // 快速排序函数
14 void QuickSort(int data[], int length, int low, int high) {
15     if (low == high) {
16         return;
17     }
18     
19     int index = Partition(data, length, low, high);
20     
21     if (index > low) {
22         QuickSort(data, length, low, index - 1);
23     }
24     
25     if (index < high) {
26         QuickSort(data, length, index + 1, high);
27     }
28 }
29 
30 // 数据打印
31 void PrintData(int data[], int length) {
32     for (int i = 0; i < length; ++i) {
33         std::cout << data[i] << " ";
34     }
35     
36     std::cout << std::highl;
37 }
38 
39 int main() {
40     // 以系统时间作为随机函数种子
41     srand((unsigned)time(nullptr));
42 
43     int const length = 10;
44     
45     int data[length];
46 
47     // 生成随机数
48     for (int i = 0; i < length; ++i) {
49         data[i] = RandomInRange(1, length*length);
50     }
51     
52     // 打印生成的随机数
53     PrintData(data, length);
54     
55     // 调用快排函数进行排序
56     QuickSort(data, length, 0, length - 1);
57   
58     // 打印快速排序后的数
59     PrintData(data, length);
60     
61     return 0;
62     
63 }

 

初始顺序为{49, 38, 65, 97, 76, 13, 27}，基准值为49的数据的第一趟快速排序的实现如下所示：

 

 

第一趟排序完之后基准值49之前的{27, 38, 13}都比49小，基准值49之后的{76, 65, 97}都比49大。

3.一般教材上的Partition实现

 1 // Partition为分割函数
 2 int Partition(int data[], int low, int high) {
 3 
 4     // 将当前表中第一个元素设为基准值，对表进行划分
 5     int pivot = data[low]; 
 6 
 7     // 循环跳出条件
 8     while (low < high) {
 9         while (low < high && data[high] >= pivot) {
10             --high;
11         }
12 
13         // 将比基准值小的元素移动到左端
14         data[low] = data[high];
15 
16         while (low < high && data[low] <= pivot) {
17             ++low;
18         }
19 
20         // 将比基准值大的元素移动到右端
21         data[high] = data[low];
22     }
23 
24     // 基准元素存放到最终位置
25     data[low] = pivot;
26 
27     // 返回存放基准值的最终位置
28     return low;
29 }

 

快速排序其它函数实现如下:

 

 1 void QuickSort(int data[], int low, int high) {
 2     // 递归跳出条件
 3     if (low < high) {
 4         // 将data[low...high]一分为二，pivotpos是基准值
 5         int pivotpos = Partition(data, low, high);
 6 
 7         // 对左子表进行递归排序
 8         QuickSort(data, low, pivotpos - 1);
 9 
10         // 对右子表进行递归排序
11         QuickSort(data, pivotpos + 1, high);
12     }
13 }

 

初始顺序为{49, 38, 65, 97, 76, 13, 27}，基准值为49的数据的第一趟快速排序的实现如下所示：

 

 

第一趟排序完之后基准值49之前的{27, 38, 13}都比49小，基准值49之后的{76, 97, 65}都比49大。

4.总结

可以看出，上述这两种思想导致的运行过程是不同的，前者是用small指代小于标准元素的最右位置，在遍历过程中进行交换操作来保证small左边都是小于标准元素的元素，而后者是用low，high分别表示小于和大于基准值的集合边界位置，所以后者更浅显易懂。