基本思想
- 先选取一个元素作为基准元素 partition（这个基准元素通常是随机选择的），交换到待排序部分的开头；
- 通过与 partition 比较将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数；
- 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；
复杂度
-
时间复杂度：
O(NlogN)，时间复杂度与 归并排序 一样； -
空间复杂度：
O(logN)，由于快速排序使用了递归函数，递归调用栈的深度接近 logN；
随机切分快排
选取基准元素
-
具体的例子分析
![]( "选取基准元素")
- 左边有序数组，每一轮循环要把剩下的元素都看一遍才能确定一个元素，算法在这个数组上的执行效率等同于使用 选择排序；
- 而右边，一开始 4 这个元素被交换到了数组的中间，好处是：递归执行下去的时候，每一次 partition 看的元素更少了，递归树更低，因此可以较快地完成排序任务；
- 事实上，以后对于树的优化，总是想方设法让树的高度更低，让树更「平衡」，这样执行效率更高；
- 一个比较容易想到的方案就是在一开始的时候，
随机选择一个元素交换到待排序部分的开头；
-
如果基准元素被交换到的位置越中间，递归执行的深度就越浅，快速排序的执行效率就越高；
图解
代码实现
function quickSort(nums, left, right) {
// 如果选取基准元素正好选择到了最小的那个值，则 pivotInx 索引为 0，会被分成 [0, -1]、[1, nums.length-1] 两个区间
// [0, -1] 是有问题的，所以要写成 left >= right
if (left >= right) {
return;
}
let pivotInx = partition(nums, left, right);
quickSort(nums, left, pivotInx - 1);
quickSort(nums, pivotInx + 1, right);
}
function partition(nums, left, right) {
// 1. 随机选择一个元素作为切分元素
let randomIndex = left + (Math.random() * (right - left) + 1) >> 0;
// 2. 将随机数放到数组的第一个位置
[nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];
// 3. 用 lt 来记录小于 pivot 元素的子序列右边界，即 [left + 1, lt] < pivot，[lt + 1, i) >= pivot
let pivot = nums[left];
let lt = left;
for (let i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
// 交换当前元素与 lt 的位置
lt++;
[nums[i], nums[lt]] = [nums[lt], nums[i]];
}
}
// 4. 将 pivot 放到中间，即 pivot 左侧都是小于 pivot 的元素序列，右侧都是大于 pivot 的元素序列
[nums[left], nums[lt]] = [nums[lt], nums[left]];
// 返回 pivot 的索引，用于分治（分别对 pivot 两侧的序列进行快排）
return lt;
}
双边快排-对撞指针
对随机切分快排的优化
-
随机选择切分元素有一种情况是无效的，那就是输入数组中有大量重复元素的数据：
![]( "无效的随机选择切分快速排序")
- 交换过来的元素还是和 pivot 相等的元素；
- 和切分元素相等的元素都全部被划分到了一侧，都会使得递归树失衡，即递归树的深度增加，从而时间复杂度退化为
O(N^2)；
-
这个时候的策略是：
把和 pivot 相等的元素平均分到数组的两边，使得递归树平衡；
![]( "把和pivot相等的元素平均分到数组的两边")
图解
代码实现
function quickSort(nums, left, right) {
// 如果选取基准元素正好选择到了最小的那个值，则 pivotInx 索引为 0，会被分成 [0, -1]、[1, nums.length-1] 两个区间
// [0, -1] 是有问题的，所以要写成 left >= right
if (left >= right) {
return;
}
let pivotInx = partition(nums, left, right);
quickSort(nums, left, pivotInx - 1);
quickSort(nums, pivotInx + 1, right);
}
function partition(nums, left, right) {
// 1. 随机选择一个元素作为切分元素
let randomIndex = left + (Math.random() * (right - left) + 1) >> 0;
// 2. 将随机数放到数组的第一个位置
[nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];
// 3. 用 lt 来记录小于 pivot 元素的子序列右边界，即 [left + 1, lt) <= pivot，(ge, right] >= pivot，le > ge 的时候终止
let pivot = nums[left];
let le = left + 1;
let ge = right;
while (true) {
// ge >= pivot，跳出循环，找到了第一个左侧大于等于 pivot 的元素
while (le <= ge && nums[le] < pivot) {
le++;
}
// ge <= pivot，跳出循环，找到了第一个右侧小于 pivot 的元素
while (le <= ge && nums[ge] > pivot) {
ge--;
}
// 此时 ge 来到第 1 个小于等于 pivot 的位置
if (le > ge) {
break;
}
// le 处是大于等于 pivot 的，ge 处是小于等于 pivot 的，则交换位置（左侧都是小于 pivot 的序列，右侧都是大于 pivot 的序列）
[nums[le], nums[ge]] = [nums[ge], nums[le]];
le++;
ge--;
}
// 4. 将 pivot 放到中间，即 pivot 左侧都是小于 pivot 的元素序列，右侧都是大于 pivot 的元素序列
[nums[left], nums[ge]] = [nums[ge], nums[left]];
// 返回 ge 的索引，用于分治（分别对 ge 两侧的序列进行快排）
return ge;
}
双边快排-三向切分
对随机切分快排的优化
-
随机选择切分元素有一种情况是无效的，那就是输入数组中有大量重复元素的数据：
![]( "无效的随机选择切分快速排序")
- 交换过来的元素还是和 pivot 相等的元素；
- 和切分元素相等的元素都全部被划分到了一侧，都会使得递归树失衡，即递归树的深度增加，从而时间复杂度退化为
O(N^2)；
-
这个时候的策略是：
把和 pivot 相等的元素放到数组中间，使得递归树平衡；
![]( "三向切分的快速排序")
图解
[left, lt - 1 ] < pivot
[lt + 1, i) === pivot
[gt, right] > pivot
代码实现
function quickSort(nums, left, right) {
// 如果选取基准元素正好选择到了最小的那个值，则 pivotInx 索引为 0，会被分成 [0, -1]、[1, nums.length-1] 两个区间
// [0, -1] 是有问题的，所以要写成 left >= right
if (left >= right) {
return;
}
// 1. 随机选择一个元素作为切分元素
let randomIndex = left + (Math.random() * (right - left) + 1) >> 0;
// 2. 将随机数放到数组的第一个位置
[nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];
let pivot = nums[left];
let lt = left; // 小于 pivot 序列右边界索引
let gt = right + 1; // 大于 pivot 序列左边界索引
let i = left + 1; // 遍历数组变量
while (i < gt) {
if (nums[i] < pivot) {
lt++;
[nums[i], nums[lt]] = [nums[lt], nums[i]];
i++;
} else if (nums[i] == pivot) {
i++;
} else {
gt--;
[nums[i], nums[gt]] = [nums[gt], nums[i]];
}
}
// 将 pivot 放到中间，即 pivot 序列的左侧都是小于 pivot 的元素序列，pivot 序列的右侧都是大于 pivot 的元素序列
[nums[left], nums[lt]] = [nums[lt], nums[left]];
// 区间 [lt, gt - 1] 不必递归求解，大大减少了分治的区间
quickSort(nums, left, lt - 1);
quickSort(nums, gt, right);
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 归并排序
上一篇
评论
