【算法】快速排序
算法 系列博客
【算法】刷题范围建议 和 代码规范
【算法】复杂度理论 ( 时间复杂度 )
【字符串】最长回文子串 ( 蛮力算法 )
【字符串】最长回文子串 ( 中心线枚举算法 )
【字符串】最长回文子串 ( 动态规划算法 ) ★
【字符串】字符串查找 ( 蛮力算法 )
【字符串】字符串查找 ( Rabin-Karp 算法 )
【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )
【算法】双指针算法 ( 有效回文串 II )
【算法】哈希表 ( 两数之和 )
一、快速排序思想
快速排序的思想 : 先 整体有序 , 后 局部有序 , 分治算法 ;
先从数组中 挑选出一个数 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]
进行推导 , 即可出现死循环 ;
快速排序的时间复杂度是 O ( n log n ) O(n \log n) O(nlogn) ;
代码示例 :
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);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
文章来源: hanshuliang.blog.csdn.net,作者:韩曙亮,版权归原作者所有,如需转载,请联系作者。
原文链接:hanshuliang.blog.csdn.net/article/details/119133567
- 点赞
- 收藏
- 关注作者
评论(0)