排序算法是算法中基础的部分，也是面试中经常被问到的地方。因此，根据对《算法》和《算法导论》关于这部分的学习，做一下总结，以后再遇到排序方面的问题就可以直接看一下博文就行了（文中算法用java实现）。

选择排序
插入排序
希尔排序
冒泡排序
归并排序
快速排序
堆排序
计数排序
基数排序
桶排序

性能评估指标

运行时间：排序的成本模型：在研究排序算法时，需要计算比较和交换的数量，对于不交换元素的算法，我们会计算访问数组的次数。
额外的内存使用：排序算法分为两种：除了函数调用的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间存储另一份数组副本的其他排序算法。

代码中使用基本方法的实现如下：

public static boolean less(Comparable v, Comparable w){
    return v.compareTo(w) < 0;
}

public static void exch(Comparable[] a, int i, int j){
    Comparable tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

public static void show(Comparable[] a){
    for(int i = 0; i < a.length; i++)
        System.out.print(a[i] + " ")
    System.out.println();
}

//默认按升序排列
public static boolean isSorted(Comparable[] a){
    for(int i = 1; i < a.length; i++){
        if(less(a[i],a[i-1]))
            return false;
        return true;
    }
}

选择排序

原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

步骤

先找到数组中最小的那个元素；
将它和数组中第一个元素交换位置（如果第一个元素是自己，和自己交换）；
在剩下的数组中找到最小的元素，将它和第二个元素交换位置，以此类推。

实现

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i + 1; j < N; j++) {
            if (less(a[j], a[min]))
                min = j;
        }
        exch(a, i, min);
    }
}

完整代码参考Selection.java

排序效果如下图所示（原图来自维基百科之选择排序）

selection_sort

性能分析

复杂度分析：
1. 对于长度为$N$的数组，选择排序需要大约$\frac{N^2}{2}$次比较和$N$次交换；
2. 最好的情况：已经有序，交换$0$次；
3. 最坏的情况：逆序，交换$N-1$次。
特点：
1. 运行时间与输入无关，即使对于一个有序数组，依然需要扫描全部元素而且运行时间与随机数组一样；
2. 数据移动是最少的。交换次数与数组大小成线性关系。

插入排序

原理

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果被扫描的元素（已排序）大于新元素，将该元素后移一位；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

实现

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j > 0; j--) {
            if(less(a[j], a[j - 1]))
                exch(a, j, j - 1);
        }
    }
}

完整代码参考Insertion.java

排序效果如下图所示（原图来自维基百科之插入排序）

Insertion_sort

性能分析

复杂度分析：
1. 平均来说，插入排序的复杂度为$O(n^2)$;
2. 最好的情况：已经有序，只需要比较操作$N-1$次即可；
3. 最坏的情况：逆序，需要比较$\frac{N*(N-1)}{2}$次。
特点：
1. 插入排序很适合部分有序的数组和规模较小的数组；
2. 插入排序不适合对于数据量比较大的排序应用.

希尔排序

原理

也称为递减增量排序算法，它是对插入排序的一种快速算法，插入排序相当于$h=1$的情况。（希尔排序的思想是使数组中任意间隔为h的元素都是有序的）

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

步骤

算法最重要的部分是步长，当步长为1时就是插入排序。

最开始以一定的步长进行排序；
然后会继续以一定步长进行排序；
最终算法以步长为1进行排序。

当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

步长的设置，影响着希尔排序算法的复杂度，具体可参考维基百科之希尔排序，这里给出一个步长序列与复杂度的关系表：

shell

实现

public static void sort(Comparable[] a) {
    int N = a.length;
    int h = 1;
    while (h < N / 3)
        h = 3 * h + 1;
    while (h >= 1) {
        for (int i = h; i < N; i++) {
            for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                exch(a, j, j - h);
            }
        }
        h = h / 3;
    }
}

完整代码参考Shell.java

排序效果如下图所示（原图来自维基百科之希尔排序）

shellsort

性能分析

复杂度分析：参见上表
特点：
1. 排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。

冒泡排序

原理

冒泡排序是一种简单的排序算法。它每次去从开始去比较两个元素，如果顺序错误就交换过来，当比较到最后一个元素时，就会把最小（最大）的元素找出来；然后在重复比较，前面已经找到的就不再参与比较。元素越小（大）的元素会经过交换慢慢“浮”到数列顶端。

步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实现

