快排
快速排序
快速排序背后采用的也是分治的思想。
核心思想
- 选择基准元素
从数组中 随机选择 一个元素作为基准值（pivot）。 - 分区操作
将数组中所有小于基准的元素移动到基准的左侧，大于基准的元素移动到右侧。这样，基准就处于它排序后应在的位置上。整个序列就变成了[比基准小的值] 基准值 [比基准大的值] - 递归排序
对基准左右两边的子数组分别重复上述步骤，直到所有子数组都有序。
举个例子：
假设我们有 [3, 5, 8, 1, 2, 9, 4, 7] 这个序列，这里选择 4 来作为基准值
接下来从头到尾，把小于 4 的放到左边，大于 4 的放到右边，如下图所示：
接下来对基准值左边和右边进行相同的操作即可。
好了，这是关于快速排序的最基本的思想。下面是一个快速排序整体框架的示例代码：
// 分治函数
function partition(array, left, right){
// todo
}
// 这是入口函数
function quickSort(array){
function QuickSort(array, left, right){
if(left < right){
// 该方法内部，会选择一个元素作为基准值
// 然后将所有小于基准值的元素，放到基准值左边，所有大于基准值的元素，放到基准值右边
// 最后会返回基准值的索引
let index = partition(array, left, right);
// 拿到基准值之后，再对数组进行切割，对左右两边的子数组做相同的操作
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
QuickSort(array, 0, array.length - 1);
}
const arr = [3, 5, 8, 1, 2, 9, 4, 7];
quickSort(arr);
快速排序的 partition 方法的实现有多种方式，例如：
- 左右指针法
- 挖坑法
这里我们就介绍一个最常用的左右指针法。
左右指针法
使用左右指针法实现 partition 方法的步骤如下：
- 选取某个元素作为 pivot 基准值，一般取当前数组的第一个元素或者最后一个元素，这里我们采用 最后一个元素。
- 从 left 一直 向后寻找，直到找到一个大于 pivot 的值，然后 right 从后往前找，找到一个小于 pivot 的值，然后交换这两个元素的位置。
- 重复第 2 步，直到 left 和 right 相遇，这时将 pivot 放置在 left 的位置即可。
下面是一个具体的图解：
（1）原始数组，left 一开始指向第一个元素，right 一开始指向倒数第二个元素，最后一个元素是基准值
（2）left 从左往右走，走到 7 的位置就停下了，接下来 right 从右往左走，一开始在 3 的位置就停下了。然后两者进行交换
（3）left 继续往右走，走到 6 的位置停下，right 走到 0 的位置，然后停下，两者进行交换
（4）left 继续走，走到 9 停下来，right 继续走，走到 2 停下来，进行交换
（5）接下来 left 继续往右走，此时 left >= right 了，说明第一轮就走完了，将基准值和 array[left]进行交换
然后走完一轮之后，基准值左边的元素都是比基准值小的，基准值右边的元素都是比基准值大的。
代码实现
// 分治函数
function partition(array, left, right) {
// 首先是找一个基准值，我们取最后一个元素作为基准值
let pivot = array[right];
let pivotIndex = right; // 基准值对应的下标
while (left < right) {
// 左边的left一直往右走
while (left < right && array[left] < pivot) {
left++;
}
// 上面跳出 while 说明找到了一个比基准值大的
// 右边的right一直往左边走
while (left < right && array[right] >= pivot) {
right--;
}
// 上面跳出 while 说明找到了一个比基准值小的
[array[left], array[right]] = [array[right], array[left]];
}
// 当跳出上面的while 的时候，需要将基准值和left指向的值进行交换
[array[left], array[pivotIndex]] = [array[pivotIndex], array[left]];
return left;
}
// 这是入口函数
function quickSort(array) {
function QuickSort(array, left, right) {
// 注意下面的条件判断，是判断子数组是否还能够继续拆分
if (left < right) {
// 该方法内部，会选择一个元素作为基准值
// 然后将所有小于基准值的元素，放到基准值左边，所有大于基准值的元素，放到基准值右边
// 最后会返回基准值的索引
let index = partition(array, left, right);
// 拿到基准值之后，再对数组进行切割，对左右两边的子数组做相同的操作
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
QuickSort(array, 0, array.length - 1);
}
const arr = [3, 5, 8, 1, 2, 9, 4, 7];
quickSort(arr);
console.log(arr);
复杂度
- 时间复杂度：
O(nlogn) - 空间复杂度：
O(logn)
稳定性
快排是一种 不稳定 排序，因为在分区的过程中，元素的交换可能影响相等元素的原始顺序。
我的实现与问题纠正
function change(arr, left, right) {
let tar = arr[right]
let tarIndex = right
let start = left
let end = right - 1
while (start < end) {
while (arr[start] > tar && start < end) {
start ++
}
while (arr[end] <= tar && start < end) {
end --
}
[arr[start], arr[end]] = [arr[end], arr[start]]
}
[arr[start], arr[tarIndex]] = [arr[tarIndex], arr[start]]
return start
}
function sort(arr) {
function helper(arr, left, right) {
if (left < right) {
let index = change(arr, left, right)
helper(arr, left, index - 1)
helper(arr, index + 1, right)
}
}
helper(arr, 0, arr.length - 1)
return arr
}
let arr = [1,4,7,3,6,9,3,2,8]
console.log(sort(arr))
这样实现的结果是错误的，原因如下
你的代码实现的是快速排序的 分区（partition） 过程，问题出在 end = right - 1 这个初始值上。我们来逐步分析：
问题分析
-
你的逻辑：
- 分区时以
arr[right]为基准值（pivot）。 start从左向右找 大于 pivot 的值，end从右向左找 小于等于 pivot 的值。- 交换
start和end，最后将pivot放到正确的位置。
- 分区时以
-
关键问题：
- 当
end = right - 1时，end的初始位置是基准值的前一个元素，这会导致：- 如果
arr[end]本身 就是正确的（即arr[end] <= pivot），end--会跳过它，导致分区点计算错误。 - 最终
start和end的相遇点可能不满足arr[start] <= pivot，导致基准值被交换到错误的位置。
- 如果
- 当
-
为什么
end = right能修复问题？- 让
end从right开始（即包含基准值本身），可以保证：- 如果
arr[right]是最大值，end会一直减到start，此时start指向的位置就是基准值的正确位置。 - 分区逻辑更通用，不会漏掉边界情况。
- 如果
- 让
修正后的代码
function change(arr, left, right) {
let pivot = arr[right]; // 基准值
let pivotIndex = right; // 基准值原始索引
let start = left;
let end = right; // 关键修改：end 从 right 开始，而非 right - 1
while (start < end) {
while (arr[start] <= pivot && start < end) start++; // 注意条件改为 <=
while (arr[end] >= pivot && start < end) end--; // 注意条件改为 >=
[arr[start], arr[end]] = [arr[end], arr[start]];
}
// 将基准值放到正确位置
[arr[start], arr[pivotIndex]] = [arr[pivotIndex], arr[start]];
return start; // 返回分区点
}
function sort(arr) {
function helper(arr, left, right) {
if (left < right) {
let index = change(arr, left, right);
helper(arr, left, index - 1);
helper(arr, index + 1, right);
}
}
helper(arr, 0, arr.length - 1);
return arr;
}
let arr = [1, 4, 7, 3, 6, 9, 3, 2, 8];
console.log(sort(arr)); // 输出正确排序结果
关键修改点
end = right而非end = right - 1- 确保分区过程能正确处理基准值本身的位置。
- 调整比较条件
arr[start] <= pivot和arr[end] >= pivot：避免重复元素导致死循环。
- 分区逻辑的对称性
- 从两端向中间扫描时，
start和end的移动条件需要对称，否则可能导致分区点偏移。
- 从两端向中间扫描时，
快速排序的分区正确写法（经典Hoare分区）
更常见的分区实现如下（无需单独处理 right - 1）：
function partition(arr, left, right) {
let pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
总结
- 你的原始代码因
end初始值少了一位，导致分区点计算不准确。 - 快速排序的分区需要保证 基准值最终位置 的正确性，因此
end应从right开始扫描。 - 建议使用经典的分区写法（如上），更简洁且不易出错。
-EOF-