我的Github地址
小码哥《恋上数据结构与算法》笔记
极客时间《iOS开发高手课》笔记
iOS大厂面试高频算法题总结
iOS面试资料汇总
快速排序(Quick Sort)
一、概念
- 从序列中选择一个
轴点元素(pivot)
,假设每次选择0
位置的元素为轴点元素。
- 利用
pivot
将序列分割成2
个子序列,将小于pivot
的元素放在pivote
前面(左侧),将大于pivot
的元素放在pivot
后面(右侧),等于pivot
的元素放在哪边都可以。
- 对子序列进行上一步操作,直到不能再分割(子序列中只剩下
1
个元素)。
- 快速排序的本质:逐渐将每个元素都转换成轴点元素。
二、轴点构造
- 将
6
作为轴点,备份一份。
- 从
右边(end)
开始扫描数组。
- 扫描
7
,大于6a
,执行end--
即可。
- 扫描
5
,小于6a
,用5
覆盖6a
的位置,begin++
。
- 下一步,从
左边(begin)
继续扫描。
- 扫描
8a
,大于6a
,用8a
覆盖5
的位置,end--
。
- 下一步,从
右边(end)
继续扫描
- 扫描
9
,大于6a
,执行end--
,不做其他操作。
- 扫描
4
,小于6a
,用4
覆盖8a
的位置,begin++
。
- 扫描
8b
,大于6a
,用8b
覆盖4
的位置,end--
。
- 扫描
6b
,等于6a
,用6b
覆盖8b
的位置,begin++
。
- 扫描
2
,小于6a
,begin++
。
- 当发现
begin
和end
重叠,则轴点构造完成。将备份的6a
,覆盖6b
的位置。
三、代码实现
public class QuickSort<T extends Comparable<T>> extends Sort<T> {
@Override
protected void sort() {
sort(0, array.length);
}
private void sort(int begin, int end) {
if (end - begin < 2) return;
int mid = pivotIndex(begin, end);
sort(begin, mid);
sort(mid + 1, end);
}
private int pivotIndex(int begin, int end) {
swap(begin, begin + (int)(Math.random() * (end - begin)));
T pivot = array[begin];
end--;
while (begin < end) {
while (begin < end) {
if (cmp(pivot, array[end]) < 0) {
end--;
} else {
array[begin++] = array[end];
break;
}
}
while (begin < end) {
if (cmp(pivot, array[begin]) > 0) {
begin++;
} else {
array[end--] = array[begin];
break;
}
}
}
array[begin] = pivot;
return begin;
}
}
- 在当前算法,如果序列中的
元素a
与轴点元素
相等,则会将轴点元素
与元素a
替换位置。
- 如果
元素a
与轴点元素
相等时,不进行替换,那么最终得到的数组会非常不平衡(黄色轴点在数组中的位置),导致出现最坏时间复杂度O(n^2)。
四、时间复杂度
- 在轴点左右元素数量比较均匀的情况下,同时也是最好的情况,时间复杂度是
O(nlogn)
。
- 如果轴点左右元素数量极度不均匀,最坏情况是
O(n^2)
。
- 为了降低最坏情况的出现概率,一般采取的做法是
随机选择轴点元素
。
- 由于递归调用的缘故,空间复杂度是:
O(logn)
。
- 快速排序属于
不稳定排序
。