【基本思想】
Divide and Conquer分治思想
将原问题分成若干规模更小，但结构相似的小问题。递归解决子问题，再把子问题的解组合为原问题的解。
【步骤】
- 基准。选取一个元素作为基准
- 分区。将小于/大于基准的点分别放置在两边，分区结束后，基准所在的位置即为它的最终位置
- 对基准左右两边的数据集重复步骤1&2，知道所有子数据集只剩一个元素为止
【实例分析】
现有数组 Arr = [6 1 2 7 9 3 4 5 10 8]
- 选择基准，方便起见，选择第一个6
-
交换基准外的元素
两个变量 i 和 j，分别指向序列最左边和最右边i=0, j=9;
（先移动j，知道i j相遇）
j 一步一步地向左挪动（即 j--），直到找到一个小于 6 的数停下来;
i 再一步一步向右挪动（即 i++），直到找到一个数大于 6 的数停下来;
--第一次交换--
image
image
[6 1 2 5 9 3 4 7 10 8]
--“探测”继续--
i，j继续移动，j到了4位置，i到了9位置，交换
6 1 2 5 4 3 9 7 10 8
--“探测”继续--
j 继续向左挪动，他发现了 3；i 继续向右移动，此时哨兵 i 和哨兵 j 相遇了。探索结束。 -
交换基准
将基准数 6 和 3 进行交换。
3 1 2 5 4 6 9 7 10 8 -
拆分序列，继续探索
以 6 为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“ 9 7 10 8 ”。接下来还需要分别处理这两个序列。
3 1 2 5 4 ==> 2 1 3 5 4
2 1 ==> 1 2 5 4 ==> 4 5
【伪代码】
【JAVA代码实现】
public static void main(String[] args)
{
// TODO Auto-generated method stub
int[] arr = {6,1,2,7,9,3,4,5,10,8};
quick_sort(arr, 0, arr.length-1);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quick_sort(int[] arr, int l, int r) {
if(l < r) {
int i = l+1, j = r;
int p = arr[l];
while(i <= j) {
while(i <= j && arr[i] <= p) {
i = i+1;
}
while(i <= j && arr[j] > p) {
j = j-1;
}
if(i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
if(l < j) {
int tmp = arr[l];
arr[l] = arr[j];
arr[j] = tmp;
quick_sort(arr, l, j-1);
}
if(j < r) {
quick_sort(arr, j+1, r);
}
}
}
==>1 2 3 4 5 6 7 8 9 10
【性能分析】
快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。
1. 最优
时间复杂度为O(nlogn)
最优的情况，每次Partition都划分得很均匀。递归树的深度就为.logn.+1(.x.表示不大于x的最大整数)，需要递归logn次，时间为T(n)
T（n）≤2T（n/2） +n，T（1）=0
T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n
T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n
……
T（n）≤nT（1）+（log2n）×n= O(nlogn)
2. 最坏
时间复杂度为O(n^2)
待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。
需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置
因此比较次数为
3. 平均
O(nlogn)
设枢轴的关键字应该在第k的位置（1≤k≤n）
4. 空间复杂度
递归造成的栈空间
最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)
最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)
平均情况，空间复杂度也为O(logn)
5. 稳定性
由于关键字的比较和交换是跳跃进行的，所以为不稳定算法
【应用：常见面试题目】
- 找出数组中最小/大的k个数
- 数组中出现次数超过一半的数字
- 找出数组中第k个最小的数
- 荷兰旗问题
参考：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
https://blog.csdn.net/weshjiness/article/details/8660583
网友评论