快速排序算法概念
快速排序一般基于递归实现。其思路是这样的：
1.选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。
2.基于这个值，将数组分为两部分，较小的分在左边，较大的分在右边。
3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。
4.对两个子数组分别重复上述过程，直到每个数组只有一个元素。
5.排序完成。
基本实现方式：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1);}private static void qsort(int[] arr, int low, int high){ if (low < high){ int pivot=partition(arr, low, high); //将数组分为两部分 qsort(arr, low, pivot-1); //递归排序左子数组 qsort(arr, pivot+1, high); //递归排序右子数组 }}private static int partition(int[] arr, int low, int high){ int pivot = arr[low]; //枢轴记录 while (low<high){ while (low<high && arr[high]>=pivot) --high; arr[low]=arr[high]; //交换比枢轴小的记录到左端 while (low<high && arr[low]<=pivot) ++low; arr[high] = arr[low]; //交换比枢轴小的记录到右端 } //扫描完成，枢轴到位 arr[low] = pivot; //返回的是枢轴的位置 return low;} |
使用泛型实现快排算法
下面设计一个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 45int[] after sorting: 3 8 16 21 26 45 48 59 65 92String[] 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 |