public static void sort(Comparable[] a) {
    int N=a.length-1;
    while(N>0){
        for(int i=1;i<=N;i++){
            if(less(a[i],a[i-1]))
                exch(a,i,i-1);
        }
        N--;
    }
}

完整代码参考Bubble.java

排序效果如下图所示（原图来自维基百科之插入排序）

Bubble_sort

归并排序

原地归并排序

介绍

对两个有序数组进行归并。

步骤

原地归并排序主要是对于有序数组而言，这里只需要额外申请一段数据空间，来进行合并数组即可（迭代法）。

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤3直到某一指针到达序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

实现

//迭代法(第一个有序数组为lo~mid，第二个有序数组为mid+1~hi)
public static void merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo;
    int j = mid + 1;
    Comparable[] aux = new Comparable[a.length];
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];
    for (int k = lo; k <= hi; k++) {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (less(aux[j], aux[i]))
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

自顶向下

原理

首先要知道原地归并排序算法，这个是将两个有序的数组归并到一个数组中，然后使用递归算法，每次都对对并一半的数据（直到把数据间隔减少到1为止，从上往下切分）进行归并排序，这样就是递归地调用归并排序。

步骤

将序列分成两部分，然后对部分分别进行归并；
再将这部分分成两部分进行归并；
重复步骤2，直到把每部分分成为大小为1的数组。

实现

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo)
        return;
    int mid = lo + (hi - lo) / 2;
    sort(a, lo, mid);
    sort(a, mid + 1, hi);
    merge(a, lo, mid, hi);// 归并两个有序数组
}

性能分析

对于长度为N的任意数组，自顶向下的归并排序需要$\frac{N\lg{N}}{2} $至$N\lg{N}$次比较；
对于长度为N的任意数组，自顶向下的归并排序最多需要访问数组$6NlgN$次。

缺点：其辅助数组所使用的额外空间和N的大小成正比。

自低向上

原理

从最下面的长度为1数组开始往上进行合并，直到最后数组变成两个有序数组，再进行最后依次合并。

步骤

将序列每相邻两个数字进行归并操作，形成$ \lfloor\frac{n}{2}\rfloor$个序列，排序后每个序列包含两个元素；
将上述序列再次归并，形成$\lfloor\frac{n}{4}\rfloor$个序列，每个序列包含四个元素；
重复步骤2，直到所有元素排序完毕。

实现

public static void sortBU(Comparable[] a) {
    int N = a.length;
    for (int sz = 1; sz < N; sz = sz + sz) {
        for (int lo = 0; lo < N - sz; lo += sz + sz)
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }
}

性能分析

对于长度为N的任意数组，自低向上的归并排序需要$\frac{N\lg{N}}{2}$至$N\lg{N}$次比较，最多需要访问数组$6N\lg{N}$次。
与自顶向下是相同的，只是顺序不同而已。

快速排序

原理

分治思想，将数组分成两个子数组，独自进行排序。最简单的递归切分：指针i从数组的最左端开始扫描直到找到一个大于等于它的元素，指针j从数组的最右端开始扫描直到找到一个小于等于它的元素，然后交换它们的位置，直到指针相遇。

注意：

终止循环：一个常见的错误就是没有考虑到数组中可能包含和切分元素的值相同的其他元素。

步骤

选择一个基准元素,通常选择第一个元素或者最后一个元素;
通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大;
此时基准元素在其排好序后的正确位置;
然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

实现

public static void sort(Comparable[] a, int low, int high) {
    int l = low;
    int h = high;
    Comparable key = a[l];
    while (l < h) {
        while (l < h && less(key, a[h]))
            h--;
        if (l < h) {
            exch(a, l, h);
            l++;
        }

        while (l < h && less(a[l], key))
            l++;
        if (l < h) {
            exch(a, l, h);
            h--;
        }
    }
    if (l > low)
        sort(a, low, l - 1);
    if (h < high)
        sort(a, l + 1, high);
}

完整代码参考Quick.java

排序效果如下图所示（原图来自维基百科之快速排序）

quick_sort

性能分析

快速排序的内循环会用一个递增的索引将数组元素和一个定值进行比较，其他的几种排序还需要再内循环中移动元素；
它的比较次数较少；
排序的效率取决于切分的效果，而不是切分元素的值，最好的效果是每次都能将数组对半分，在切分不平衡时，程序就会变得比较低效；
对于长度为N的无重复数组排序，快速排序平均需要～$2N\ln{N}$次比较（以及$\frac{1}{6}$次交换）；
快速排序最多需要约$\frac{n^2}{2}$次比较，随机打乱数组可以预防这种情况（当切分时，每次两个子数组之一为空才会出现这种情况）；
三向切分：主要对于有大量元素相等的情况。

