排序算法系列——八大排序算法对比分析

本系列最后一篇,综合分析下前面介绍的八种排序算法的效率,以及各自的适用情况。
下面先看看八种排序算法的时间复杂度表格:
八种排序算法时间复杂度
图中八种排序被分成了两组,一组时间复杂度为O(n^2),另一组相对高效些。
下面先对第一组O(n^2)的四种排序算法进行对比,分别取数组长度为100,1000,10000,100000四个数量级,各个元素在0-10000000之间随机获取。下面看下结果的分析。

排序算法 长度=100 长度=1000 长度=10000 长度=100000
直接插入排序 535 2,198 135,773 16,554,053
希尔排序 308 703 3,639 39,769
直接选择排序 382 3,219 232,495 24,201,891
冒泡排序 525 5,377 475,865 62,703,335

从上表可以看出,以上四种算法效率最高的绝对是希尔排序,其次是直接插入排序,再就是直接选择排序,最后才是冒泡排序。事实证明冒泡排序真的不适合实际应用,实际使用中最优先选择希尔排序,但是如果要求稳定性的话就选择直接插入排序,但是效率差太多了。
下面主要对另外四个排序算法进行对比,不过通过上面的结果,所以在这里把希尔排序也加进来一起比较。由于基数排序对数组最大位数敏感,所以这里会分别对最大值为3位、4位、5位、6位、7位五种情况分别对应长度为10000,100000,1000000,10000000四种情况进行比较,长度太小体现不出O(nlgn)的优势。

排序算法 长度=10000 长度=100000 长度=1000000 长度=10000000
希尔排序 3996 36439 876530 12129001
堆排序 3451 38077 767878 10459868
快速排序 2446 37998 2566811 673399814
归并排序 2549 23595 356314 8325651
基数排序 4162 12724 272851 10866036

上表是MaxValue=1000时的结果,从表中可以看出当长度为10000时快速排序和归并排序效果最好,基数排序效果最差,但是当长度达到10W和100W基数排序效果最好,不过归并排序效率就比快速排序高很多了,同时快速排序当排序数组长度达到100W时效果变得很差,远远落后其他四个排序算法。所以当待排序数组最大值为1000时,数组长度为10000时使用快速和归并,当长度为1000W以内使用基数排序,或者归并排序。

排序算法 长度=10000 长度=100000 长度=1000000 长度=10000000
希尔排序 16349 201486 2800650 53033110
堆排序 3622 130898 3091654 51502613
快速排序 2366 83221 985588 71016772
归并排序 2544 60744 841400 20983723
基数排序 4815 42903 962442 15133291

以上是MaxValue=10000时的结果,从表中可以看出基数排序的效果最好,其次是归并排序,然后快速排序。所以当待排序数组最大值为10000时使用基数排序还是很不错的,虽然长度在10000时效果不如归并排序。当然归并排序也是个不错的选择。

排序算法 长度=10000 长度=100000 长度=1000000 长度=10000000
希尔排序 5107 203601 3401635 89081661
堆排序 5900 140530 4087559 76957182
快速排序 2873 89582 1553479 30429666
归并排序 3215 81579 1238016 21442519
基数排序 15017 65216 1116738 16308437

以上是MaxValue=100000时的结果,从表中可以看出结果同MaxValue=10000时的结果差不多。

排序算法 长度=10000 长度=100000 长度=1000000 长度=10000000
希尔排序 3701 246185 3496864 79870999
堆排序 3999 122765 3563651 69155734
快速排序 14974 45710 1351332 19350824
归并排序 3718 47956 1375705 23364515
基数排序 15001 37974 1290274 16083427

以上是MaxValue=1000000时的结果,结果还是一样,基数排序效果最好。

排序算法 长度=10000 长度=100000 长度=1000000 长度=10000000
希尔排序 4063 235374 3524810 92989117
堆排序 11444 155166 3461969 63201731
快速排序 7501 61635 1435866 19843452
归并排序 3376 42739 1322604 20859039
基数排序 6159 106208 1535261 25146006

