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
排序的结构我就不公布了。我大概试了一下最快的应该是自己插入排序吧。冒泡最慢。。。。。。。