概述
上一篇文章分析了一下基本的排序算法以及Java的实现，不过没有比较深入的去分析，因为对于O(n^2)的算法实现比较简单，但是对于O(nLogn)的算法本身有些复杂，所以就分为两篇文章来写。评价算法的标准有很多，时间复杂度，空间复杂度以及稳定性等等。下面从两个方面来对经典排序算法进行总结一下：
正文
时间复杂度
时间复杂度分类
经典排序算法的时间复杂度大致可以分为以上两种，下面来通过一个表格来看一下：
| 对比 | O(n^2) | O(nLogn) | 快的倍数 |
|---|---|---|---|
| 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 |
当数据量比较小的时候，O(nLogn)的优势并不明显，当数据量越来越大的时候，优势才更加明显
先写一个测试的通用的工具类SortUtils
public class SortUtils {
// 生成有n个范围在[rangeL, rangeR]的数组
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;
}
// 生成一个有序数组, 之后随机交换swapTimes对
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;
}
}
通过反射测试排序算法：
// 通过反射获取调用相应的方法
static void testSort(String sortClassName, Comparable[] arr) {
// 通过Java的反射机制，通过排序的类名，运行排序函数
try {
// 通过sortClassName获得排序函数的Class对象
Class sortClass = Class.forName(sortClassName);
// 通过排序函数的Class对象获得排序方法
Method sortMethod = sortClass.getMethod("sort", new Class[]{Comparable[].class});
// 排序参数只有一个，是可比较数组arr
Object[] params = new Object[]{arr};
long startTime = System.currentTimeMillis();
// 调用排序函数
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);
测试随机数据
500条数据：
SelectionSort : 7ms
InsertionSort : 14ms
BubbleSort : 14ms
ShellSort : 0ms
1000条数据：
SelectionSort : 18ms
InsertionSort : 16ms
BubbleSort : 24ms
ShellSort : 1ms
5000条数据：
SelectionSort : 75ms
InsertionSort : 164ms
BubbleSort : 195ms
ShellSort : 9ms
20000条数据：
SelectionSort : 1265ms
InsertionSort : 1361ms
BubbleSort : 2999ms
ShellSort : 22ms
总结一下
| 随机数据 | 500条 | 1000条 | 5000条 | 20000条 |
|---|---|---|---|---|
| SelectionSort | 7ms | 18ms | 75ms | 1265ms |
| InsertionSort | 14ms | 16ms | 164ms | 1361ms |
| BubbleSort | 14ms | 24ms | 195ms | 2999ms |
| ShellSort | 0ms | 1ms | 9ms | 22ms |
测试有序数据
500条数据：
SelectionSort : 11ms
InsertionSort : 2ms
BubbleSort : 1ms
ShellSort : 3ms
1000条数据：
SelectionSort : 6ms
InsertionSort : 10ms
BubbleSort : 10ms
ShellSort : 1ms
5000条数据：
SelectionSort : 98ms
InsertionSort : 8ms
BubbleSort : 82ms
ShellSort : 3ms
20000条数据：
SelectionSort : 624ms
InsertionSort : 28ms
BubbleSort : 991ms
ShellSort : 20ms
总结一下
| 有序数据 | 500条 | 1000条 | 5000条 | 20000条 |
|---|---|---|---|---|
| SelectionSort | 11ms | 6ms | 98ms | 624ms |
| InsertionSort | 2ms | 10ms | 8ms | 28ms |
| BubbleSort | 1ms | 24ms | 82ms | 991ms |
| ShellSort | 3ms | 1ms | 3ms | 20ms |
通过对比可以发现，不管是测试有序还是无序的数据，希尔排序都是效率最高的。
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");
}
测试随机数据
因为只有数据量涉及到几十万甚至上百万的时候，才能体体现出O(nlogn)的优势
10000条数据：
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条数据：
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条数据：
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条数据：
Shell Sort Run Time: 1062 ms
Heap Sort Run Time: 734 ms
Merge Sort Run Time: 281 ms
Quick Sort Run Time: 282 ms
测试随机数据
| 随机数据 | 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 |
测试有序数据
10000条数据：
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条数据：
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条数据：
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条数据：
Shell Sort Run Time: 1086 ms
Heap Sort Run Time: 606 ms
Merge Sort Run Time: 302 ms
Quick Sort Run Time: 257 ms
测试有序数据
| 有序数据 | 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 |
对比分析，发现快排不管是对于有序的还是无序的数组，排序效率都比较高。
稳定性
定义：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
根据这个定义来分析一下经典排序算法：
- 简单选择排序：由于需要交换元素的位置，所以有可能会破坏原来的顺序，比如说7571，第一次交换之后，两个7之间的顺序就调换了。不稳定
- 堆排序：在数据结构分析之二叉树中分析过二叉堆的数据结构，在堆排序之前需要将数组是生成一个二差堆，如果给定的二叉堆是数组是37556，那么进行生成二叉堆的时候层次遍历是35756，两个5相对顺序不变，但是取出最小值的时候，底部的元素进行上滤操作，后面的5会置顶，相对顺序被破坏。不稳定
- 直接插入排序：只有当后面的元素大于前面的元素的时候才会进行交换，所以不会破坏相同元素的顺序。稳定
- 希尔排序：分组的插入排序，虽然插入排序都是稳定的，但是每列之间的元素在排序之间会相互移动，这样就有可能导致相同元素之间的位置发生变化。不稳定
- 冒泡排序：第一个比第二个大，才进行交换，所以元素相同的元素之间不会进行交换，相对位置也就不会发生变化。稳定
- 快速排序：在分组的时候很容易把两个元素相同的位置进行交换，对于6225，分组的时候22之间的顺序会被打乱。不稳定
- 归并排序：分组进行递归，递归到最后，每一个数组都是有序的，合并的时候，也是从左到右的，相同的元素不会进行交换，所以可以保证稳定性。稳定
下面用图片总结一下
算法稳定性分类
对比
| 算法 | 最大时间 | 平均时间 | 最小时间 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 冒泡排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n^(3/2)) | O(n^(3/2)) | O(n^(3/2)) | O(1) | 不稳定 |
| 快速排序 | O(n^2) | O(nlogn) | O(nlogn) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
排序方法的选择
数据较小
有序
可采用直接插入排序。因为插入排序效率此时效率最高。
无序
采用直接插入排序或者直接选择排序
数据较大
快速排序在完全有序的情况下，会退化到O(n^2)级别，效率较低
有序
则应采用时间复杂度为 O(nLogn)的排序方法：堆排序或归并排序
无序
则应采用时间复杂度为 O(nLogn)的排序方法：快速排序、堆排序或归并排序
以上选择是在对排序算法稳定性没有要求的情况下进行选择的，如果需要排序稳定，则需要剔除不稳定的算法，在排序稳定的算法里面进行选择即可。