以上是MaxValue=10000000时的结果,基数排序的效率已经没有归并排序好了,应该由于归并的次数增加了。
这里有个地方很奇怪,可以从上面MaxValue=1000时的表中可以看到当长度=100W时,快速排序的时间超过其他四个排序一个数量级,但是当MaxValue=10000,甚至更大之后快速排序的时间都和其它排序是一个数据量,而且MaxValue=1000时耗时大于MaxValue=10000以上。具体原因未知,大家可以自己测试,也许重复元素太多会影响快速排序的效率?
综合以上所有测试结果,总结各个排序算法的适用场景。
直接插入排序:直接用希尔排序替代就好,除非待排序数组本身就是部分有序
希尔排序: 效果最好,秒杀所有O(n^2)的排序算法,所在在数据量较小的场景下,如100000个元素以下都可考虑希尔排序
直接选择排序: 直接用希尔排序替代,或者用堆排序替代
冒泡排序: 强烈推荐不使用此排序算法
堆排序: 优于希尔排序,推荐替代希尔排序,但是如果待排序数组是部分有序的那么希尔优于堆排序
快速排序: 数组长度100W以下效率最高,100W以上可以用归并排序替代
归并排序: 不考虑基数排序的话,数组长度100W以上效率最高,100W以下可以用快速排序替代
基数排序: 适用场景要求较高,元素必须是整数,整数时长度10W以上,最大值100W以下效率较好,但是基数排序比其他排序好在可以适用字符串,或者其他需要根据多个条件进行排序的场景,例如日期,先排序日,再排序月,最后排序年 ,其它排序算法可是做不了的。
下面附上测试代码:

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
package com.vicky.sort;

import java.util.Random;
import java.util.Scanner;

import org.junit.Test;

