【算法】快速排序
算法 系列博客
【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )
文章目录
一、快速排序思想
快速排序的思想 : 先 整体有序 , 后 局部有序 , 分治算法 ;
先从数组中 挑选出一个数 a , 然后 进行分割 , 将数组分割成两部分 , 左半部分 小于等于 a , 右半部分 大于等于 a ;
此时数组左半部分肯定小于右半部分 ;
然后分别对 左半部分 和 右半部分 再次挑选一个数 , 进行分割 ;
递归进行分割操作 , 直到数组中所有元素排序完成 ;
分割数组时 , 分割条件是小于等于 / 大于等于的原因 :
分割时 , 挑选的数 a , 如果数组元素为 a , 则该元素即可以在左边 , 又可以在右边 ;
如果数组中除几个数之外 , 其它全都是一样的数 , 如 1,1,1,1,1,1,1,2 , 挑选数字时 , 大概率选中 1 , 此时如果要求左半部分严格小于 1 , 此时 左半部分没有任何数值 , 很容易出现不均匀的划分 ;
快速排序的 理想划分 是每次划分 , 划分的左边和右边的元素个数基本差不多 , 递归时不会出现极端情况 ,
二、快速排序代码
整数排序 : https://www.lintcode.com/problem/463/
下面代码中有三个要点
- 分割中心点选取 ;
- 指针限制条件 ;
- 分割时判定要左右交换元素的条件 ;
取中心点, 一般取 start 与 end 索引的 中心索引对应的数组元素值 ;
如下取中间值是强行指定的, 也可以随机指定 , 指定 start 与 end 之间的一个随机值 ;
尽量不选取 start 和 end 索引的值 , 如果选取开始/结束值 , 作为分割点 , 假如该数组是按照升序或降序排列 , 可能出现极端情况 ;
指针限制条件 , 分割遍历时的两个指针的条件是 left <= right , 这里不能是 left < right ;
如果使用 left < right 会造成死循环递归 , 导致栈溢出 ;
使用 [3,2,1,4,5] 进行推导 , 即可出现死循环 ;
判定左右元素交换时 , 必须用 array[left] < pivot 和 array[right] > pivot , 不能使用 array[left] <= pivot 和 array[right] >= pivot , 否则会造成死循环递归 , 导致栈溢出 ;
使用 [3,2,1,4,5] 进行推导 , 即可出现死循环 ;
快速排序的时间复杂度是
;
代码示例 :
class Solution {
/**
* 快速排序
* @param A
*/
public void sortIntegers(int[] A) {
if (A == null || A.length == 0) {
return;
}
quickSort(A, 0, A.length - 1);
}
// 将 array 数组中 start 到 end 之间的元素进行排序
private void quickSort(int[] array, int start, int end) {
if (start >= end) {
// start 如果等于 end, 说明就一个元素, 不用排序
// start 正常情况下不会大于 end
return;
}
// 设置两个指针, 分别指向头尾
int left = start, right = end;
// 1. 分割操作第一步 : 取中心点
// 取中心点, 一般取 start 与 end 索引的中心索引对应的数组元素值
// 如下取中间值是强行指定的, 也可以随机指定 , 指定 start 与 end 之间的一个随机值
// 尽量不选取 start 和 end 索引的值
int pivot = array[(start + end) / 2];
// 2. 分割操作第二部 : 进行数组元素分割
// 注意此处, left 小于等于 right , 不能是小于
while (left <= right) {
// 找到一个不属于左边部分的元素, 将其交换到右边
while (left <= right && array[left] < pivot) {
// 如果遇到一个元素不属于左边, 则退出循环
left++;
}
// 找到一个不属于右边部分的元素, 将其交换到左边
while (left <= right && array[right] > pivot) {
// 如果遇到一个元素不属于右边, 则退出循环
right--;
}
// 交换上述检测出来的需要交换的元素
if (left <= right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
// 交换完毕后, 继续向后遍历
left++;
right--;
}
// 交换完毕后, 继续循环, 该循环退出的条件是 left >= right
}
// 分割完毕后, 继续递归
// 如果按照中心点分割完毕的话, 上面的循环退出, left >= right
// 索引的分布如下 : start , right, left, end
quickSort(array, start, right);
quickSort(array, left, end);
}
}腾讯云开发者
