前言

本文主要使用java实现选择排序，插入排序，冒泡排序，希尔排序，快速排序，归并排序，并对这些算法进行的性能的测试，从中窥探出各个算法的优劣，从而有助于在今后结合应用场景能够选择合适的排序算法。

选择排序

算法

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

代码实现

public static void selectionSort(int[] data) { for (int i = 0; i < data.length; i++) { int k = i; for (int j = i + 1; j < data.length; j++) { if (data[k] > data[j]) { k = j; } } if (i != k) { int t = data[i]; data[i] = data[k]; data[k] = t; } } }

冒泡排序

算法

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

代码实现

public static void bubbleSort(int[] data) { for (int i = 0; i < data.length - 1; i++) { for (int j = 0; j < data.length - 1 - i; j++) { if (data[j] > data[j + 1]) { int t = data[j]; data[j] = data[j + 1]; data[j + 1] = t; } } } }

插入排序

算法

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

代码实现

版本一

从前往后找到插入的位置，然后再做移位操作腾出插入的空间，最后将元素插入。

public static void insertSortV1(int[] data) { for (int i = 1; i < data.length; i++) { for (int j = 0; j < i; j++) { if (data[i] < data[j]) { int t = data[i]; for (int k = i - 1; k >= j; k--) { data[k + 1] = data[k]; } data[j] = t; break; } } } }

版本二

从后往前寻找插入的位置，一边寻找一边做移位操作，最后找到位置将元素插入。

public static void insertSortV2(int[] data) { for (int i = 1; i < data.length; i++) { int value = data[i]; int j; for (j = i - 1; j >=0 && data[j] > value; j--) { data[j + 1] = data[j]; } data[j + 1] = value; } }

版本一 VS 版本二

显然，版本二的插入算法实现更加高效，然而，版本一虽然很笨拙，但也是很多人可能想到的一种实现插入排序算法的方法。在此特地突出对比这两种方法，只是为了提醒大家在实现插入排序算法时，要避免采用第一种的现实方法，而采取第二种实现方法。

快速排序

算法

快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。详细可查考快速排序算法

代码实现

public static void quickSort(int[] data, int from, int to) { if (to > from) { int c = from; int left = from; int right = to; boolean flip = true; while (right >= left) { if (flip) { if (data[right] < data[c]) { int t = data[c]; data[c] = data[right]; data[right] = t; c = right; flip = false; } right--; } else { if (data[left] > data[c]) { int t = data[c]; data[c] = data[left]; data[left] = t; c = left; flip = true; } left++; } } quickSort(data, from, c - 1); quickSort(data, c + 1, to); } }

希尔排序

算法

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。 详细可见希尔排序

代码实现

版本一

private static void shellSortV1(int[] data) { for (int step = data.length / 2; step > 0; step = step / 2) { for (int i = 0; i < step; i++) { for (int j = i + step; j < data.length; j = j + step) { int t = data[j]; int k = j - step; while(k > 0 && data[k] > t) { data[k + step] = data[k]; k = k - step; } data[k + step] = t; } } } }

版本二

