概述
上一篇文章分析了一下基本的排序算法以及Java的實(shí)現(xiàn)院促，不過沒有比較深入的去分析醋虏，因?yàn)閷?duì)于O(n^2)的算法實(shí)現(xiàn)比較簡單，但是對(duì)于O(nLogn)的算法本身有些復(fù)雜谭胚，所以就分為兩篇文章來寫徐块。評(píng)價(jià)算法的標(biāo)準(zhǔn)有很多，時(shí)間復(fù)雜度灾而，空間復(fù)雜度以及穩(wěn)定性等等胡控。下面從兩個(gè)方面來對(duì)經(jīng)典排序算法進(jìn)行總結(jié)一下：
正文
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度分類
經(jīng)典排序算法的時(shí)間復(fù)雜度大致可以分為以上兩種，下面來通過一個(gè)表格來看一下：
| 對(duì)比 | O(n^2) | O(nLogn) | 快的倍數(shù) |
|---|---|---|---|
| n = 10 | 100 | 100 | 3 |
| n=100 | 10000 | 664 | 15 |
| n=1000 | 10^6 | 9966 | 100 |
| n=10000 | 10^8 | 132877 | 753 |
| n=100000 | 10^10 | 1660964 | 6020 |
當(dāng)數(shù)據(jù)量比較小的時(shí)候旁趟，O(nLogn)的優(yōu)勢并不明顯昼激，當(dāng)數(shù)據(jù)量越來越大的時(shí)候，優(yōu)勢才更加明顯
先寫一個(gè)測試的通用的工具類SortUtils
public class SortUtils {
// 生成有n個(gè)范圍在[rangeL, rangeR]的數(shù)組
static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
assert rangeL <= rangeR;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = (int) (Math.random() * (rangeR - rangeL + 1) + rangeL);
return arr;
}
// 生成一個(gè)有序數(shù)組, 之后隨機(jī)交換swapTimes對(duì)
static Integer[] generateOrderedArray(int n, int swapTimes) {
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = i;
for (int i = 0; i < swapTimes; i++) {
int a = (int) (Math.random() * n);
int b = (int) (Math.random() * n);
int t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
return arr;
}
}
通過反射測試排序算法：
// 通過反射獲取調(diào)用相應(yīng)的方法
static void testSort(String sortClassName, Comparable[] arr) {
// 通過Java的反射機(jī)制锡搜，通過排序的類名橙困，運(yùn)行排序函數(shù)
try {
// 通過sortClassName獲得排序函數(shù)的Class對(duì)象
Class sortClass = Class.forName(sortClassName);
// 通過排序函數(shù)的Class對(duì)象獲得排序方法
Method sortMethod = sortClass.getMethod("sort", new Class[]{Comparable[].class});
// 排序參數(shù)只有一個(gè)，是可比較數(shù)組arr
Object[] params = new Object[]{arr};
long startTime = System.currentTimeMillis();
// 調(diào)用排序函數(shù)
sortMethod.invoke(null, params);
long endTime = System.currentTimeMillis();
System.out.println(sortClass.getSimpleName() + " : " + (endTime - startTime) + "ms");
} catch (Exception e) {
e.printStackTrace();
}
}
O(n^2)排序算法
編寫測試方法
Integer[] arr1 = SortUtils.generateRandomArray(N, 0, 20000);
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
SortUtils.testSlow("com.wustor.slow.SelectionSort", arr1);
SortUtils.testSlow("com.wustor.slow.InsertionSort", arr2);
SortUtils.testSlow("com.wustor.slow.BubbleSort", arr3);
SortUtils.testSlow("com.wustor.ShellSort", arr4);
測試隨機(jī)數(shù)據(jù)
500條數(shù)據(jù)：
SelectionSort : 7ms
InsertionSort : 14ms
BubbleSort : 14ms
ShellSort : 0ms
1000條數(shù)據(jù)：
SelectionSort : 18ms
InsertionSort : 16ms
BubbleSort : 24ms
ShellSort : 1ms
5000條數(shù)據(jù)：
SelectionSort : 75ms
InsertionSort : 164ms
BubbleSort : 195ms
ShellSort : 9ms
20000條數(shù)據(jù)：
SelectionSort : 1265ms
InsertionSort : 1361ms
BubbleSort : 2999ms
ShellSort : 22ms
總結(jié)一下
| 隨機(jī)數(shù)據(jù) | 500條 | 1000條 | 5000條 | 20000條 |
|---|---|---|---|---|
| SelectionSort | 7ms | 18ms | 75ms | 1265ms |
| InsertionSort | 14ms | 16ms | 164ms | 1361ms |
| BubbleSort | 14ms | 24ms | 195ms | 2999ms |
| ShellSort | 0ms | 1ms | 9ms | 22ms |
測試有序數(shù)據(jù)
500條數(shù)據(jù)：
SelectionSort : 11ms
InsertionSort : 2ms
BubbleSort : 1ms
ShellSort : 3ms
1000條數(shù)據(jù)：
SelectionSort : 6ms
InsertionSort : 10ms
BubbleSort : 10ms
ShellSort : 1ms
5000條數(shù)據(jù)：
SelectionSort : 98ms
InsertionSort : 8ms
BubbleSort : 82ms
ShellSort : 3ms
20000條數(shù)據(jù)：
SelectionSort : 624ms
InsertionSort : 28ms
BubbleSort : 991ms
ShellSort : 20ms
總結(jié)一下
| 有序數(shù)據(jù) | 500條 | 1000條 | 5000條 | 20000條 |
|---|---|---|---|---|
| SelectionSort | 11ms | 6ms | 98ms | 624ms |
| InsertionSort | 2ms | 10ms | 8ms | 28ms |
| BubbleSort | 1ms | 24ms | 82ms | 991ms |
| ShellSort | 3ms | 1ms | 3ms | 20ms |
通過對(duì)比可以發(fā)現(xiàn)耕餐，不管是測試有序還是無序的數(shù)據(jù)纷宇，希爾排序都是效率最高的。
O(nlogn)排序算法
編寫測試方法
public static void main(String[] args) {
int T = 1000000;
int N = 20000;
// 比較 HeapSort蛾方、Shell Sort 和 Merge Sort 和 三種 Quick Sort 的性能效率
Integer[] arr1 = SortUtils.generateRandomArray(T, 0, N);
// Integer[] arr1 = SortUtils.generateOrderedArray(T, N);
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
long time1 = SortUtils.testFast("com.wustor.ShellSort", arr1);
long time2 = SortUtils.testFast("com.wustor.fast.HeapSort", arr2);
long time3 = SortUtils.testFast("com.wustor.fast.MergeSort", arr3);
long time4 = SortUtils.testFast("com.wustor.fast.QuickSort", arr4);
System.out.println("Sorting " + N + " elements " + T + " times. Calculate theRun Time.");
System.out.println("Shell Sort Run Time: " + time1 + " ms");
System.out.println("Heap Sort Run Time: " + time2 + " ms");
System.out.println("Merge Sort Run Time: " + time3 + " ms");
System.out.println("Quick Sort Run Time: " + time4 + " ms");
}
測試隨機(jī)數(shù)據(jù)
因?yàn)橹挥袛?shù)據(jù)量涉及到幾十萬甚至上百萬的時(shí)候，才能體體現(xiàn)出O(nlogn)的優(yōu)勢
10000條數(shù)據(jù)：
Shell Sort Run Time: 0 ms
Heap Sort Run Time: 0 ms
Merge Sort Run Time: 93 ms
Quick Sort Run Time: 0 ms
20000條數(shù)據(jù)：
Shell Sort Run Time: 16 ms
Heap Sort Run Time: 15 ms
Merge Sort Run Time: 0 ms
Quick Sort Run Time: 0 ms
100000條數(shù)據(jù)：
Shell Sort Run Time: 75 ms
Heap Sort Run Time: 44 ms
Merge Sort Run Time: 110 ms
Quick Sort Run Time: 62 ms
1000000條數(shù)據(jù)：
Shell Sort Run Time: 1062 ms
Heap Sort Run Time: 734 ms
Merge Sort Run Time: 281 ms
Quick Sort Run Time: 282 ms
測試隨機(jī)數(shù)據(jù)
| 隨機(jī)數(shù)據(jù) | 10000條 | 20000條 | 100000條 | 1000000條 |
|---|---|---|---|---|
| Shell Sort | 0ms | 16ms | 75ms | 1062ms |
| Heap Sort | 0ms | 15ms | 44ms | 734ms |
| Merge Sort | 93ms | 0ms | 110ms | 281ms |
| Quick Sort | 0ms | 0ms | 62ms | 282ms |
測試有序數(shù)據(jù)
10000條數(shù)據(jù)：
Shell Sort Run Time: 0 ms
Heap Sort Run Time: 0 ms
Merge Sort Run Time: 16 ms
Quick Sort Run Time: 0 ms
20000條數(shù)據(jù)：
Shell Sort Run Time: 16 ms
Heap Sort Run Time: 0 ms
Merge Sort Run Time: 15 ms
Quick Sort Run Time: 16 ms
100000條數(shù)據(jù)：
Shell Sort Run Time: 77 ms
Heap Sort Run Time: 52 ms
Merge Sort Run Time: 62 ms
Quick Sort Run Time: 31 ms
1000000條數(shù)據(jù)：
Shell Sort Run Time: 1086 ms
Heap Sort Run Time: 606 ms
Merge Sort Run Time: 302 ms
Quick Sort Run Time: 257 ms
測試有序數(shù)據(jù)
| 有序數(shù)據(jù) | 10000條 | 20000條 | 100000條 | 1000000條 |
|---|---|---|---|---|
| Shell Sort | 0ms | 16ms | 77ms | 1086ms |
| Heap Sort | 0ms | 0ms | 52ms | 606ms |
| Merge Sort | 16ms | 15ms | 62ms | 302ms |
| Quick Sort | 0ms | 16ms | 31ms | 282ms |
對(duì)比分析上陕，發(fā)現(xiàn)快排不管是對(duì)于有序的還是無序的數(shù)組桩砰，排序效率都比較高。
穩(wěn)定性
定義：假定在待排序的記錄序列中释簿，存在多個(gè)具有相同的關(guān)鍵字的記錄亚隅，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變庶溶，即在原序列中煮纵，ri=rj懂鸵，且ri在rj之前，而在排序后的序列中行疏，ri仍在rj之前匆光，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的酿联。
根據(jù)這個(gè)定義來分析一下經(jīng)典排序算法：
- 簡單選擇排序：由于需要交換元素的位置终息，所以有可能會(huì)破壞原來的順序，比如說7571贞让，第一次交換之后周崭，兩個(gè)7之間的順序就調(diào)換了。不穩(wěn)定
- 堆排序：在數(shù)據(jù)結(jié)構(gòu)分析之二叉樹中分析過二叉堆的數(shù)據(jù)結(jié)構(gòu)喳张，在堆排序之前需要將數(shù)組是生成一個(gè)二差堆续镇，如果給定的二叉堆是數(shù)組是37556，那么進(jìn)行生成二叉堆的時(shí)候?qū)哟伪闅v是35756销部，兩個(gè)5相對(duì)順序不變摸航，但是取出最小值的時(shí)候，底部的元素進(jìn)行上濾操作柴墩，后面的5會(huì)置頂忙厌，相對(duì)順序被破壞。不穩(wěn)定
- 直接插入排序：只有當(dāng)后面的元素大于前面的元素的時(shí)候才會(huì)進(jìn)行交換江咳，所以不會(huì)破壞相同元素的順序逢净。穩(wěn)定
- 希爾排序：分組的插入排序，雖然插入排序都是穩(wěn)定的歼指，但是每列之間的元素在排序之間會(huì)相互移動(dòng)爹土，這樣就有可能導(dǎo)致相同元素之間的位置發(fā)生變化。不穩(wěn)定
- 冒泡排序：第一個(gè)比第二個(gè)大踩身，才進(jìn)行交換胀茵，所以元素相同的元素之間不會(huì)進(jìn)行交換，相對(duì)位置也就不會(huì)發(fā)生變化挟阻。穩(wěn)定
- 快速排序：在分組的時(shí)候很容易把兩個(gè)元素相同的位置進(jìn)行交換琼娘，對(duì)于6225，分組的時(shí)候22之間的順序會(huì)被打亂附鸽。不穩(wěn)定
- 歸并排序：分組進(jìn)行遞歸脱拼，遞歸到最后，每一個(gè)數(shù)組都是有序的坷备，合并的時(shí)候熄浓，也是從左到右的，相同的元素不會(huì)進(jìn)行交換省撑，所以可以保證穩(wěn)定性赌蔑。穩(wěn)定
下面用圖片總結(jié)一下
算法穩(wěn)定性分類
對(duì)比
| 算法 | 最大時(shí)間 | 平均時(shí)間 | 最小時(shí)間 | 輔助空間 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 穩(wěn)定 |
| 冒泡排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 希爾排序 | O(n^(3/2)) | O(n^(3/2)) | O(n^(3/2)) | O(1) | 不穩(wěn)定 |
| 快速排序 | O(n^2) | O(nlogn) | O(nlogn) | O(logn) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
排序方法的選擇
數(shù)據(jù)較小
有序
可采用直接插入排序俯在。因?yàn)椴迦肱判蛐蚀藭r(shí)效率最高。
無序
采用直接插入排序或者直接選擇排序
數(shù)據(jù)較大
快速排序在完全有序的情況下娃惯，會(huì)退化到O(n^2)級(jí)別跷乐，效率較低
有序
則應(yīng)采用時(shí)間復(fù)雜度為 O(nLogn)的排序方法：堆排序或歸并排序
無序
則應(yīng)采用時(shí)間復(fù)雜度為 O(nLogn)的排序方法：快速排序、堆排序或歸并排序
以上選擇是在對(duì)排序算法穩(wěn)定性沒有要求的情況下進(jìn)行選擇的石景，如果需要排序穩(wěn)定劈猿，則需要剔除不穩(wěn)定的算法，在排序穩(wěn)定的算法里面進(jìn)行選擇即可潮孽。
