摘要
快速排序算法的多种实现方案,动画示意,Java代码实现。
基本思路
使用分治思想。选择一个Pivot,把小于Pivot的放到Pivot左边,大于Pivot的放到Pivot右边。之后继续对Pivot分隔开的左右两侧做相同的操作,直到所有元素有序。
复杂度
这里讨论的是原地算法的复杂度。
1、最好的情况下,每次选取的Pivot,都能把数组平分为两部分,时间复杂度为 O(N·logN)
,空间复杂度为O(logN)
。
2、最坏的情况下,每次选取的Pivot,都是最大值(最小值),每次只能排好一个元素,退化为冒泡排序,时间复杂度为 O(N^2)
,空间复杂度为O(N)
。
总结:
- 时间复杂度:最好:
O(N·logN)
,最坏:O(N^2)
,平均:O(N·logN)
- 空间复杂度:最好:
O(logN)
,最坏:O(N)
具体的推导过程可以参考:https://blog.csdn.net/YuZhiHui_No1/article/details/44198701
Pivot选择
Pivot的选择是快速排序的关键,对复杂度起到决定作用。Pivot的选择有很多种,例如:
- 选第一个
- 选最后一个
- 选中间一个
- 随机选一个
- 三数取中法
为了便于算法实现,需要取中间某个Pivot时,可以通过交换元素,转换成取第一个(或最后一个)。
随机选取
使用Random随机选一个,并交换到开头。
static void movePivotToStart(int[] array, int start, int end) {
// 随机选一个作为pivot并移动到开头
int pivotIndex = start + new Random().nextInt(end - start);
swap(array, pivotIndex, start);
}
其中swap是通用的元素交换方法:
static void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
三数取中法
三数取中法的策略是,分别取开头、末尾和中间三个数,并将值处于中间的那个数作为Pivot。
代码实现如下,利用类似冒泡排序的思路,将start,mid,end按照从小到大的顺序排列起来。然后再把中间值即mid交换到start。
static void movePivotToStart(int[] array, int start, int end) {
int mid = (start + end) / 2;
if (array[start] > array[mid]) {
swap(array, start, mid);
}
if (array[mid] > array[end]) {
swap(array, mid, end);
}
if (array[start] > array[mid]) {
swap(array, start, mid);
}
swap(array, start, mid);
}
因为最后两步可能会对start和mid进行两次交换,还可以进一步优化为:
static void movePivotToStart(int[] array, int start, int end) {
int mid = (start + end) / 2;
if (array[start] > array[mid]) {
swap(array, start, mid);
}
if (array[mid] > array[end]) {
swap(array, mid, end);
}
if (array[start] <= array[mid]) {
swap(array, start, mid);
}
}
非原地算法
快排又分为非原地排序和原地排序。非原地排序思路很简单,但是给数组排序需要消耗额外内存。这个思路更适合链表排序。伪代码如下(来自维基百科 ):
function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else {
select a pivot value pivot from q
for each x in q except the pivot element {
if x < pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}
原地算法partition实现
通常会把选取pivot和移动元素的操作放到partition方法中,而partition有多种实现。
static void quickSort(int[] array, int start, int end) {
// start = end时,size为1,不需要排序
if (start >= end) {
return;
}
// 处理并返回pivot
int index = partition(array, start, end);
quickSort(array, start, index - 1);
quickSort(array, index + 1, end);
}
实现一:遍历
最常见的实现,选第一个作为Pivot,然后直接从左到右遍历,把数据分割为两部分。
static int partition(int[] array, int start, int end) {
// 取第一个作为轴
int pivot = array[start];
// index为pivot最终的位置,最终要满足 [start~index-1] < [index] < [index+1 ~ end]
int index = start;
// 循环过程中,先不移动pivot,满足 [start+1 ~ index] < pivot < [index+1 ~ end]
for (int i = start + 1; i <= end; i++) {
if (array[i] < pivot) {
index++;
swap(array, index, i);
}
}
// 最终交换 start 和 index,让pivot移动到正确的位置,
// 使得 [start~index-1] < [index] < [index+1 ~ end]
swap(array, start, index);
return index;
}
对应的示意图如下:
参考: https://www.cnblogs.com/onepixel/p/7674659.html
实现二:两端搜索交换
选中最后一个作为Pivot,先从左边找到第一个大于Pivot的元素,再从右边找到第一个小于Pivot的元素,将这两者交换。继续交互步骤直到两端相遇。
或者:选中第一个作为Pivot,先从右边找到第一个小于Pivot的元素,再从左边找到第一个大于Pivot的元素,将这两者交换。
注意选中一端作为Pivot,就必须先从另一端搜索,因为可能会有一个特殊情况,就是原始数组已经满足条件不需要调整。
static int partition(int[] array, int start, int end) {
int pivot = array[start];
// 这里有一种特殊情况,
// 原始数组已经满足 [start] < [start+1 ~ end],执行循环后,应该得到 i = j = start
// i必须从start开始,而不是 start + 1
int i = start, j = end;
while (i < j) {
// 必须先执行--j的操作
while (i < j && array[j] >= pivot) --j;
while (i < j && array[i] <= pivot) ++i;
if (i < j) {
swap(array, i, j);
}
}
// 移动pivot到正确位置
swap(array, start, i);
return i;
}
图片示意:
还可以参考:https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
顺便把图片摘录过来了:
实现三:挖坑法
挖坑法。选取第一个作为Pivot,并挖出来形成一个坑。先从右边找到第一个小于Pivot的元素,挖出来填到坑里。再从左边找到第一个大于Pivot的元素,挖出来填到坑里。继续填坑步骤直到两端相遇。
static int partition3(int[] array, int start, int end) {
int pivot = array[start];
// [start] 是第一个坑
int i = start, j = end;
while (i < j) {
while (i < j && array[j] >= pivot) --j;
if (i < j) {
// [j] 挪到 [i] , [j] 形成了新的坑
array[i] = array[j];
++i;
}
while (i < j && array[i] <= pivot) ++i;
if (i < j) {
// [i] 挪到 [j] , [i] 形成了新的坑
array[j] = array[i];
--j;
}
}
//退出时,i == j。将 pivot 填到这个坑中。
array[i] = pivot;
return i;
}
参考: https://blog.csdn.net/MoreWindows/article/details/6684558
总结:快排完整写法示例
下面给出一个快排完整示例,Pivot使用随机选取,两端搜索交换。
static void quickSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int pivot = partition(array, start, end);
quickSort(array, start, pivot - 1);
quickSort(array, pivot + 1, end);
}
static int partition(int[] array, int start, int end) {
movePivotToStart(array, start, end);
int pivot = array[start];
int i = start, j = end;
while (i < j) {
while (i < j && array[j] >= pivot) --j;
while (i < j && array[i] <= pivot) ++i;
if (i < j) {
swap(array, i, j);
}
}
swap(array, start, i);
return i;
}
static void movePivotToStart(int[] array, int start, int end) {
int pivotIndex = start + new Random().nextInt(end - start);
swap(array, pivotIndex, start);
}
static void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
最后,欢迎扫码关注微信公众号。程序员同行学习交流,聊天交友,国内外名企求职内推(微软 / 小冰 / Amazon / Shopee / Coupang / ATM / 头条 / 拼多多等),可加我微信 jzj2015 进技术群(备注进技术群,并简单自我介绍)。

本文由jzj1993原创,转载请注明来源:https://www.paincker.com/quick-sort
(标注了原文链接的文章除外)
暂无评论