十大排序算法之快速排序

发表于 | 分类于
字数统计: 1.5k 字 | 阅读时长 ≈ 6 分钟

本文首发于个人博客

前言

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

  • 使用的语言为：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

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

代码地址