快排算法改进

小数组时（$h_i<lo+M$），切换到插入排序。对于小数组，快排比插入排序要慢；
三取样切分。使用子数组的一小部分的中位数来切分数组，这样做得到切分效果更好，但是代价是需要计算中位数；
三向切分，主要是对于有重复元素的情况下，将数组切分为三部分，分别是小于，等于和大于切分元素的数组元素。

堆排序

原理

先构造一个最大堆（最小堆），然后将根节点的最大值（最小值）与最后一位交换，再对第一位进行下沉（上浮）操作，依次类推（下次与倒数第二位进行交换），最后得到的数组即为有序数组。

最大堆的特点：

一棵大小为$N$的完全二叉树的高度为不小于的$\lg{N}$最小整数；
当一棵二叉树的每个节点都大于等于它的两个子节点时，被称为堆有序；
根节点是最大的节点；
对于节点$i$，左移一位算出$2i$节点（即为左子节点），左移一位并在低位加1得到$2i+1$节点（右子节点），右移一位得到$\lfloor\frac{i}{2}\rfloor$（父节点）。

实现

public static void sort(Comparable[] pq) {
		int N = pq.length;
		for (int k = N / 2; k >= 1; k--)
			sink(pq, k, N);
		while (N > 1) {
			exch(pq, 1, N);
			N--;
			sink(pq, 1, N);
		}
	}

	public static void sink(Comparable[] pq, int k, int N) {
		while (2 * k <= N) {
			int j = 2 * k;
			if (j + 1 <= N) {
				if (j < N && less(pq, j, j + 1))
					j++;
			}
			if (!less(pq, k, j))
				break;
			exch(pq, k, j);
			k = j;
		}
	}

	public static void exch(Comparable[] pq, int i, int j) {
		Comparable swap = pq[i - 1];
		pq[i - 1] = pq[j - 1];
		pq[j - 1] = swap;
	}

	public static boolean less(Comparable[] pq, int i, int j) {
		return pq[i - 1].compareTo(pq[j - 1]) < 0;
	}

完整代码参考Heap.java

排序效果如下图所示（原图来自维基百科之快速排序）

heap_sort

性能分析

复杂度分析：
1. 构造堆的时间复杂度为$O(n)$；
2. 堆排序的时间复杂度为$O(n\lg{n})$;
特点：
1. 排序算法使用的是最大堆，最小堆通常用于优先队列（当然也可以反过来）；
2. 将一个数组构造为一个最大堆时，使用递归循环通过下沉（sink方法）将所有有子节点的父节点下沉到给定位置，它的时间复杂度为O(n)；
3. 最大优先队列的一个典型应用就是共享计算机系统中的作业调度。

计数排序

原理

对于每个输入元素x，确定小于x的元素个数，利用这个信息可以直接把x放在输出数组中的位置上了。

步骤

参考CountingSort，其步骤为：

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项；
对所有的计数累加（从$C$中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第$C(i)$项，每放一个元素就将$C(i)$减去1。

实现

public static int[] sort(int[] a) {
	int[] b = new int[a.length];
	int min = a[0];
	int max = a[0];
	for (int i : a) {
		if (i > max)
			max = i;
		if (i < min)
			min = i;
	}
	int size = max - min + 1;
	int[] c = new int[size];
	for (int i = 0; i < a.length; i++) {
		c[a[i] - min]++;
	}
	for (int i = 1; i < c.length; i++) {
		c[i] = c[i] + c[i - 1];
	}
	for (int i = a.length - 1; i >= 0; i--) {
		b[--c[a[i] - min]] = a[i];
	}
	return b;
}

完整代码参考CountingSort.java

性能分析

复杂度分析：
1. 时间复杂度为O(k+n).
特点：
1. 用运算确定次序，而非比较来确定；
2. 稳定：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序是相同的。

基数排序（Radix Sort）

将整数按位数切割成不同的数字，然后按每个位数分别比较。

原理

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序直到最高位排序完成以后，数列就变成了一个有序序列。

步骤

对于$n$个$d$位数，每个数位有k个可能的取值（比如十进制数每位有10个可能的取值）。

先按最低位对数进行排序（可以是计数排序）；
再次低位进行排序
重复第2步，直到最后一步按照最高位进行排序。

