快速排序算法的基本思想是
1.从数组中取出一个数，称之为基数（pivot）
2.遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
3.将左右两个区域视为两个数组，重复前两个步骤，直到排序完成
最简单的分区算法
分区的方式也有很多种，最简单的思路是：从 left 开始，遇到比基数大的数，就交换到数组最后，并将 right 减一，直到 left 和 right 相遇，此时数组就被分成了左右两个区域。再将基数和中间的数交换，返回中间值的下标即可。
void exchange(vector<int> arr, int i, int j)
{int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}void quickSort(vector<int> arr, int start, int end)
{// 如果区域内的数字少于 2 个，退出递归if (start >= end) return;// 将数组分区，并获得中间值的下标int middle = partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle + 1, end);
}void quickSort(vector<int> arr) {quickSort(arr, 0, arr.size() - 1);
}// 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
int partition(vector<int> arr, int start, int end) {// 取第一个数为基数int pivot = arr[start];// 从第二个数开始分区int left = start + 1;// 右边界int right = end;// left、right 相遇时退出循环while (left < right) {// 找到第一个大于基数的位置while (left < right && arr[left] <= pivot) left++;// 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数if (left != right) {exchange(arr, left, right);right--;}}// 如果 left 和 right 相等，单独比较 arr[right] 和 pivotif (left == right && arr[right] > pivot) right--;// 将基数和中间数交换if (right != start) exchange(arr, start, right);// 返回中间值的下标return right;
}
双指针分区算法
除了上述的分区算法外，还有一种双指针的分区算法更为常用：从 left 开始，遇到比基数大的数，记录其下标；再从 right 往前遍历，找到第一个比基数小的数，记录其下标；然后交换这两个数。继续遍历，直到 left 和 right 相遇。然后就和刚才的算法一样了，交换基数和中间值，并返回中间值的下标。
void exchange(vector<int> arr, int i, int j)
{int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}// 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
int partition(vector<int> arr, int start, int end)
{// 取第一个数为基数int pivot = arr[start];// 从第二个数开始分区int left = start + 1;// 右边界int right = end;while (left < right) {// 找到第一个大于基数的位置while (left < right && arr[left] <= pivot) left++;// 找到第一个小于基数的位置while (left < right && arr[right] >= pivot) right--;// 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数if (left < right) {exchange(arr, left, right);left++;right--;}}// 如果 left 和 right 相等，单独比较 arr[right] 和 pivotif (left == right && arr[right] > pivot) right--;// 将基数和轴交换exchange(arr, start, right);return right;
}void quickSort(vector<int> arr, int start, int end)
{// 如果区域内的数字少于 2 个，退出递归if (start >= end) return;// 将数组分区，并获得中间值的下标int middle = partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle + 1, end);
}void quickSort(vector<int> arr)
{quickSort(arr, 0, arr.size() - 1);
}