for (int step = data.length / 2; step > 0; step = step / 2) { for (int i = 0; i < step; i++) {

将上面的两层循环合并成一个循环

public static void shellSortV2(int[] data) { for (int step = data.length / 2; step > 0; step = step / 2) { for (int j = step; j < data.length; j++) { int t = data[j]; int k = j - step; while(k >= 0 && data[k] > t) { data[k + step] = data[k]; k = k - step; } data[k + step] = t; } } }

归并排序

算法

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。详细可见归并排序

代码实现

public static void mergeSort(int[] data, int from, int to) { if (to > from) { int middle = (from + to) / 2; if (from < middle) { mergeSort(data, from, middle); } if (middle + 1 < to) { mergeSort(data, middle + 1, to); } int l = from; int r = middle + 1; if (l < r) { int[] helpArr = new int[to - from + 1]; for (int i = 0; i < helpArr.length; i++) { if (l <= middle && r <= to) { if (data[l] < data[r]) { helpArr[i] = data[l]; l++; } else { helpArr[i] = data[r]; r++; } } else if (l > middle) { helpArr[i] = data[r]; r++; } else if (r > to) { helpArr[i] = data[l]; l++; } } for (int i = 0; i < helpArr.length; i++) { data[from + i] = helpArr[i]; } } } }

性能测试

随机数据测试

准备数据

//生成无序的数据 public static int[] generateNoOrderedData(int n) { Random random = new Random(); int[] data = new int[n]; for(int i=0; i<n; i++) { data[i] = random.nextInt(); } return data; } //生成有序的数据 public static int[] generateTotallyOrderedData(int n) { Random random = new Random(); int[] data = new int[n]; data[0] = random.nextInt(); for (int i = 1; i < n; i++) { data[i] = data[i-1] + 1; } return data; }

测试代码

public static void main(String[] args) { //生成数据 int[] data = generateNoOrderedData(10000); long start; long end; int[] a1 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); selectionSort(a1); end = System.currentTimeMillis(); System.out.println("selectionSort: " + (end - start) + " ms"); int[] a2 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); bubbleSort(a2); end = System.currentTimeMillis(); System.out.println("bubbleSort: " + (end - start) + " ms"); int[] a3 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); insertSortV1(a3); end = System.currentTimeMillis(); System.out.println("insertSortV1: " + (end - start) + " ms"); int[] a32 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); insertSortV2(a32); end = System.currentTimeMillis(); System.out.println("insertSortV2: " + (end - start) + " ms"); int[] a4 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); quickSort(a4, 0, data.length-1); end = System.currentTimeMillis(); System.out.println("quickSort: " + (end - start) + " ms"); int[] a51 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); shellSortV1(a51); end = System.currentTimeMillis(); System.out.println("shellSortV1: " + (end - start) + " ms"); int[] a52 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); shellSortV2(a52); end = System.currentTimeMillis(); System.out.println("shellSortV2: " + (end - start) + " ms"); int[] a6 = Arrays.copyOf(data, data.length); start = System.currentTimeMillis(); mergeSort(a6, 0, data.length - 1); end = System.currentTimeMillis(); System.out.println("mergeSort: " + (end - start) + " ms"); }

无序数据

1万

selectionSort: 49 ms bubbleSort: 167 ms insertSortV1: 39 ms insertSortV2: 18 ms quickSort: 3 ms shellSortV1: 4 ms shellSortV2: 5 ms mergeSort: 3 ms

selectionSort: 48 ms bubbleSort: 170 ms insertSortV1: 43 ms insertSortV2: 18 ms quickSort: 3 ms shellSortV1: 4 ms shellSortV2: 12 ms mergeSort: 13 ms

selectionSort: 48 ms bubbleSort: 157 ms insertSortV1: 40 ms insertSortV2: 20 ms quickSort: 5 ms shellSortV1: 5 ms shellSortV2: 10 ms mergeSort: 4 ms

可看出quickSort，shellSortV1，shellSortV2，mergeSort的要明显快于selectionSort，bubbleSort，insertSortV1，insertSortV2。insertSortV2要明显快于insertSortV1。在所有算法中bubbleSort显然最慢。

10万

selectionSort: 5482 ms bubbleSort: 19889 ms insertSortV1: 2931 ms insertSortV2: 1229 ms quickSort: 24 ms shellSortV1: 27 ms shellSortV2: 23 ms mergeSort: 49 ms

selectionSort: 4933 ms bubbleSort: 18720 ms insertSortV1: 2958 ms insertSortV2: 1138 ms quickSort: 21 ms shellSortV1: 18 ms shellSortV2: 18 ms mergeSort: 43 ms

selectionSort: 5080 ms bubbleSort: 20309 ms insertSortV1: 3155 ms insertSortV2: 1213 ms quickSort: 17 ms shellSortV1: 19 ms shellSortV2: 19 ms mergeSort: 41 ms

可看出quickSort，shellSortV1，shellSortV2，mergeSort的速度大大快于selectionSort，bubbleSort，insertSortV1，insertSortV2。insertSortV2要明显快于insertSortV1，在两倍左右。在所有算法中bubbleSort显然还是最慢。后面随着数据量的加大，selectionSort，bubbleSort，insertSortV1，insertSortV2肯定会变得更慢，我们将不再对它们进行测试，只对quickSort，shellSortV1，shellSortV2，mergeSort进行测试。

100万

quickSort: 199 ms shellSortV1: 283 ms shellSortV2: 268 ms mergeSort: 247 ms

quickSort: 132 ms shellSortV1: 404 ms shellSortV2: 261 ms mergeSort: 265 ms

quickSort: 138 ms shellSortV1: 397 ms shellSortV2: 251 ms mergeSort: 293 ms

quickSort，shellSortV1，shellSortV2，mergeSort依然性能可以接受，在其中quickSort相较其他算法更加快，shellSortV2要比shellSrotV1快一些，mergeSort与shellSortV1较为接近。

1000万

quickSort: 1812 ms shellSortV1: 5903 ms shellSortV2: 3296 ms mergeSort: 2096 ms

quickSort: 1727 ms shellSortV1: 5286 ms shellSortV2: 3362 ms mergeSort: 1902 ms

quickSort: 1747 ms shellSortV1: 5507 ms shellSortV2: 3174 ms mergeSort: 2114 ms

quickSort，shellSortV1，shellSortV2，mergeSort依然性能可以接受，在其中quickSort相较其他算法仍然更加快，shellSortV2可以看出要明显比shellSrotV1快一些，后面我们将不对shellSrotV1进行测试。mergeSort速度在shellSort与quickSort之间，要明显快于shellSort，与quickSort接近。

5000万

quickSort: 9360 ms shellSortV2: 22090 ms mergeSort: 10715 ms

quickSort: 7701 ms shellSortV2: 21014 ms mergeSort: 10672 ms

quickSort: 8582 ms shellSortV2: 21330 ms mergeSort: 10470 ms

可以看出随着数据量的加大，quickSort相较其他算法仍然更加快，mergeSort速度在shellSortV2与quickSort之间，要明显快于shellSortV2，与quickSort接近。shellSortV2最慢。

有序数据

1万

selectionSort: 14 ms bubbleSort: 19 ms insertSortV1: 15 ms insertSortV2: 0 ms quickSort: 36 ms shellSortV1: 4 ms shellSortV2: 2 ms mergeSort: 5 ms

selectionSort: 18 ms bubbleSort: 24 ms insertSortV1: 18 ms insertSortV2: 0 ms quickSort: 42 ms shellSortV1: 3 ms shellSortV2: 7 ms mergeSort: 3 ms

selectionSort: 15 ms bubbleSort: 21 ms insertSortV1: 16 ms insertSortV2: 0 ms quickSort: 39 ms shellSortV1: 4 ms shellSortV2: 2 ms mergeSort: 7 ms

insertSortV2，shellSortV1，shellSortV2，mergeSort要明显快于selectionSort，bubbleSort，insertSortV1，quickSort。在这其中insertSertV2最快，quickSort最慢。

10万

selectionSort: 2088 ms bubbleSort: 1947 ms insertSortV1: 1233 ms insertSortV2: 3 ms Exception in thread “main” java.lang.StackOverflowError at com.company.SortAlgorithm.quickSort(SortAlgorithm.java:147) at com.company.SortAlgorithm.quickSort(SortAlgorithm.java:148) at com.company.SortAlgorithm.quickSort(SortAlgorithm.java:148)

意外发生了quickSort报错了，由于在这有序数据的场景下quickSort递归太深，不适合这样的场景，被KO了。后面，我们将不再加入quickSort。

再测10万

selectionSort: 1616 ms bubbleSort: 1871 ms insertSortV1: 1109 ms insertSortV2: 2 ms shellSortV1: 6 ms shellSortV2: 6 ms mergeSort: 31 ms

selectionSort: 1640 ms bubbleSort: 1804 ms insertSortV1: 1148 ms insertSortV2: 3 ms shellSortV1: 7 ms shellSortV2: 10 ms mergeSort: 35 ms

selectionSort: 1558 ms bubbleSort: 1764 ms insertSortV1: 1092 ms insertSortV2: 2 ms shellSortV1: 6 ms shellSortV2: 7 ms mergeSort: 30 ms

insertSortV2，shellSortV1，shellSortV2，mergeSort要明显快于selectionSort，bubbleSort，insertSortV1。其中insertSort明显最快，bubbleSort最慢。后面将不再测试selectionSort，bubbleSort，insertSortV1。

100万

insertSortV2: 6 ms shellSortV1: 130 ms shellSortV2: 30 ms mergeSort: 156 ms

insertSortV2: 6 ms shellSortV1: 124 ms shellSortV2: 28 ms mergeSort: 145 ms

insertSortV2: 6 ms shellSortV1: 119 ms shellSortV2: 24 ms mergeSort: 127 ms

insertSortV2，shellSortV2明显最快。mergeSort最慢，但是可以接受。

1000万

insertSortV2: 13 ms shellSortV1: 3297 ms shellSortV2: 251 ms mergeSort: 1028 ms

insertSortV2: 17 ms shellSortV1: 3432 ms shellSortV2: 296 ms mergeSort: 1075 ms

insertSortV2: 14 ms shellSortV1: 3108 ms shellSortV2: 268 ms mergeSort: 930 ms

insertSortV2明显最快，shellSortV2次之，mergeSort再次之，shellSortV1最慢，已明显拉开差距，后面我们将不再测试shellSortV1。

5000万

insertSortV2: 67 ms shellSortV2: 1128 ms mergeSort: 5410 ms

insertSortV2: 76 ms shellSortV2: 1119 ms mergeSort: 4901 ms

insertSortV2: 58 ms shellSortV2: 1529 ms mergeSort: 4989 ms

insertSortV2明显最快，shellSortV2次之，mergeSort再次之。

总结

quickSort（快速排序），shellSort（希尔排序)和mergeSort（归并排序）相较于其他算法，性能表现尤为突出，因此我们重点将这三者做一下对比。

quickSort（快速排序）在大多数情况下排序速度都是最快的，但是当数据基本有序或者完全有序时，其性能将会急剧下降。quickSort是建立在二路排序的基础上的，当在数据有序的情况下，其二路排序将退化成了单路，而且递归的深度会等同于元素的数目，最后不仅性能下降，而且会由于递归深度太深，导致堆栈溢出。

shellSort（希尔排序）在大多数情况下其性能并不如quickSort（快速排序）和mergeSort（归并排序），但是在数据基本有序的情况下，shellSort（希尔排序）的性能优势会显现出来。

mergeSort（归并排序）的排序性能比较稳定，处于quickSorkt和shellSort之间，不会出现性能急剧波动。但是，其排序过程中需要借助额外的空间来实现排序，因而相较其它两种排序需要消耗更多的内存空间。

各个算法都有自己的优势和不足，我们必须根据应用场景来做出合适的选择。

而对于同一算法不同的实现也会造成性能表现的差异。

在insertSort（插入排序）中我们实现有版本一和版本二，很显然两者的性能大不相同，显然版本二的性能更好。

在shellSort（希尔排序）中我们实现也有版本一和版本二，很显然两者的性能大不相同，显然版本二的性能更好。

因而，在确定好选择一种算法后，我们也需要进行更好的实现，这样才能到达更加的性能。