快排算法的特点
- 实用性强。
很多实际的项目中使用了快排算法。但通常对算法都进行了调整（tuning），比如Java.util.Arrays类中的sort函数就使用了快排算法，但使用了双参考值（Dual-Pivot Quicksort）等一些改进措施。由于快排算法为递归算法，可以用循环代替递归函数调用，改进性能。
- 不需要额外的空间。
可以将数组中的数据直接交换位置实现排序，所以理论上不需要额外的空间。
时间复杂度
- 平均情况：O(nlgn)
- 最坏情况：O(n*n)，发生在当数据已经是排序状态时
快排算法的基本原理
1、从数据中选取一个值a[i]作为参考
2、以a[i] 为参考，将数据分成2部分：P1、P2，P1中的数据全部≤a[i]，P2中的数据全部＞a[i]，数据变为｛｛P1｝｛a[i]｝｛P2｝｝
3、将P1、P2重复上述步骤，直到各部分中只剩1个数据
4、数据完成升序排列
示例：
|
1
2
3
4
5
6
7
8
9
10
|
原始数据： ｛3，9，8，5，2，1，6｝
第1步：选取第1个数据：3
第2步：将数据分成2部分，左边≤3，右边大于>3：
｛2，1｝ ｛3｝ ｛9，8，5，6｝
第3步：将各部分重复以上步骤，直到每部分只剩1个数据：
｛2，1｝ => ｛1｝ ｛2｝
｛9，8，5，6｝ => ｛8，5，6｝ ｛9｝=> ｛5，6｝ ｛8｝ ｛9｝=> ｛5｝ ｛6｝ ｛8｝ ｛9｝
第4步：数据完成升序排列：
｛1｝ ｛2｝ ｛3｝ ｛5｝ ｛6｝ ｛8｝ ｛9｝
|
程序中数据通常保存在数组中，以int类型的数组为例，可以将上面的步骤写成一个quickSort函数原型：
|
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
|
quickSort(int begin, int end) {
//begin为数组的第一个数据的索引值，end为数组的最后一个数据的索引值+1 //如果只有1个数据或0个数据，则程序返回
if( begin == end || begin == (end-1) ) return;
int p = in[begin];//p为选择的参考数据，选择第一个数据
int a = begin +1; //a作为2部分数据分界线的索引值
int b = a;//b为待比较的数据的索引值
for( ; b < end; b++) {//将数组中的各个数据依次与参考数据进行比较
if( in[b] < p) { //如果该数据<参考数据则将其移动到左边
if(a == b){a++; continue;} //如果该数据已经在左边则不动
int temp = in[a];//将数据移动到左边
in[a] = in[b];
in[b] = temp;
a++;//将分界线右移
}
}
in[begin] = in[a-1];//讲参考值移动到2组数据中间
in[a-1] = p;
if( a-1 > begin){ // 如果左边有数据则将其重复上述步骤
quickSort(begin, a);
}
if( end-1 > a ) {// 如果右边有数据则将其重复上述步骤
quickSort(a, end);
}
return; // 如果无数据返回
} |
使用泛型实现快排算法
下面设计一个QuickSort类，包含了静态函数sort()，可以对任意类型数组进行排序。如果为对象类型数组，则该对象类型必须实现Comparable接口，这样才能使用compareTo函数进行比较。
使用了最基本的快排算法，没有进行优化处理。
源代码如下：
|
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class QuickSort {
@SuppressWarnings("unchecked")
//对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。
private static void quickSort(Object[] in,int begin, int end) {
if( begin == end || begin == (end-1) ) return;
Object p = in[begin];
int a = begin +1;
int b = a;
for( ; b < end; b++) {
//该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较
if( ((Comparable<Object>)in[b]).compareTo(p) < 0) {
if(a == b){a++; continue;}
Object temp = in[a];
in[a] = in[b];
in[b] = temp;
a++;
}
}
in[begin] = in[a-1];
in[a-1] = p;
if( a-1 > begin){
quickSort(in,begin, a);
}
if( end-1 > a ) {
quickSort(in,a, end);
}
return;
}
//使用泛型，对任意对象数组排序，该对象类型数组必须实现Comparable接口
public static <T extends Comparable<? super T>> void sort(T[] input){
quickSort(input,0,input.length);
}
//添加对List对象进行排序的功能，参考了Java中的Java.util.Collections类的sort()函数
public static <T extends Comparable<? super T>> void sort(List<T> list){
Object[] t = list.toArray();//将列表转换为数组
quickSort(t,0,t.length); //对数组进行排序
//数组排序完成后再写回到列表中
ListIterator<T> i = list.listIterator();
for (int j=0; j<t.length; j++) {
i.next();
i.set((T)t[j]);
}
}
//由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。
public static void sort(int[] input){
Integer[] t = new Integer[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];//封装
}
quickSort(t,0,t.length);//排序
for(int i = 0; i < input.length; i++){
input[i] = t[i];//解封装
}
}
//double[]数组的重载函数
public static void sort(double[] input){
Double[] t = new Double[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//byte[]数组的重载函数
public static void sort(byte[] input){
Byte[] t = new Byte[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//short[]数组的重载函数
public static void sort(short[] input){
Short[] t = new Short[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//char[]数组的重载函数
public static void sort(char[] input){
Character[] t = new Character[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//float[]数组的重载函数
public static void sort(float[] input){
Float[] t = new Float[input.length];
for(int i = 0; i < input.length; i++){
t[i] = input[i];
}
quickSort(t,0,t.length);
for(int i = 0; i < input.length; i++){
input[i] = t[i];
}
}
//测试用的main函数
public static void main(String[] args) {
//生产一个随机数组成的int[]数组，用来测试
int LEN = 10;
int[] input = new int[LEN];
Random r = new Random();
System.out.print("int[] before sorting: ");
for(int i = 0; i < input.length; i++) {
input[i] = r.nextInt(10*LEN);
System.out.print(input[i] + " ");
}
System.out.println();
System.out.print("int[] after sorting: ");
sort(input);
for(int i : input) {
System.out.print(i + " ");
}
System.out.println();
//生成一个字符串数组，用来测试
String[] s = new String[]{"b","a","e","d","f","c"};
System.out.print("String[] before sorting: ");
for(int i = 0; i < s.length; i++) {
System.out.print(s[i] + " ");
}
System.out.println();
System.out.print("String[] after sorting: ");
sort(s);
for(int i = 0; i < s.length; i++) {
System.out.print(s[i] + " ");
}
System.out.println();
//生成一个字符串列表，用来测试
List<String> l = new LinkedList<String>();
s = new String[]{"b","a","e","d","f","c"};
System.out.print("LinkedList<String> before sorting: ");
for (int j=0; j<s.length; j++) {
l.add(s[j]);
System.out.print(s[j] + " ");
}
System.out.println();
sort(l);
System.out.print("LinkedList<String> after sorting: ");
for (String ts : l) {
System.out.print(ts + " ");
}
System.out.println();
}
} |
运行main函数测试，从输出可以看出QuickSort类工作正常：
|
1
2
3
4
5
6
|
int[] before sorting: 65 48 92 26 3 8 59 21 16 45
int[] after sorting: 3 8 16 21 26 45 48 59 65 92
String[] before sorting: b a e d f c String[] after sorting: a b c d e f LinkedList<String> before sorting: b a e d f c LinkedList<String> after sorting: a b c d e f |
参考资料：
[1] 麻省理工学院公开课：算法导论> 快排及随机化算法
http://v.163.com/movie/2010/12/S/4/M6UTT5U0I_M6V2T7IS4.html
[2] Java官方API(Oracle Java SE7)源代码，下载安装JDK后，源代码位于安装根目录的src.zip文件中
http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html
[3] OpenJDK源代码下载（包括了HotSpot虚拟机、各个系统下API的源代码，其中API源代码位于openjdk\jdk\src\share\classes文件夹下）：
https://jdk7.java.net/source.html
http://my.oschina.net/u/1382972/blog/169747
http://www.tuicool.com/articles/BfY7Nz
相关推荐
实际应用中，由于快速排序的常数因子较小，即使在最坏情况下也通常比其他O(nlog n)的排序算法如归并排序表现得更快。 值得注意的是，上述代码没有考虑优化措施，例如三数取中法选择枢轴，或者使用插入排序处理小...
这是一个使用JAVA实现的泛型编程，分为两部分，第一部分创建泛型类，并实例化泛型对象，得出相加结果。 第二部分用户自行输入0--4，选择要进行的加减乘除运算或退出，再输入要进行运算的两个数，并返回运算结果及...
JAVA泛型源代码实现以下功能：返回数组元素的最大值/最小值下标；判断数组元素是否按升序排列；T对象数组排序；二分法查找key元素；
Java泛型是Java编程语言中的一个强大特性，它允许在定义类、接口和方法时使用类型参数，从而实现参数化类型。这使得代码更加安全、可读性更强，并且能够减少类型转换的必要。在“java泛型的内部原理及更深应用”这个...
Java泛型的用法及T.class的获取过程解析 Java泛型是Java编程语言中的一种重要特性，它允许开发者在编写代码时指定类型参数，从而提高代码的灵活性和可读性。本文将详细介绍Java泛型的用法 及T.class的获取过程解析...
下面我们将深入探讨Java泛型方法的概念、语法以及使用示例。 **一、泛型方法概念** 泛型方法是一种具有类型参数的方法，这些类型参数可以在方法声明时指定，并在方法体内部使用。与类的泛型类似，它们提供了编译时...
Java泛型是Java编程语言中的一个强大特性，它允许我们在定义类、接口和方法时指定类型参数，从而实现代码的重用和类型安全。在Java泛型应用实例中，我们可以看到泛型如何帮助我们提高代码的灵活性和效率，减少运行时...
- Java集合框架（如ArrayList、LinkedList、HashMap等）广泛使用了泛型，确保插入和检索的对象类型与集合定义的类型一致。 - 使用泛型集合可以避免`ClassCastException`，并提高代码的可读性和安全性。 7. **野...
在本文中，我们将详细介绍 Java 泛型的使用方法和实现原理。 一、泛型的简介 泛型是 Java 5 中引入的一种语言特性，旨在解决类型安全问题。在 Java 中，泛型可以应用于集合、类、接口和方法中。泛型的主要目的是...
Java泛型机制详解 Java泛型是Java语言中的一种机制，用于在编译期检查类型安全。Java泛型的出现解决了Java早期版本中类型安全检查的缺陷。Java泛型的好处是可以在编译期检查类型安全，避免了运行时的...
泛型接口是泛型在接口中的应用，它允许我们在接口中定义带有类型参数的方法，使得实现该接口的类可以使用不同的数据类型。下面我们将详细探讨Java泛型接口的相关知识点。 1. **泛型接口的定义** 泛型接口的定义...
Java 泛型详解 Java 泛型是 Java SE 5.0 中引入的一项特征，它允许程序员在编译时检查类型安全，从而减少了 runtime 错误...通过了解 Java 泛型的基本概念和关键字，我们可以更好地使用泛型来提高代码的质量和可读性。
Java泛型技术是Java编程语言中的一个重要特性，它在2004年随着Java SE 5.0的发布而引入，极大地增强了代码的类型安全性和可读性。本篇文章将深入探讨Java泛型的发展历程、核心概念以及其在实际开发中的应用。 一、...