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