排序算法之快速排序

发表于 | 分类于 ，

基本思想

在一趟排序过程中，选择一个基准值，通过交换的方式将待排序序列分为两个序列。其中一个序列在基准值左侧，这部分中所有数值都小于基准值；另一序列在基准值右侧，这部分中所有数值都大于基准值。然后对分割出的两个序列重复上述过程，直到排序结束。

详细排序步骤

  • 第一步：从待排序序列选取一个基准值（一般为待排序列的首元素）并记录，使得 i , j 分别指向待排序序列首元素和最后一个元素。
  • 第二步：从待排序序列右侧开始，比较 j 指向的元素和基准值的大小，如果大于基准值，j 向前移动一个元素，直到找到一个比基准值小的元素，停止 j 的移动。此时, 将 j 所指向的元素赋值给i所指向的元素，并让 i 向后移动一个元素。
  • 第三步：从待排序序列左侧开始，比较 i 指向的元素和基准值的大小，如果小于基准值，i 向后移动一个元素，直到找到一个比基准值大的元素，停止 i 的移动。此时, 将 i 所指向的元素赋值给 j 所指向的元素，并让 j 向前移动一个元素。
  • 第四步：重复上述步骤，直到 i 和 j 指向同一个元素，然后将基准值赋值给 i 和 j 所指向的元素。此时，序列已经被基准值分为两部分，左侧所有元素小于基准值，右侧所有的元素大于基准值。
  • 第五步：使用相同方法，对基准值两侧的序列分别进行排序。

排序示例

假设，对序列{3, 4, 63, 4, 0, 1, 32, -2, 21}进行排序。

第1步：选取基准值为3（序列首元素），此时，i=0，j=8。

第2步：
    从序列右侧开始向左逐渐移动 j 直到找到一个比3小的元素即-2，此时i=0, j=7。
    然后把 j 指向的元素赋值到 i 所在位置，此时序列变为：{-2, 4, 63, 4, 0, 1, 32, -2, 21}。

第3步：
    从序列左侧开始向右逐渐移动 i 直到找到一个比3大的元素即4，此时i=1, j=7。
    然后把 i 指向元素赋值到 j 所在位置，此时序列变为：{-2, 4, 63, 4, 0, 1, 32, 4, 21}。

第4步：
    从序列右侧开始向左逐渐移动 j 直到找到一个比3小的元素即1， 此时i=1, j=5。
    然后把 j 指向元素赋值到 i 所在位置，此时序列变为：{-2, 1, 63, 4, 0, 1, 32, 4, 21}。

第5步：
    从序列左侧开始向右逐渐移动 i 直到找到一个比3大的元素即63，此时i=2, j=5。
    然后把 i 指向元素赋值到 j 所在位置，此时序列变为：{-2, 1, 63, 4, 0, 63, 32, 4, 21}。

第6步：
    从序列右侧开始向左逐渐移动 j 直到找到一个比3小的元素即0， 此时i=2, j=4。
    然后把 j 指向元素赋值到 i 所在位置，此时序列变为：{-2, 1, 0, 4, 0, 63, 32, 4, 21}。

第7步：
    从序列左侧开始向右逐渐移动 i 直到找到一个比3大的元素即4，此时i=3, j=4。
    然后把 i 指向元素赋值到 j 所在位置，此时序列变为：{-2, 1, 0, 4, 4, 63, 32, 4, 21}。

第8步：
    从序列右侧开始向左移动 j ，于是i=j=3，将基准值赋值给i（或j）指向位置。序列变化为：{-2, 1, 0, 3, 4, 63, 32, 4, 21}

至此，第一趟排序结束。

此时序列以基准值分为了两部分，即小于基准值3的左侧部分{-2, 1, 0}和大于基准值3的右侧部分{4, 63, 32, 4, 21}。

下面再分别对序列{-2, 1, 0}和{4, 63, 32, 4, 21}按上述方法排序，详细过程不再演示。

说明：序列中加粗的数字为 i 所指向元素，斜体加粗数字为 j 所指向元素，如2 和 -2。

算法特点

时间复杂度

最坏情况下：对于一个有n个元素的序列来说，假如基准值右侧数据均大于（或小于）基准值，那么分割后的序列只有一个且序列长度为n-1，如果每次都发生这种情况，那块快速排序就退化程了冒泡排序，时间复杂度变为了O(n^2)。

理想情况下：
如果每次排序后都能将序列分为相等的两个部分，那么每次只需要对n/2的两个子序列进行排序。
在一个大小为 n 的记录中确定一个记录的位置所需要的时间为O(n)。
若T(n)为对n个记录进行排序所需要的时间，我们可以推导出快速排序的时间复杂度为：

1
2
3
4
5
6
T(n) <= cn + 2T(n/2)    c是一个常数
　　　<= cn + 2(cn/2+2T(n/4)) = 2cn+ 4T(n/4)
　　　<= 2cn + 4(cn/4+ 2T(n/8)) = 3cn + 8T(n/8)
	 <= 3cn + 8(cn/8 + 2T(n/16)) = 4cn + 16T(n/16)
　　　……
　　　<= cnlogn + nT(1) = O(nlogn)

其中cn 是一次划分所用的时间，c是一个常数

最坏的情况，每次划分都得到一个子序列，时间复杂度为：

1
2
3
4
5
T(n) = cn + T(n-1)
	 = cn + c(n-1) + T(n - 2) = 2cn -c + T(n-2)
     = 2cn -c + c(n - 2) + T(n-3) = 3cn -3c + T(n-3)
　　　……
　　　= c[n(n+1)/2-1] + T(1) =  O(n2)

稳定性

因为快速排序在进行交换时，只是根据比较基数值判断是否交换，且不是相邻元素来交换，在交换过程中可能改变相同元素的顺序，因此是一种不稳定的排序算法。

代码

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
public static int[] sort(int[] array, int start, int end) {
	if (start < 0 || end > array.length - 1) {
		return array;
	}
	int k = array[start];
	int i = start;
	int j = end;
	while (i < j) {
		while (i < j) {
			//从后往前依次查找，直到找到一个小于基准值的数
			if (k > array[j]) {
				array[i] = array[j];
				i++;
				break;
			}
			j--;
		}
		while (i < j) {
			//从前往后依次查找，直到找到一个大于基准值的数，
			if (k < array[i]) {
				array[j] = array[i];
				j--;
				break;
			}
			i++;
		}
		
	array[i] = k;
	if (start < i - 1) {
		sort(array, start, i - 1);
	}
	if (i + 1 < end) {
		sort(array, i + 1, end);
	}
	return array;
}

代码地址：快速排序源码

参考文章

  1. 面试题之——常用排序算法
  2. 快速排序