切换主题
快速排序
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法过程描述：
- 创建首尾指针，左指针指向数组第一个值，右指针指向数组最后一个值；
- 从数组中随机取出基准数
pivot，并将基准数换到数组开头； - 当左指针小于右指针时：
1. 移动右指针，直到找到第一个比基准数小的值的下标；
2. 移动左指针，直到找到第一个比基准数大的值的下标；
3. 交换左右指针处的值。 - 遍历完成后，数组被分成了左右两个区域，此时基准数位于左（右）指针处；
- 将左右两个区域视为两个数组，重复
步骤1至步骤3，直到排序完成。
原地快排
JavaScript
const quickSort = (A, s = 0, e = A.length - 1) => {
let [l, r] = [s, e] // 定义首尾指针
const idx = ~~(s + Math.random() * (e - s + 1)); //随机选择基准数
[A[s], A[idx]] = [A[idx], A[s]] // 将基准数换到数组开头
while (l < r) {
// 移动右指针找到比基准数小的数
while (l < r && A[r] >= A[s]) r--
// 移动左指针找到比基准数大的数
while (l < r && A[l] <= A[s]) l++
[A[l], A[r]] = [A[r], A[l]]
}
// 由于此时的l/r就是基准值的下标，所以更新基准值
[A[s], A[l]] = [A[l], A[s]]
if (s < l - 1) {
// 左闭右闭区间
quickSort(A, s, l - 1)
}
if (e > l + 1) {
// 左闭右闭区间
quickSort(A, l + 1, e)
}
}