1 package com.anduo.sort;剛剛在大魚的博客上看到關于排序算法的文章，自己就做了下小實驗，代碼就是自己copy大魚的了。謝謝大魚了。
首先建好一個排序類，我就命名為Sort了
1 package com.anduo.sort;
2
3 /*******************************************************************************
4 * 插入排序:直接插入排序、折半插入排序和系爾排序
5 * 交換排序:冒泡排序和快速排序
6 * 選擇排序:簡單選擇排序和堆排序
7 * 歸并排序:歸并排序
8 *
9 * 基本思想
10 * 插入排序:將第N個記錄插入到前面(N-1)個有序的記錄當中。
11 * 交換排序:按照某種順序比較兩個記錄的關鍵字大小，然后根據需要交換兩個記錄的位置。
12 * 選擇排序:根據某種方法選擇一個關鍵字最大的記錄或者關鍵字最小的記錄，放到適當的位置。
13 *
14 * 排序方法比較
15 * 排序方法 平均時間 最壞時間 輔助存儲
16 * 直接插入排序 O(N2) O(N2) O(1)
17 * 起泡排序 O(N2) O(N2) O(1)
18 * 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
19 * 簡單選擇排序 O(N2) O(N2) O(1)
20 * 堆排序 O(Nlog2N) O(Nlog2N) O(1)
21 * 歸并排序 O(Nlog2N) O(Nlog2N) O(n)
22 * 基數排序 O(d(n+radix)) O(d(n+radix)) O(radix)
23 * @author anduo
24 *
25 */
26 public class Sort {
27
28 /***************************************************************************
29 * 歸并排序法————歸并排序
30 *
31 * @param data
32 **************************************************************************/
33 public static void recursionSort(Number[] data) {
34 Number[] result = merge_sort(data, 0, data.length - 1);
35 for (int i = 0; i < result.length; i++) {
36 data[i] = result[i];
37 }
38 }
39
40 private static Number[] merge_sort(Number[] array, int start, int end) {
41 Number[] result = new Number[end - start + 1];
42 if (start < end) {
43 int mid = (start + end) / 2;
44 Number[] left = merge_sort(array, start, mid);
45 Number[] right = merge_sort(array, mid + 1, end);
46 result = merge(left, right);
47 } else if (start == end) {
48 result[0] = array[start];
49 return result;
50 }
51 return result;
52 }
53
54 private static Number[] merge(Number[] left, Number[] right) {
55 Number[] result = new Number[left.length + right.length];
56 int i = 0;
57 int j = 0;
58 int k = 0;
59 while (i < left.length && j < right.length) {
60 if (left[i].doubleValue() < right[j].doubleValue()) {
61 result[k++] = left[i++];
62 } else {
63 result[k++] = right[j++];
64 }
65 }
66 while (i < left.length) {
67 result[k++] = left[i++];
68 }
69 while (j < right.length) {
70 result[k++] = right[j++];
71 }
72 return result;
73 }
74
75 /***************************************************************************
76 * 選擇排序————堆排序
77 *
78 * @param data
79 */
80 public static void heapSort(Number[] data) {
81 int n = data.length;
82 for (int i = n / 2; i >= 0; i--) {
83 keepHeap(data, n, i);
84 }
85 while (n > 0) {
86 swap(data, 0, n - 1);
87 keepHeap(data, --n, 0);
88 }
89 }
90
91 private static void keepHeap(Number[] a, int n, int i) {
92 Number x = a[i];
93 int j = 2 * i + 1;
94 while (j <= n - 1) {
95 if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue())
96 ++j;
97 if (a[j].doubleValue() > x.doubleValue()) {
98 a[i] = a[j];
99 i = j;
100 j = 2 * i;
101 } else {
102 break;
103 }
104 }
105 a[i] = x;
106 }
107
108 /***************************************************************************
109 * 選擇排序————簡單選擇排序
110 *
111 * @param data
112 **************************************************************************/
113 public static void selectSort(Number[] data) {
114 for (int i = 0; i < data.length - 1; i++) {
115 int smallPoint = i;
116 for (int j = i + 1; j < data.length; j++) {
117 if (data[smallPoint].doubleValue() > data[j].doubleValue()) {
118 smallPoint = j;
119 }
120 }
121 swap(data, i, smallPoint);
122 }
123 }
124
125 /***************************************************************************
126 * 交換排序————快速排序
127 *
128 * @param data
129 **************************************************************************/
130 public static void quickSort(Number[] data) {
131 QuickSort(data, 0, data.length - 1);
132 }
133
134 private static void QuickSort(Number[] data, int begin, int end) {
135 if (begin < end) {
136 // 取中點
137 int mid = (begin + end) / 2;
138 if (data[end].doubleValue() < data[begin].doubleValue()) {
139 swap(data, end, begin);
140 }
141 if (data[end].doubleValue() < data[mid].doubleValue()) {
142 swap(data, end, mid);
143 }
144 if (data[mid].doubleValue() < data[begin].doubleValue()) {
145 swap(data, mid, begin);
146 }
147 swap(data, mid, begin);
148 int min = begin + 1;
149 int big = end;
150 while (true) {
151 while (min < big
152 && data[min].doubleValue() < data[begin].doubleValue()) {
153 min++;
154 }
155 while (min < big
156 && data[big].doubleValue() >= data[begin].doubleValue()) {
157 big--;
158 }
159 if (min >= big) {
160 break;
161 }
162 swap(data, min, big);
163 }
164 if (data[begin].doubleValue() > data[min].doubleValue()) {
165 swap(data, begin, min);
166 }
167 if (min > 1)
168 QuickSort(data, begin, min - 1);
169 QuickSort(data, min, end);
170 }
171 }
172
173 /***************************************************************************
174 * 插入排序————希爾排序
175 *
176 * @param data
177 **************************************************************************/
178 public static void shellSort(Number[] data) {
179 int span = data.length / 7;
180 if (span == 0)
181 span = 1;
182 while (span >= 1) {
183 for (int i = 0; i < span; i++) {
184 for (int j = i; j < data.length; j = j + span) {
185 // 組內直接插入排序
186 int p = j - span;
187 Number temp = data[j];
188 while (p >= 0 && data[p].doubleValue() > temp.doubleValue()) {
189 data[p + span] = data[p];
190 p -= span;
191 }
192 data[p + span] = temp;
193 }
194 }
195 span = span / 2;
196 }
197 }
198
199 /***************************************************************************
200 * 插入排序————折半插入排序
201 *
202 * @param data
203 **************************************************************************/
204 public static void binarySearchSort(Number[] data) {
205 Number tmp = null;
206 for (int i = 1; i < data.length; i++) {
207 tmp = data[i];
208 int smallpoint = 0;
209 int bigpoint = i - 1;
210 while (bigpoint >= smallpoint) {
211 int mid = (smallpoint + bigpoint) / 2;
212 if (tmp.doubleValue() > data[mid].doubleValue()) {
213 smallpoint = mid + 1;
214 } else {
215 bigpoint = mid - 1;
216 }
217 }
218 for (int j = i; j > smallpoint; j--) {
219 data[j] = data[j - 1];
220 }
221 data[bigpoint + 1] = tmp;
222 }
223 }
224
225 /***************************************************************************
226 * 插入排序————直接插入排序
227 *
228 * @param data
229 **************************************************************************/
230 public static void straightInsertionSort(Number[] data) {
231 Number tmp = null;
232 for (int i = 1; i < data.length; i++) {
233 tmp = data[i];
234 int j = i - 1;
235 while (j >= 0 && tmp.doubleValue() < data[j].doubleValue()) {
236 data[j + 1] = data[j];
237 j--;
238 }
239 data[j + 1] = tmp;
240 }
241 }
242
243 /***************************************************************************
244 * 交換排序-----冒泡排序
245 *
246 * @param data
247 **************************************************************************/
248 public static void bulleSort(Number[] data) {
249 for (int i = 0; i < data.length; i++) {
250 // 將相鄰兩個數進行比較，較大的數往后冒泡
251 for (int j = 0; j < data.length - i - 1; j++) {
252 if (data[j].doubleValue() > data[j + 1].doubleValue()) {
253 // 交換相鄰兩個數
254 swap(data, j, j + 1);
255 }
256 }
257 }
258 }
259
260 /**
261 * 交換數組中指定的兩元素的位置
262 *
263 * @param data
264 * @param x
265 * @param y
266 */
267 private static void swap(Number[] data, int x, int y) {
268 Number temp = data[x];
269 data[x] = data[y];
270 data[y] = temp;
271 }
272 }
273
接著開始寫單元測試
1
2 package com.anduo.sort;
3 import java.util.ArrayList;
4 import java.util.Date;
5 import java.util.List;
6
7 import org.junit.AfterClass;
8 import org.junit.BeforeClass;
9 import org.junit.Test;
10
11 public class SortTest {
12
13 private static Number[] data;
14 private static long beginTime;
15 private static long endTime;
16
17 private static Integer[] getRundom(long num) {
18 List<Integer> list = new ArrayList<Integer>();
19 for (long i = 0; i < num; i++) {
20 int k;
21 if (Math.random() > 0.5) {
22 k = (int) (Math.random() * Integer.MAX_VALUE);
23 } else {
24 k = (int) (Math.random() * Integer.MIN_VALUE);
25 }
26 list.add(k);
27 }
28 return list.toArray(new Integer[list.size()]);
29 }
30
31 @BeforeClass
32 public static void beforeClass() {
33 data = getRundom(100000);
34 System.out.println("----------------------------------------------");
35 }
36
37 @AfterClass
38 public static void afterClass() {
39 }
40
41 @Test
42 public void testRecursionSort() {
43 System.out.println("test RecursionSort 遞歸排序");
44 beginTime = new Date().getTime();
45 Sort.recursionSort(data);
46 endTime = new Date().getTime();
47 System.out.println(endTime - beginTime);
48 System.out.println("----------------------------------------------");
49 }
50
51 @Test
52 public void testHeapSort() {
53 System.out.println("test HeapSort 堆排序");
54 beginTime = new Date().getTime();
55 Sort.heapSort(data);
56 endTime = new Date().getTime();
57 System.out.println(endTime - beginTime);
58 System.out.println("----------------------------------------------");
59 }
60
61 @Test
62 public void testQuickSort() {
63 System.out.println("test QuickSort 快速排序");
64 beginTime = new Date().getTime();
65 Sort.quickSort(data);
66 endTime = new Date().getTime();
67 System.out.println(endTime - beginTime);
68 System.out.println("----------------------------------------------");
69 }
70
71 @Test
72 public void testShellSort() {
73 System.out.println("test ShellSort 希爾排序");
74 beginTime = new Date().getTime();
75 Sort.shellSort(data);
76 endTime = new Date().getTime();
77 System.out.println(endTime - beginTime);
78 System.out.println("----------------------------------------------");
79 }
80
81 @Test
82 public void testBinarySearchSort() {
83 System.out.println("test BinarySearchSort 二分搜索排序");
84 beginTime = new Date().getTime();
85 Sort.binarySearchSort(data);
86 endTime = new Date().getTime();
87 System.out.println(endTime - beginTime);
88 System.out.println("----------------------------------------------");
89 }
90
91 @Test
92 public void testStraightInsertionSort() {
93 System.out.println("test StraightInsertionSort 直接插入排序");
94 beginTime = new Date().getTime();
95 Sort.straightInsertionSort(data);
96 endTime = new Date().getTime();
97 System.out.println(endTime - beginTime);
98 System.out.println("----------------------------------------------");
99 }
100
101 @Test
102 public void testBulleSort() {
103 System.out.println("test BulleSort 冒泡排序");
104 beginTime = new Date().getTime();
105 Sort.bulleSort(data);
106 endTime = new Date().getTime();
107 System.out.println(endTime - beginTime);
108 System.out.println("----------------------------------------------");
109 }
110
111 @Test
112 public void testSelectSort() {
113 System.out.println("test SelectSort 選擇排序");
114 beginTime = new Date().getTime();
115 Sort.selectSort(data);
116 endTime = new Date().getTime();
117 System.out.println(endTime - beginTime);
118 System.out.println("----------------------------------------------");
119 }
120
121 }
122
排序的結構我就不公布了。我大概試了一下最快的應該是自己插入排序吧。冒泡最慢。。。。。。。