public class SortComparison2 {

/**
* 比较全部排序算法
*/

@Test
public void testAll() {
Scanner scan = new Scanner(System.in);
int num = -1;
int maxValue = -1;
while (true) {
// 从命令行输入元素数量,以及最大值,格式:10,1000,输入quit结束
String input = scan.next();
if ("quit".equals(input)) {
System.exit(1);
}
String[] strs = input.split(",");
num = Integer.parseInt(strs[0]);
maxValue = Integer.parseInt(strs[1]);
System.out.println("Sort Data Num = " + num + ", MaxValue = " + maxValue);

Random ran = new Random();
Integer[] data = new Integer[num];
Integer[] data1 = new Integer[data.length];
Integer[] data2 = new Integer[data.length];
Integer[] data3 = new Integer[data.length];
Integer[] data4 = new Integer[data.length];
Integer[] data5 = new Integer[data.length];
Integer[] data6 = new Integer[data.length];
Integer[] data7 = new Integer[data.length];
Integer[] data8 = new Integer[data.length];
for (int i = 0; i < data.length; i++) {
data[i] = ran.nextInt(maxValue);
data1[i] = data[i];
data2[i] = data[i];
data3[i] = data[i];
data4[i] = data[i];
data5[i] = data[i];
data6[i] = data[i];
data7[i] = data[i];
data8[i] = data[i];
}
// 插入排序
long insertTimes = testStraightInsertionSort(data1);
long shellTimes = testShellSort(data2);
// 选择排序
long selectTimes = testStraightSelectionSort(data3);
long heapTimes = testHeapSort(data4);
// 交换排序
long bubbleTimes = testBubbleSort(data5);
long quickTimes = testQuickSort(data6);
// 归并排序
long mergeTimes = testMergeSort(data7);
// 基数排序
long radixTimes = testRadixSort(data8);

System.out.println("method \ttime(ms)");
System.out.println("InsertionSort\t" + insertTimes);
System.out.println("ShellSort \t" + shellTimes);
System.out.println("SelectionSort\t" + selectTimes);
System.out.println("HeapSort \t" + heapTimes);
System.out.println("BubbleSort \t" + bubbleTimes);
System.out.println("QuickSort \t" + quickTimes);
System.out.println("MergeSort \t" + mergeTimes);
System.out.println("RadixSort \t" + radixTimes);
}
}

/**
*测试时间复杂度为O(n^2)的排序
*/

@Test
public void testBase() {
Scanner scan = new Scanner(System.in);
int num = -1;
int maxValue = -1;
while (true) {
// 从命令行输入元素数量,以及最大值,格式:10,1000,输入quit结束
String input = scan.next();
if ("quit".equals(input)) {
System.exit(1);
}
String[] strs = input.split(",");
num = Integer.parseInt(strs[0]);
maxValue = Integer.parseInt(strs[1]);
System.out.println("Sort Data Num = " + num + ", MaxValue = " + maxValue);

Random ran = new Random();
Integer[] data = new Integer[num];
Integer[] data1 = new Integer[data.length];
Integer[] data2 = new Integer[data.length];
Integer[] data3 = new Integer[data.length];
Integer[] data4 = new Integer[data.length];
for (int i = 0; i < data.length; i++) {
data[i] = ran.nextInt(maxValue);
data1[i] = data[i];
data2[i] = data[i];
data3[i] = data[i];
data4[i] = data[i];
}
// 插入排序
long insertTimes = testStraightInsertionSort(data1);
long shellTimes = testShellSort(data2);
// 选择排序
long selectTimes = testStraightSelectionSort(data3);
// 交换排序
long bubbleTimes = testBubbleSort(data4);

System.out.println("method \ttime(ms)");
System.out.println("InsertionSort\t" + insertTimes);
System.out.println("ShellSort \t" + shellTimes);
System.out.println("SelectionSort\t" + selectTimes);
System.out.println("BubbleSort \t" + bubbleTimes);
}
}

/**
* 比较O(nlgn)左右的排序算法
*
* 这里把希尔加上是因为虽然希尔时间复杂度是O(n^2)但是从实际结果来看其效率还是较高的,所以拿来跟O(nlgn)一起对比
*/

@Test
public void testGood() {
Scanner scan = new Scanner(System.in);
int num = -1;
int maxValue = -1;
while (true) {
// 从命令行输入元素数量,以及最大值,格式:10,1000,输入quit结束
String input = scan.next();
if ("quit".equals(input)) {
System.exit(1);
}
String[] strs = input.split(",");
num = Integer.parseInt(strs[0]);
maxValue = Integer.parseInt(strs[1]);
System.out.println("Sort Data Num = " + num + ", MaxValue = " + maxValue);

Random ran = new Random();
Integer[] data = new Integer[num];
Integer[] data1 = new Integer[data.length];
Integer[] data2 = new Integer[data.length];
Integer[] data3 = new Integer[data.length];
Integer[] data4 = new Integer[data.length];
Integer[] data5 = new Integer[data.length];
for (int i = 0; i < data.length; i++) {
data[i] = ran.nextInt(maxValue);
data1[i] = data[i];
data2[i] = data[i];
data3[i] = data[i];
data4[i] = data[i];
data5[i] = data[i];
}
// 插入排序
long shellTimes = testShellSort(data1);
// 选择排序
long heapTimes = testHeapSort(data2);
// 交换排序
long quickTimes = testQuickSort(data3);
// 归并排序
long mergeTimes = testMergeSort(data4);
// 基数排序
long radixTimes = testRadixSort(data5);

System.out.println("method \ttime(ms)");
System.out.println("ShellSort \t" + shellTimes);
System.out.println("HeapSort \t" + heapTimes);
System.out.println("QuickSort \t" + quickTimes);
System.out.println("MergeSort \t" + mergeTimes);
System.out.println("RadixSort \t" + radixTimes);
}
}

public static <T extends Comparable<T>> long testStraightInsertionSort(T[] data) {
long start = System.nanoTime();
StraightInsertionSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static <T extends Comparable<T>> long testShellSort(T[] data) {
long start = System.nanoTime();
ShellSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static <T extends Comparable<T>> long testStraightSelectionSort(T[] data) {
long start = System.nanoTime();
StraightSelectionSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static <T extends Comparable<T>> long testHeapSort(T[] data) {
long start = System.nanoTime();
HeapSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static <T extends Comparable<T>> long testBubbleSort(T[] data) {
long start = System.nanoTime();
BubbleSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static <T extends Comparable<T>> long testQuickSort(T[] data) {
long start = System.nanoTime();
QuickSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static <T extends Comparable<T>> long testMergeSort(T[] data) {
long start = System.nanoTime();
MergeSort.sort(data);
return (System.nanoTime() - start) / 1000;
}

public static long testRadixSort(Integer[] data) {
long start = System.nanoTime();
RadixSort.sort(data);
return (System.nanoTime() - start) / 1000;
}
}

运行时需要指定JVM运行参数:-Xms1024m -Xmx1024m -Xss2048k
以上测试可能会有偏差,