排序二：快速排序

发表于   |   分类于 ， ，   |   评论

要点

快速排序是一种交换排序。
快速排序最早是由图灵获得者Tony Hoare设计出来的，被列为20世纪十大算法之一。

算法思想

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

从上面的文字描述理解起来可能很费力，下面直接通过图解的方式来说明：

快速排序示例图
通过上面的图解分析我们知道第一轮排序结束，得到的序列为：

1
2，1，3，4，5

并得到重合点的位置为3，然后分别对3左边的序列和右边的序列进行排序，直至整个序列都是有序的。

算法分析

快速排序算法的性能

快速排序算法的性能

空间复杂度

快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N次 的分割处理，所以占用空间也是 Nlog2N 个。

时间复杂度

  • 快速排序的时间性能取决于快速排序递归的深度；
  • 当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差；
  • 当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好；
  • 当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。

算法的稳定性

在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。

完整参考代码

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
61
62
63
64
65
66
67
68
69
70
package com.akathink.sort;
public class QuickSort {
	public int division(int[] list, int left, int right) {
		// 以最左边的数(left)为基准
		int base = list[left];
		while (left < right) {
			// 从序列右端开始，向左遍历，直到找到小于base的数
			while (left < right && list[right] >= base)
				right--;
			// 找到了比base小的元素，将这个元素放到最左边的位置
			list[left] = list[right];
			// 从序列左端开始，向右遍历，直到找到大于base的数
			while (left < right && list[left] <= base)
				left++;
			// 找到了比base大的元素，将这个元素放到最右边的位置
			list[right] = list[left];
		}
		// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
		// 而left位置的右侧数值应该都比left大。
		list[left] = base;
		return left;
	}
	private void quickSort(int[] list, int left, int right) {
		// 左下标一定小于右下标，否则就越界了
		if (left < right) {
			// 对数组进行分割，取出下次分割的基准标号
			int base = division(list, left, right);
			System.out.format("base = %d:\t", list[base]);
			printPart(list, left, right);
			// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
			quickSort(list, left, base - 1);
			// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
			quickSort(list, base + 1, right);
		}
	}
	// 打印序列
	public void printPart(int[] list, int begin, int end) {
		for (int i = 0; i < begin; i++) {
			System.out.print("\t");
		}
		for (int i = begin; i <= end; i++) {
			System.out.print(list[i] + "\t");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		// 初始化一个序列
		int[] array = { 3, 4, 1, 2, 5 };
		// 调用快速排序方法
		QuickSort quick = new QuickSort();
		System.out.print("排序前:\t\t");
		quick.printPart(array, 0, array.length - 1);
		quick.quickSort(array, 0, array.length - 1);
		System.out.print("排序后:\t\t");
		quick.printPart(array, 0, array.length - 1);
	}
}

运行结果

1
2
3
4
5
排序前:		3	4	1	2	5
base = 3:	2	1	3	4	5
base = 2:	1	2
base = 4:				4	5
排序后:		1	2	3	4	5

参考资料

《大话数据结构》
http://www.cnblogs.com/jingmoxukong/p/4302718.html

相关阅读

内功修养：数据结构总结之排序算法