快速排序

听说有的公司面试会考？0.0

快速排序思想：分治法

　　基本思想：1、从数列中选出一个数

　　　　　　　2、分区（遍历），比它大的放他右边，比它小的或者等于的，放他左边

　　　　　　　3、对左右区间重复第2步，直到区间只有一个数（递归）

参考：快速排序 | 菜鸟教程 (runoob.com)

在该网站中将思想2的实现称为挖坑填数，我称之为找例外，那么怎么找？

 简单描述，结合上图：

一开始i和j分别站在0，与9的位置，我们根据思想1选出参考数72

然后j开始从右边往左边找，由于右边分区的数都应该比72大，j走到8的位置认为48很突兀，把48扔到左边参考数空出来的位置0，左边多了右边少了一个数字，j站定轮到i出手，

i从左边往右边找，左边应该都是比参考数72小于等于的数，i走到位置3看到突兀的88，把他扔到右边空出来的位置8，i在位置3站定，轮到j操作，

j从之前站定的位置8出发，走到位置5，把突兀的42扔到左边空位位置3，在位置5站定，轮到i操作，

i从位置3出发，走到位置5与j见面，两人协商后把参考数放在空位5，

代码实现：

正经人不手写代码，以下代码ai生成后人为检查：

 1 // 分区函数：挖坑填数法
 2 int partition(std::vector<int>& arr, int low, int high) {
 3     // 选取基准元素
 4     int pivot = arr[low];
 5     // 记录挖的坑的位置
 6     int left = low;
 7     int right = high;
 8 
 9     // 当左右指针未相遇时，继续循环
10     while (left < right) {
11         // 从右侧找到第一个小于基准元素的值
12         while (left < right && arr[right] >= pivot)
13             right--;
14         // 将右侧小于基准元素的值填入左侧坑位，left等right也没事，
15         arr[left] = arr[right];
16 
17         // 从左侧找到第一个大于基准元素的值
18         while (left < right && arr[left] <= pivot)
19             left++;
20         // 将左侧大于基准元素的值填入右侧坑位
21         arr[right] = arr[left];
22     }
23 
24     // 将基准元素放入最终的坑位
25     arr[left] = pivot;
26     // 返回基准元素的位置
27     return left;
28 }

// 快速排序函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot_index = partition(arr, low, high);
        quickSort(arr, low, pivot_index - 1);
        quickSort(arr, pivot_index + 1, high);
    }
}

代码注意的几个点：

arr数组传参用的引用，可以用指针吗？

快速排序入口检查low小于high，请注意，分区后再整理子区，左右两个分区都是不包含pivot_index 这个值的，当low比high小于1的时候，pivot_index 将是它们两者之一，临界检查通过。