从最低位开始排序，保证排序算法的稳定性（如果遇到该位数值相同的话，就按输入顺序）。可以参考百度百科之基数排序中例子。

实现

public static void sort(int[] a, int d) {// d最大值多少位
	int index = 0;
	int m = 1;
	int n = 1;
	int[][] tmp = new int[10][a.length];
	int[] num = new int[10];
	while (m <= d) {
		for (int i : a) {
			int lsd = (i / n) % 10;
			tmp[lsd][num[lsd]] = i;
			num[lsd]++;
		}
		for (int i = 0; i < 10; i++) {
			if (num[i] != 0) {
				for (int j = 0; j < num[i]; j++) {
					a[index] = tmp[i][j];
					index++;
				}
				num[i] = 0;
			}
		}
		n *= 10;
		index = 0;
		m++;
	}
}

完整代码参考RadixSort.java

性能分析

复杂度分析：
1. 使用稳定排序方法耗时$O(k+n)$，那么就可以在$O(d*(k+n))$时间内将这些数排好序。
特点：
1. 基数排序利用的计数排序不是原址排序，而快排是原址排序。

桶排序

也即是箱排序。

原理

将数组分到有限数量的桶子里。每个桶子再个别排序。

步骤

设置一个合适数量的数组作为空桶子；
寻访序列，并且把项目一个一个放到对应的桶子里；
对每个不是空桶子进行排序；
从不是空的桶子里把项目再放回原来的序列中。

排序效果如下图所示（原图来自百度百科之桶排序）

bucket_sort

实现

public static void sort(int a[]) {
	int n = a.length;
	int bask[][] = new int[10][n];
	int index[] = new int[10];
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < n; i++) {
		max = max > (Integer.toString(a[i]).length()) ? max : (Integer.toString(a[i]).length());
	}
	String str;
	for (int i = max - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			str = "";
			if (Integer.toString(a[j]).length() < max) {
				for (int k = 0; k < max - Integer.toString(a[j]).length(); k++)
					str += "0";
			}
			str += Integer.toString(a[j]);
			bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = a[j];
		}
		int pos = 0;
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < index[j]; k++) {
				a[pos++] = bask[j][k];
			}
		}
		for (int x = 0; x < 10; x++)
			index[x] = 0;
	}
}

完整代码参考BucketSort.java

性能分析

复杂度分析：
1. 平均时间复杂度为 $O(k+n)$；
2. 最差时间复杂度：$O(n^2)$;
3. 最差空间复杂度：$O(k*n)$；
特点：
1. 感觉相当于先进行hash，然后再进行排序，这种思想在海量数据排序中经常会使用到。

算法性能总结

算法名称	平均时间复杂度	最坏情况时间复杂度	最好情况时间复杂度	辅助空间	稳定性
选择排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n\lg{n})$ ~ $O(n^2)$	$O(n^2)$	$O(n^{1.3})$	$ O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$ O(1)$	稳定
自底向上归并排序	$O(n\lg{n})$	$O(n\lg{n}) $	$ O(n) $	$ O(n)$	稳定
自顶向下归并排序	$O(n\lg{n})$	$ O(n\lg{n}) $	$O(n) $	$ O(n)$	稳定
快速排序	$O(n\lg{n}) $	$O(n^2)$	$O(nlgn)$	$O(\lg{n})$ ~ $O(n)$	不稳定
堆排序	$O(n\lg{n}) $	$O(n\lg{n}) $	$O(n\lg{n}$)	$O(1)$	不稳定
计数排序	$ O(n+k) $			$O(n + k)$	稳定
基数排序	$O(k*n)$			$O(n)$	稳定
桶排序	$O(n^2)$			$ O(k)$	稳定

参考资料：

排序算法总结

排序算法总结

性能评估指标

选择排序

原理

步骤

实现

性能分析

插入排序

原理

步骤

实现

性能分析

希尔排序

原理

步骤

实现

性能分析

冒泡排序

原理

步骤

实现

归并排序

原地归并排序

介绍

步骤

实现

自顶向下

原理

步骤

实现

性能分析

自低向上

原理

步骤

实现

性能分析

快速排序

原理

步骤

实现

性能分析

快排算法改进

堆排序

原理

实现

性能分析

计数排序

原理

步骤

实现

性能分析

基数排序（Radix Sort）

原理

步骤

实现

性能分析

桶排序

原理

步骤

实现

性能分析

算法性能总结

版权说明

公众号