十大排序算法之快速排序

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为:Java
  • 结构为:
    定义抽象类Sort里面实现了,交换,大小比较等方法。例如交换两个值,直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* 返回值等于0,代表 array[i1] == array[i2]
* 返回值小于0,代表 array[i1] < array[i2]
* 返回值大于0,代表 array[i1] > array[i2]
*/
protected int cmp(int i1, int i2) {
return array[i1].compareTo(array[i2]);
}

protected int cmp(T v1, T v2) {
return v1.compareTo(v2);
}

protected void swap(int i1, int i2) {
T tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}

什么是快速排序

  • 快速排序(Quicksort)是对冒泡排序的一种改进。
    快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

算法思想

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:

  • 首先设定一个分界值,通过该分界值将数组分成左右两部分。

  • 将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。

  • 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

  • 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

算法分析

时间复杂度

  • 在轴点左右元素数量比较均匀的情况下,同时也是最好的情况 O(nlogn)
  • 如果轴点左右元素数量极度不均匀,最坏情况 O(n^2)
  • 为了降低最坏情况的出现概率,一般采用随机选择轴点元素

空间复杂度

  • 递归调用的原因,其空间复杂度是 O(nlogn)

算法稳定性

  • 快速排序是一种不稳定排序算法。

是否是原地算法

  • 何为原地算法?
    • 不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法,称为 Not-in-place 或者 Out-of-place
  • 快速排序属于 In-place

代码

代码逻辑

  • 从序列中选择一个轴点元素(pivot)

    • 假设每次选择0位置的元素为轴点元素
  • 利用pivot将序列分割成2个子序列

    • 将小于pivot的元素放在pivot左侧
    • 将大于pivot的元素放在pivot右侧
    • 等于pivot的元素放哪边都可以
  • 对子序列进行前面两步操作,直到不能再分割(子序列中只剩下一个元素)

  • 快速排序的本质

    • 逐渐将每个元素都转换成轴点元素
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
package YZ.Sort;

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

@Override
protected void sort() {
sort(0, array.length);
}
/**
* 对 [begin, end) 范围的元素进行快速排序
* @param begin
* @param end
*/
private void sort(int begin,int end) {
if (end-begin<2) {
return;
}
// 确定轴点位置 O(n)
int mid = pivotIndex(begin, end);
// 对子序列进行快速排序
sort(begin,mid);
sort(mid+1, end);
}

/**
* 构造出 [begin, end) 范围的轴点元素
* @return 轴点元素的最终位置
*/
private int pivotIndex(int begin,int end) {
//随机选择一个元素和begin位置的元素进行交换
swap(begin, begin+(int)Math.random()*(end-begin));
// 备份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; //break退出,从另外一边(begin)开始
}
}

while (begin<end) {
if (cmp(pivot, array[begin])>0) { // 左边元素 < 轴点元素
begin++;
}else {// 左边元素 >= 轴点元素
array[end--] = array[begin];
break;//break退出,从另外一边(end)开始
}
}
}
// 将备份的轴点元素放入最终的位置
array[begin] = pivot;
// 返回轴点元素的位置
return begin;
}
}

验证

使用数据源如下

Integer[] array = Integers.random(20000, 1, 80000);

结果为:

【BubbleSort】
稳定性:true 耗时:2.494s(2494ms) 比较次数:2.00亿 交换次数:9950.84万

【BubbleSort1】
稳定性:true 耗时:1.95s(1950ms) 比较次数:2.00亿 交换次数:9950.84万

【BubbleSort2】
稳定性:true 耗时:2.048s(2048ms) 比较次数:2.00亿 交换次数:9950.84万

【InsertionSort1】
稳定性:true 耗时:1.125s(1125ms) 比较次数:9952.84万 交换次数:9950.84万

【InsertionSort2】
稳定性:true 耗时:0.772s(772ms) 比较次数:9952.84万 交换次数:0

【InsertionSort3】
稳定性:true 耗时:0.546s(546ms) 比较次数:25.80万 交换次数:0

【SelectionSort】
稳定性:true 耗时:0.458s(458ms) 比较次数:2.00亿 交换次数:2.00万

【HeapSort】
稳定性:false 耗时:0.013s(13ms) 比较次数:51.08万 交换次数:2.00万

【QuickSort】
稳定性:false 耗时:0.01s(10ms) 比较次数:32.00万 交换次数:1.32万

【MergeSort】
稳定性:true 耗时:0.011s(11ms) 比较次数:26.08万 交换次数:0

结果来看快速排序性能还是很好的。

代码地址