快速排序算法概念
快速排序一般基于遞歸實(shí)現(xiàn)。其思路是這樣的：
1.選定一個(gè)合適的值（理想情況中值最好，但實(shí)現(xiàn)中一般使用數(shù)組第一個(gè)值）,稱為“樞軸”(pivot)。
2.基于這個(gè)值，將數(shù)組分為兩部分，較小的分在左邊，較大的分在右邊。
3.可以肯定，如此一輪下來(lái)，這個(gè)樞軸的位置一定在最終位置上。
4.對(duì)兩個(gè)子數(shù)組分別重復(fù)上述過(guò)程，直到每個(gè)數(shù)組只有一個(gè)元素。
5.排序完成。
基本實(shí)現(xiàn)方式：
|
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); //將數(shù)組分為兩部分 qsort(arr, low, pivot-1); //遞歸排序左子數(shù)組 qsort(arr, pivot+1, high); //遞歸排序右子數(shù)組 }}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;} |
使用泛型實(shí)現(xiàn)快排算法
下面設(shè)計(jì)一個(gè)QuickSort類，包含了靜態(tài)函數(shù)sort()，可以對(duì)任意類型數(shù)組進(jìn)行排序。如果為對(duì)象類型數(shù)組，則該對(duì)象類型必須實(shí)現(xiàn)Comparable接口，這樣才能使用compareTo函數(shù)進(jìn)行比較。
使用了最基本的快排算法，沒(méi)有進(jìn)行優(yōu)化處理。
源代碼如下：
|
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") //對(duì)上述快排函數(shù)原型修改，使其可以對(duì)任意對(duì)象類型數(shù)組進(jìn)行排序。這個(gè)函數(shù)為內(nèi)部使用，外部排序函數(shù)接口為sort()，sort函數(shù)要求對(duì)象必須實(shí)現(xiàn)Comparable接口，可以提供編譯時(shí)類型檢測(cè)，見(jiàn)后文。 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++) { //該對(duì)象類型數(shù)組必須實(shí)現(xiàn)Comparable接口，這樣才能使用compareTo函數(shù)進(jìn)行比較 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; } //使用泛型，對(duì)任意對(duì)象數(shù)組排序，該對(duì)象類型數(shù)組必須實(shí)現(xiàn)Comparable接口 public static <T extends Comparable<? super T>> void sort(T[] input){ quickSort(input,0,input.length); } //添加對(duì)List對(duì)象進(jìn)行排序的功能，參考了Java中的Java.util.Collections類的sort()函數(shù) public static <T extends Comparable<? super T>> void sort(List<T> list){ Object[] t = list.toArray();//將列表轉(zhuǎn)換為數(shù)組 quickSort(t,0,t.length); //對(duì)數(shù)組進(jìn)行排序 //數(shù)組排序完成后再寫(xiě)回到列表中 ListIterator<T> i = list.listIterator(); for (int j=0; j<t.length; j++) { i.next(); i.set((T)t[j]); } } //由于Java中原始數(shù)據(jù)類型（int、double、byte等）無(wú)法使用泛型，所以只能使用函數(shù)重載機(jī)制實(shí)現(xiàn)對(duì)這些原始類型數(shù)組（int[]、double[]、byte[]等）的排序。這里為了共用同一個(gè)排序函數(shù)，利用原始類型的(AutoBoxing，UnBoxing)機(jī)制將其封裝為對(duì)應(yīng)對(duì)象類型，組成新的對(duì)象數(shù)組，排序后再解封裝，這樣的缺點(diǎn)是需要額外的轉(zhuǎn)換步驟、額外的空間保存封裝后的數(shù)組。另一種方式是將排序代碼復(fù)制到各個(gè)重載函數(shù)中，官方API中的Java.util.Arrays這個(gè)類中的sort()函數(shù)就是使用這種方法，可以從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[]數(shù)組的重載函數(shù) 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[]數(shù)組的重載函數(shù) 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[]數(shù)組的重載函數(shù) 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[]數(shù)組的重載函數(shù) 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[]數(shù)組的重載函數(shù) 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]; } } //測(cè)試用的main函數(shù) public static void main(String[] args) { //生產(chǎn)一個(gè)隨機(jī)數(shù)組成的int[]數(shù)組，用來(lái)測(cè)試 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(); //生成一個(gè)字符串?dāng)?shù)組，用來(lái)測(cè)試 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(); //生成一個(gè)字符串列表，用來(lái)測(cè)試 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(); }} |
運(yùn)行main函數(shù)測(cè)試，從輸出可以看出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 |
