排序算法

吹梦到西洲

发布于：Mar 19, 2020

十大排序算法比较与总结

下列表格主要来源于学习数据结构时的总结，在《Algorithm to Algorithm》一书中涉及的算法将以该书内容为准，因为Markdown并不能完美支持 $LaTex$，所以这里就不能手写伪代码(Pseudocode)了。

在此默认排序方式为升序，即从小到大。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

分类	算法名称	平均	最好	最坏	空间复杂度	稳定性
插入	直接插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	$Y$
插入	折半插入	$O(n^2)$	$O(n\lg n)$	$O(n^2)$	$O(1)$	$Y$
插入	希尔排序	$O(n\lg n)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	$N$
交换	冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	$Y$
交换	快速排序	$O(n\lg n)$	$O(n\lg n)$	$O(n^2)$	$O(\lg n)$	$N$
选择	简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	$N$
选择	堆排序	$O(n\lg n)$	$O(n)$	$O(n\lg n)$	$O(1)$	$N$
归并	二路归并	$O(n\lg n)$	$O(n\lg n)$	$O(n\lg n)$	$O(n)$	$Y$
线性	基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r+n)$	$Y$
线性	计数排序	$\Theta(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	$Y$
线性	桶排序	$O(n+k)$	$O(n)$	$O(n^2)$	$O(n*k)$	$Y$

平均而言，快速排序最佳，最坏情况下不如堆排序与归并排序
直接插入排序，折半插入排序，简单选择排序，冒泡排序等时间复杂度为 $O(n^2)$ 的排序不适用与 $n$ 较大的情况
一趟排序至少能保证一个关键字到达最终位置的排序：交换类(冒泡排序，快速排序)，选择类排序(简单选择排序，堆排序)
关键字比较次数和原始序列无关的排序：简单选择排序，折半插入排序，归并排序，基数排序
排序趟数和原始序列有关的排序：交换类排序(冒泡排序，快速排序)
排序趟数与原始序列无关的排序：直接插入排序，折半插入排序，希尔排序，堆排序，二路归并排序，简单选择排序，基数排序
借助于比较进行排序的算法，最坏时至少为 $O(n\lg n)$
直接插入和折半插入的区别仅在于查找插入位置的方式不同
元素的移动次数与原始序列无关的排序：基数排序
不稳定排序：快速排序，希尔排序，简单选择排序，堆排序
时间复杂度为 $O(n\lg n)$ 的排序：快速排序，希尔排序，二路归并排序，堆排序
计数排序不是比较排序，因此不受 $\Omega(n\lg n)$ 的限制

TODO

时间复杂度的计算方法
未完成的算法
相应算法的动图

1. 插入类排序

1.1 直接插入

《Introduction to Algorithm》这本经典著作中的第一个算法例子就是 $Insertion Sort$ ，作者也是在这个例子中举出了此书中分析算法的核心名词 Loop Invariant ，即循环不变量，使用循环不变量能够帮助我们明白一个算法为什么是正确的。循环不变量包括三个要素

Initialization: It is true prior to the first iteration of the loop.
- 初始化：在循环迭代中第一步是正确的
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
- 保持：如果循环中前一次的迭代结果时正确的，那么在下一次迭代过程中也应该是正确的。
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
- 终止：当循环结束时，不变量可以给我们一个能证明算法是正确的有用的特性。

就像打扑克牌补牌时的方式一样，第一张牌肯定是有序的，从二张牌开始，每次将补到的牌按大小顺序插入手牌中，这样每次能保证每次插入后的手牌都是有序的，但是很可能会存在的问题是补到的牌不大不小，正处中间，这就会导致比这张牌大的手牌将会逐个后移。

基本思想：将待插入的元素逐个插入到已经有序的数组中。
循环不变量：在插入之前已经有序的数组，在插入后数组仍然是有序的。

/**
 * 基本思想：从数组中的第二个元素起，保存当前元素，
 * 拿当前元素之前的所有元素跟当前元素比较，如果之前元素 > 当前元素，将之前元素后移一位，
 * 如果遇到之前的某个元素不比当前元素大了，或者是走到头了，表示这个之前元素是不大于当前元素的，
 * 那当前元素就应该排在这个之前元素的屁股后边，这里就是它的最终归宿。
 */
public static int[] insertionSort(int[] nums) {
    if (Objects.isNull(nums) || nums.length <= 1) {
        return nums;
    }
    
    for (int i = 1; i < nums.length; i++) {
        int currentNum = nums[i]; // 当前值
        int j = i - 1; // 当前值前边的值的索引
        // j >= 0 至关重要，这个值为数组中第一个值的下标，
        // 如果是 j > 0 的话，进入循环的条件少了个数（num[0]），第一个值不会参与比较。
        while (j >= 0 && nums[j] > currentNum) {
            nums[j + 1] = nums[j];
            --j;
        }
        // 归位元素
        nums[j + 1] = currentNum;
    }
    return nums;
}

现在，利用 循环不变量 来证明这个算法是正确的。

初始化：在第一次执行的时候，仅有元素 array[0]，很显然一个数字无论从哪种排序方式看都是有序的。
保持：接下来需要证明在每一次循环中都能保持循环不变量成立。从非形式化的方式上看，在for循环中，可能要将array[i-1], array[i-2]... 的元素向后移动一个位置，直到找到array[i]要插入的位置为止。
终止：当外层for循环结束的时候，在外层for循环将i 替换为 n的时候，就有子数组 array[0..n-1]已经排好序了，而子数组其实正是整个数组，说明整个数组也已经排好序了，说明算法是正确的。

渐进记号

在《Introduction to Algorithm》一书中，出现最多的其实并不是大 $O$ 记号，而是$\Theta$ 记号，使用 $\Theta$ 记号的意思是紧确界，而简单的使用大 $O$ 记号则表示该问题的一个规模的上界，表示该问题的最坏情况，另外有该问题的下界记号 $\Omega$ ，表示该问题的最好情况, 而 $\Theta$ 记号则表示介于二者之间。

图像比具体的数学定义更直观一些。

在插入排序中最好的情况是指该数组已经有序，此时代码中的while循环条件之中不满足，则不用交换元素，只需要遍历一遍数组，即达到下确界 $\Omega(n)$
最坏情况则是该数组已有序但是与要求的排序规则相比则是逆序，此时while循环每次满足，而移动元素的次数为 $1+2+3+\dots + (n-1) = \frac{n(n-1)}{2}$ 次，即达到上确界 $O(n^2)$ .
所以通常情况下，该问题的规模函数介于二者之间，为 $\Theta(n^2)$
更加细致入微的分析还请参考《Introduction to Algorithm》一书英文版26页，下面是一张书中的截图

这里可能有人要问，为什么介于二者之间就是 $\Theta(n^2)$ ，而不是 $\Theta(n)$ 呢？具体的下面再证明。

在证明之前首先了解《Introduction to Algorithm》一书中三种求解问题规模的方法：

对于问题形如
$$
T(n)=2T(n/2)+\Theta(n)
$$
一般有三种方法，分别为代入法，递归树法，主定理法

substitution method：we guess a bound and then use mathematical in- duction to prove our guess correct.
recursion-tree method：converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.
master method：rovides bounds for recurrences of the form
$$
T(n) = aT(n/b)+f(n), \quad a \ge 1, b>1
$$
$ f(n)$ 为已知函数。

1.2 折半插入

折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

public static int[] binaryInsertionSort(int[] array) {
    if (array.length == 0) return array;
    for (int i = 1; i < array.length; i++) {
        // 先保存要插入的值
        int key = array[i];
        int left = 0, right = i - 1;
        // 然后寻找它需要插入的位置
        while (left <= right) {
            int middle = (left + right) / 2;
            if (array[middle] < key) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        // 将 left 后边的数组整体后移一位
        for (int j = i; j > left; j--) {
            array[j] = array[j - 1];
        }

        array[left] = key;
    }
    return array;
}

分析：与直接插入相比，折半插入仅仅是对查找插入位置的方式进行了优化，减少了查找插入位置的时间，但是元素的移动次数并没有减少，所以总的来说时空复杂度与插入排序相同。
循环不变量：与插入排序一样，循环不变量为在插入数字之前已有序的数组。

1.3 希尔排序

希尔排序(Shellsort) ，也称递减增量排序算法，是插入排序的一种更高效的改进版本，但是希尔排序在高效的同时也破坏了排序元素的稳定性，是非稳定排序算法。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为 $O(n^2)$ 的排序（冒泡排序或插入排序），可能会进行 $n$ 次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += stepSize, 而不是 i++）。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序(其实就是按索引下标分组，如下标为0，5，10… 一组，而下标1，6，11…一组，下标 2，7，12… 一组)，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

// 步长为5得到
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

// 对每列进行排序，也就是组内排序。
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

// 第一次排序结束后 从左往右，从上到下穿起来得到
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

// 步长为3得到
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

// 再次对每列进行排序，即再一次组内排序。
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

// 再次穿起来得到
[ 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 ]

// 此时数组已经基本有序了，再次选取步长为 1 ，也就成为了实际意义上的插入排序。
// 需要注意的是，步长尽量选择为互质的数，这样就可以减小最小公倍数出现的情况，从而避免一个数字被分到不同分组里

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)，该序列的项来自 $9 \times (4^i - 2^i)$ 和 $2^{i+2}(2^{i+2}-3)+1$ 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列):(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

在此选择 Shell 本人推荐使用的步长为 n/2, 其他的步长实现待补充。

public static int[] shellSort(int[] array) {
    int length = array.length;
    if (length == 0) return array;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        // 步长每次取为分组长度的 1/2
        for (int i = step; i < length; i++) {
            // 组内排序
            temp = array[i];
            int j = i - step;
            while (j >= 0 && array[j] > temp) {
                array[j + step] = array[j];
                j -= step;
            }
            array[j + step] = temp;
        }
    }
    return array;
}

分析：显然可以看到外层循环次数为 $\lfloor \log_2n \rfloor$ ，而内层循环为 $n$ ，从而该排序方法的时间复杂度为 $O(n\log_2 n)$ .
循环不变量：元素在每一个分组之内都是有序的

2. 交换类排序

2.1 冒泡排序

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换它们的位置。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数，即 冒泡排序每轮结束后至少能保证一个元素处于最终位置上。
针对除最后一个元素外的所有元素重复以上的步骤。

public int[] bubbleSort(int[] array) {
    int temp;
    for (int i = 0; i < array.length - 1; i++) {
        // 从第一个到倒数第二个元素
        for (int j = 0; j < array.length - 1 - i; j++) {
            // 每轮冒泡结束后至少有一个元素到达最终位置，所以比较的元素个数依次为
            // n - 1、n - 2、n - 3 ...
            if (array[j] > array[j + 1]) {
                // 每次取得两个数之间较大的数
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}

冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。在最坏的情况(逆序)，冒泡排序需要 $O(n^2)$ 次交换，而插入排序只要最多 $O(n)$ 交换。

冒泡排序如果能在内部循环第一次运行时，使用一个旗标来表示有无需要交换的可能，也可以把最优情况下的复杂度降低到 $O(n)$。在这个情况，已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。

2.2 快速排序

2.2.1 快速排序基础

上图是《Introduction to Algorithm》一书第七章对于快速排序的介绍，大意是：快速排序在问题规模为 $n$ 的情况下最坏情况达到 $\Theta(n^2)$ ，但是由于它平均情况下出色的效率，时间规模为 $\Theta(n\lg n)$ ，而且在 $\Theta(n\lg n)$ 中所隐含的常数因子比较小，而且可以很好的就地排序。

像归并排序一样，快速排序也是基于分治(Divide And Conquer)思想的。下面是对一个典型子数组A[p..r]排序的分治过程的的三个步骤。

分解：找到一个枢轴 q将原数组划分为两个子数组 A[p..q-1],A[q+1, r]，使得前一个子数组中的所有元素都小于等于 A[q]，而后一个数组中的所有元素都大于 A[q]，下标 q 也在这个划分过程中参与计算；
解决：通过递归调用快速排序，对子数组 A[p..q-1] 和 A[q+1,r]排序；
合并：因为两个子数组是就地排序的，将它们的合并不需要操作，整个数组已排好序。

PARTITION 总是选择数组中最右边的元素作为 枢轴 Pivot，并围绕它来划分子数组，随着该过程的进行，数组被划分为四个区域(可能有空的)，在第 $3-6$ 行的 for 循环每次迭代的开始，每一个区域都满足特定的性质。这些性质就是我们从插入排序时就开始提到的 Loop Invariant，循环不变量。

在上图中，有 $A[p..i]$ 中的值均小于等于 $x$ ，而 $A[i+1,j-1]$ 之间均大于 $x$ ，而 $A[j,r-1]$ 则没有限制， $A[r]=x$ 。

下面来证明循环不变量：

初始化：在循环的第一轮迭代开始之前，有 $i=p-1$ 和 $j=p$ ，在 $p$ 和 $i$ 之间没有值，在 $i+1$ 和 $j-1$ 之间也没有值。因此，循环不变量的头两个条件显然满足。第1行中的赋值操作满足第三个条件。
保持：需要考虑下图中的两种情况，具体取决于第 $4$ 行中测试的结果。
- 第一种情况显示当 $A[j]>x$ 时所做的处理；循环中的唯一操作是 $j++$ ，在 $j++$ 后，条件 $2$ 对 $A[j-1]$ 成立，且所有其他项保持不变。
- 第二种情况显示当 $A[j]\le x$ 时所做的处理：将 $i$ 加 $1$，交换 $A[i]$ 和 $A[j]$ ，再将 $j$ 加1。因为进行了交换，现在 $A[i]\le x$ ，因而条件 $1$ 满足。类似的，还有 $A[j-1]>x$ ，因为根据循环不变量，被交换进 $A[j-1]$ 的项目是大于 $x$ 的。

终止：当终止时， $j=r$ ，于是数组中的每个元素都在循环不变量所描述的三个集合的某一个之中。也就是已经把数组中的所有元素划分到了三个集合中：一个集合包含了小于等于 $x$ 的元素，第二个集合中包含了大于 $x$ 的元素，还有一个只包含了 $x$ 的集合。
此过程的运行时间为 $\Theta(n)$ ，其中 $n=r-p+1$ ，暂不证明。

2.2.2 快速排序性能

快速排序的运行时间与划分是否对称有关，而是否对称又与选择哪一个元素为 $pivot$ 有关，如果划分是对称的，那么从渐进意义上来讲就与 归并算法 一样快；如果划分是不对称的，那么从渐进意义上来讲就与 插入排序 一样慢。

最坏情况：每次划分的两个区域分别包含 $n-1$ 和 $1$ 个元素，运行时间递归式为：

$$
T(n) = T(n-1)+T(0)+\Theta(n)=T(n-1)+\Theta(n)
$$

最好情况：每次划分的两个子问题的大小都不可能大于 $n/2$ ，其中的一个问题大小为 $\lfloor n/2 \rfloor$ ，另一个子问题的大小为 $\lceil n/2 \rceil - 1$ ，运行时间递归式为：

$$
T(n) = 2T(n/2)+\Theta(n)
$$

// 对自身的两次递归调用
public int[] quickSort(int[] array, int p, int r) {
    if (p < r) {
        int q = partition(array, p, r);
        quickSort(array, p, q - 1);
        quickSort(array, q + 1, r);
    }
    return array;
}

// 尾递归调用
public int[] tailRecursiveQuickSort(int[] array, int left, int right) {
  while (left < right) {
    int middle = partition(array, left, right);
    tailRecursiveQuickSort(array, left, middle - 1);
    left = right + 1;
  }
  return array;
}

// 由 N.Lomuto 提出
private int partition(int[] array, int p, int r) {
    int x = array[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (array[j] <= x) {
            i++;
            swap(array, i, j);
        }
    }
    swap(array, i + 1, r);
    return i + 1;
}

private void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

最初的快排数组划分方式，由 C.R.Hoare 提出，也是国内本科教学中最常见的划分方法。

/**
* 这是 C.R.Hoare 最早提出的分区算法，选最右元素为枢轴，
* 1. 从左向右找到第一个大于等于 key 的值 array[i]；
* 2. 从右向左找到第一个小于 key 的值 array[j]；
* 3. 交换找到的这两个值 exchange(array, i, j)
* 4. 循环结束后，交换 i 和最右元素的值，复位 array[right] 的最终位置
* 5. 返回 array[right] 的新位置
* @param arr 待排序数组
* @param l 数组左边界
* @param r 数组右边界
* @return 枢轴索引
*/
public static int hoarePartition(int[] array, int left, int right) {
  int key = array[right];
  int i = left;
  int j = right;
  while (i < j) {
    while (i < j && array[i] < key) {
      i++;
    }
    while (i < j && array[j] >= key) {
      j--;
    }
    exchange(array, i, j);
  }
  exchange(array, i, right);
  return i;
}

无论选择何种方式实现 partition，一定要确保在 pivot 左边的 <= pivot，pivot 右边的 > pivot。

2.2.3 分析与具体证明

如上图所示，我们假设在每次划分时按 $9:1$ 的比例划分两个子数组，生成的递归树如上图所示，运行时间递归式为
$$
T(n)\le T(9n/10)+T(n/10)+cn
$$
收敛速度更快的是 $\log_{10}n$ ，因为每次都减小为上一次的 $\frac{1}{10}$ ，但是为了让全部的子数组都收敛到 $1$ ，收敛时间则取决于 $\log_{10/9}n = \Theta(n)$ ,而把每一水平行加起来的结果都小于等于 $cn$ ，再乘以树的高度 $\Theta(n)$ ，得到总的运行时间为 $O(n\lg n)$ ，这与划分长度是每次在正中间的效果是一样的。

事实上，即使是按照 $99:1、999:1、9999:1、 \dots$ 这种常数比例进行的划分都会产生深度为 $\Theta(n)$ 的递归树，其中每一层的代价为 $O(n)$，那么总的运行时间也就是 $O(n\lg n)$ 了。伪代码中每次选取子数组中最右边的元素作为 $pivot$ 也是以此为依据的。

3. 选择类排序

3.1 简单选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。
选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 $n$ 个元素的表进行排序总共进行至多次 $n-1$ 交换。
在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

初始值： 3  1  5  7  2  4  9  6

第一趟： 1  3  5  7  2  4  9  6
第二趟： 1  2  5  7  3  4  9  6
第三趟： 1  2  3  7  5  4  9  6
第四趟： 1  2  3  4  5  7  9  6
第五趟： 1  2  3  4  5  7  9  6
第六趟： 1  2  3  4  5  6  9  7
第七趟： 1  2  3  4  5  6  7  9
第八趟： 1  2  3  4  5  6  7  9

算法实现：

public int[] selectionSort(int[] arr) {
    if (arr == null || arr.length == 0) return new int[0];
    int min, minIdx; // 保存最小值及其索引
    for (int i = 0; i < arr.length; i++) {
        min = arr[i]; // 保存最小值
        minIdx = i; // 保存最小值的索引
        for (int j = i + 1; j < arr.length; j++) { // 遍历当前位置之后的所有元素
            if (arr[j] < min) {
                min = arr[j]; // 更新最小值
                minIdx = j; // 更新最小值的索引
            }
        }
        // 等到找到最小值以后，将当前位置的值与最小值进行交换
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
    return arr;
}

最好情况即为数组已有序，最坏情况为逆序。
但是无论最好最坏情况，选择排序的比较次数都是 $\frac{n(n-1)}{2}$ ，仅有交换次数不同，最好情况交换 $0$ 次，最坏情况交换 $n-1$ 次。
总的问题规模为 $O(n^2)$ 。

3.2 堆排序

上图是《Introduction to Algorithm》一书第六章对于堆排序的介绍，简单的翻译一下就是：像归并排序而不像插入排序，堆排序的运行时间为 $O(n\lg n)$ ; 像插入排序而不像归并排序，堆排序是一种原地(in place)排序算法，在任何时刻，数组中只有常数个元素存储在输入数组之外。

3.2.1 堆简介

（二叉）堆数据结构式一种数组对象，如下图所示，它可以被视为一课 完全二叉树，树中每个节点与数组中存放该节点值的那个元素对应。根据完全二叉树的定义，树种除了最后一层外，其它层一定是满的，树的根为 $A[0]$ ，对于下标为 $i$ 的结点而言，父节点下标为 $\lfloor i/2-1 \rfloor$ ，左孩子为 $\lfloor 2i-1 \rfloor$ ，右孩子为 $\lfloor 2i \rfloor$ 。在计算机底层，可以通过 位运算 快速地计算出各个下标。

表示堆的数组 $A$ 是一个具有两个属性的对象： $length[A]$ 是数组中的元素个数，heap-size[A]是存放在 $A$ 中的堆的元素个数，所以有 heap-size[A] <= length[A] .

在堆排序算法中，我们使用的是 大根堆，小根堆 通常用于构造 优先队列。堆可以被看作是一棵树，因为是完全二叉树，所以其高度为 $\Theta(n)$ ，堆结构的一些基本操作的运行时间至多与树的高度成正比，为 $O(\lg n)$ 。下面给出一些基本过程，并说明它们在排序算法和优先队列数据结构中如何使用。

MAX-HEAPIFY ：运行时间为 $O(\lg n)$ ，是保持大根堆性质的关键。
BUILD-MAX-HEAP ：以线性时间运行，可以在无序的输入数组基础上构造出大根堆。
HEAPSORT ：运行时间为 $O(n\lg n)$ ，对一个数组原地进行排序。
MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM 过程的运行时间为 $O(\lg n)$ ，可以让堆结构作为优先队列使用。

3.2.2 保持堆的性质

MAX-HEAPIFY 是对大根堆进行操作的重要子程序。其输入一个数组 $A$ 和下标 $i$ 。当 MAX-HEAPIFY 被调用时，我们假设以 LEFT(i) 和 RIGHT(i) 为根的两个二叉树都是大根堆，但这时 $A[i]$ 可能小于其子女，这样就违反了大根堆的性质。MAX-HEAPIFY 让$A[i]$ 在大根堆中下降，使得以 $i$ 为根的子树成为最大堆。

下图描述了 MAX-HEAPIFY 的过程，在算法的每一步里，从元素 A[i], A[LEFT(i)],A[RIGHT(i)] 中找出最大的，并将其下标存储在 $largest$ 中。如果 $A[i]$ 是最大的，则以 $i$ 为根的子树已经是大根堆，程序结束。否则， $i$ 的某个子节点中有最大元素，则交换 $A[i]$ 和 $A[largest]$ ，从而使其满足堆的性质。下标为 $largest$ 的结点在交换后的值是 $A[i]$ ，以该节点为根的子树又有可能违反大根堆的性质。因而要对该子树递归调用 MAX-HEAPIFY 。

3.2.3 建堆

我们可以自底向上地用 MAX-HEAPIFY 来将一个数组 $A[0..n-1]$ 变成一个大根堆。

为了证明 BUILD-MAX-HEAP 的正确性，可以使用如下的 循环不变量。

在 $2-3$ 行中 $for$ 循环的每一次迭代开始时，结点 $i+1, i+2, \dots, n-1$ 都是一个大根堆的根

3.2.4 堆排序算法

开始时，对排序算法先用 BUILD-MAX-HEAP 来将输入数组 $A[0..n-1]$ 构造成一个大根堆。因为数组中最大元素在根 $A[0]$ ，则可以通过把它与 $A[n-1]$ 互换来达到最终正确的位置。现在如果从堆中去掉结点 $n-1$ ，可以很容易地将 $A[0..n-2]$ 建成大根堆。原来根的子女仍是大根堆，而新的根元素可能违背了大根堆的性质。这时调用 MAX-HEAPIFY(A, 0) 就可以保存这一性质，构造出大根堆，堆排序算法不断重复这个过程，堆的大小由 $n-1$ 降到 $2$ 。

循环不变量：在每次 $for$ 循环的 $2-5$ 行的迭代开始时，子数组 $A[0..i]$ 是一个包含了 $A[0..n-1]$ 中的 $i$ 个最小元素的最大堆；而子数组 $A[i+1..n-1]$ 包含了已排序的 $A[0..n-1]$ 中的 $n-i$ 个最大元素。

public class HeapSort {
    private int[] arr;
    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort() {
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (arr.length >> 1)- 1;
        for (int i = beginIndex; i >= 0; i--)
            maxHeapify(i, len);
        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for (int i = len; i > 0; i--) {
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index, int len) {
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。
        if (li > len) return;      // 左子节点索引超出计算范围，直接返回。
        if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if (arr[cMax] > arr[index]) {
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }
}

4. 归并排序

有很多算法在结构上是递归的，为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题，这些算法通常采用 分治策略(Divide And Conquer)：将原问题分成 $n$ 个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，最后合并其结果，就得到原问题的解。

分治策略在每一层上都有三个步骤：

分解(Divide)：将原问题分解为一系列的子问题；
解决(Conquer): 递归地解各子问题，若子问题足够小，则直接求解；
合并(Combine): 将子问题的结果合并成原问题的解。

归并排序(Merge Sort) 算法完全按照上述模式，直观操作如下：

分解：将 $n$ 个元素分成各含 $n/2$ 个元素的子序列；
解决：用归并排序对两个子序列递归地排序；
合并：合并两个已排序的子序列得到排序的结果。

在对子序列排序时，其长度为 $1$ 时递归结束，单个元素被认为是已经排好序的。

归并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做归并，引入一个辅助过程 MERGE(A, p, q, r) .

再举扑克牌这个例子，假如我们现在有两堆已好序的扑克牌，它们面朝上放着，最小的牌放在最上面，而我们要做的是把牌从小到大排成一副完整的牌。在刚开始时我们从两堆牌中取出最上面一张牌，然后比较二者大小，然后将其中较小的牌反面盖上，我们称其为第三堆，然后将较大的牌与另一堆最上面的的最小的牌进行比较。然后把二者较小的牌放到第三堆上，重复此过程，直到其中一堆牌全部被放到第三堆上，第一堆或者第二堆剩下的牌直接全部盖到第三堆上去，此时就完成了排序。

伪代码: 这里用 $\infty$ 作为哨兵，如果出现哨兵牌则说明该牌不可能是两者之中较小的牌，一旦两张牌同时出现哨兵牌，则说明所有的非哨兵牌已经全部放到第三堆上去了。

初始化：在 for 循环的第一轮迭代开始之前，有 k = p, 因而子数组 A[p..k-1] 是空的。这个空的子数组包含了 L 和 R 中 k - p = 0 个最小的元素。此外，又因为 i = j + 1 ， L[i] 和 R[j] 都是各自所在数组中，尚未被副指挥数组 A 中的最小元素。
保持：为了说明每一轮迭代中都能使循环不变式保持成立，首先架设 $L[i]\le R[j]$ ，那么 $L[i]$ 就是尚未被复制回数组 A 中的最小元素。由于 A[p..k-1] 包含了 k - p 个最小的元素，因此在第 $14$ 行将 L[i] 复制回 A[k] 中后，子数组 A[p..k] 将包含 k - p + 1 个最小的元素。增加 k, i 的值，会为下一轮迭代重新建立 循环不变量 的值，如果这次有 $L[i] \ge R[j]$，则第 $16-17$ 行就会执行相应的操作，以使循环不变量保持成立。
终止：在终止时， k = r + 1 ，根据 循环不变量，子数组 A[p..k-1] 包含了 $L[1..n_1+1]$和$R[1..n_2+1]$中 k - p = r - p + 1 个最小元素，并且已经是排好序的。数组 L、R 合起来包含了 $n_1+n_2+2=r-p+3$ 个元素，除了两个最大的元素外，其余的所有元素都已被复制回数组 A 中，这两个最大元素都是哨兵。

$MERGE$ 过程的运行时间为 $\Theta(n)$ ，此处 $n=r-p+1$ , 其中第 $1-3、8-11$ 行每一行的运行时间都是常量， $4-7$ 行 for循环所需时间为 $\Theta(n_1+n_2)=\Theta(n)$, 第 $12-17$ 行的 for 循环共有 $n$ 轮迭代，其中的每一轮迭代所需时间都是常量。

现在，就可以将 $MERGE$ 过程作为合并排序中的一个子程序来使用了，

/**
 * 归并排序
 */
public static int[] mergeSort(int[] A, int left, int right) {
    if (left < right) {
        int middle = (left + right) >>> 1;
        mergeSort(A, left, middle);
        mergeSort(A, middle + 1, right);
        return merge(A, left, middle, right);
    }
    return A;
}

/**
 * @param A A=[2,4,5,7,1,2,3,6], L = [2,4,5,7], R=[1,2,3,6].
 * @param left p = 0
 * @param middle q = 3
 * @param right r = 7
 */
private static int[] merge(int[] A, int left, int middle, int right) {
    int lenOfL = middle - left + 1;
    int lenOfR = right - middle;
    int[] L = new int[lenOfL + 1];
    int[] R = new int[lenOfR + 1];

    if (lenOfL >= 0) {
        System.arraycopy(A, left, L, 0, lenOfL);
    }

    for (int j = 0; j < lenOfR; j++) {
        R[j] = A[middle + j + 1];
    }

    L[lenOfL] = Integer.MAX_VALUE;
    R[lenOfR] = Integer.MAX_VALUE;

    int i = 0, j = 0;

    for (int k = left; k < right + 1; k++) {
        // k < right + 1，而不是 k < right，
        // L 和 R 的长度都增加了 1，如果这里不 +1 的话，不能保证 L 和 R 走到头。
        A[k] = L[i] <= R[j] ? L[i++] : R[j++];
    }

    return A;
}

归并排序的最坏情况运行时间表达式为，由 主定理 可以求得 $T(n) = \Theta(n\lg n)$
$$
T(n)=2T(n/2)+\Theta(n)
$$

5. 线性时间排序

到目前为止，我们所分析过的排序算法都有一个令人感兴趣的性质：排序结果中，各元素的次序基于输入元素间的比较，我们把这类排序算法称为 比较排序。

5.0 排序算法的下界

比较排序可以被抽象地视为决策树，表示排序算法作用于给定输入所做的所有比较，而控制结构，数据移动等都被忽略了。下图对应于插入排序算法作用于三个元素的输入序列上的决策树

定理：任意一个比较排序算法在最坏情况下，都需要做 $\Omega(n\lg n)$ 次的比较。

证明：对于一棵每个排列都作为一个可达叶结点出现的决策树，考虑一棵高度为 $h$ 的、具有 $l$ 个可达叶结点的决策树，它对应于对 $n$ 个元素所做的比较排序。因为 $n$ 个输入元素共有 $n!$ 种排列，每一种都作为一个叶子出现在树中，所以有 $n! \le l$ ，又由于在一棵高度为 $h$ 的二叉树中，叶子的数目不多于 $2^k$ ，则有
$$
n! \le l \le2^k
$$
对该式取对数，得到 $h\ge \lg(n!) = \Omega(n\lg n)$ .

从中也可以推论出：堆排序和归并排序都是渐进最优的比较排序算法。

5.1 计数排序

计数排序假设 $n$ 个输入元素中的每一个都是介于 $0..k$ 之间的整数，此处 $k$ 为某个整数。当 $k=O(n)$ 时，计数排序的运行时间为 $\Theta(n)$ .

计数排序的 基本思想 就是对每一个输入元素 $x$ ，确定出小于 $x$ 的元素个数。有了这一信息，就可以把 $x$ 直接放到它在最终输出数组中的位置上。例如，如果有 $17$ 个元素小于 $x$ ，那么 $x$ 就属于第 $18$ 个输出位置。当有几个元素相同时，就要略作修改，因为同一个位置当然不能存放多个元素，就像散列表的冲突碰撞后要做处理一样。

在下面计数排序的伪代码中，我们假定输入是个数组 $A[1..n]$ , $length[A]=n$，另外还需要两个数组：存放排序结果的 $B[1..n]$ ，以及提供临时存储区的 $C[0..k]$ .

1-3 行代码：初始化，所花时间 $\Theta(k)$
4-5 行代码：检查每个输入元素，如果值为 $i$ 即增加 $C[i]$ 的值，于是在第5行之后， $C[i]$就存放了等于元素 $i$ 的个数，所花时间 $\Theta(n)$
7-8行代码：通过在数组 $C$ 中记录计数和，可以确定对每一个 $i=0,1,2,\dots,k$ ，有多少输入元素是小于等于 $i$ 的，所花时间 $\Theta(k)$
10-12行代码：把每个元素 $A[j]$ 放在输出数组 $B$ 中与其对应的最终位置上，所花时间 $\Theta(n)$

这样，总的时间就是 $\Theta(n+k)$ ，当 $k=O(n)$ 时，计数排序的运行时间就是 $\Theta(n)$ ，同时也是稳定的。

public static int[] countingSort(int[] A) {
    int[] B = new int[A.length];
    // 假设A中的数据 a' 有，0 <= a' && a' < k并且 k = 100
    int k = 100;
    countingSort(A, B, k);
    return B;
}

private static void countingSort(int[] A, int[] B, int k) {
    int[] C = new int[k];
    // 计数
    for (int j = 0; j < A.length; j++) {
        int a = A[j];
        C[a] += 1;
    }
    // 求计数和
    for (int i = 1; i < k; i++) {
        C[i] = C[i] + C[i - 1];
    }
    // 整理
    for (int j = A.length - 1; j >= 0; j--) {
        int a = A[j];
        B[C[a] - 1] = a;
        C[a] -= 1;
    }
}

5.2 基数排序

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

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

假如我们想根据三个关键字年、月、日来对日期进行排序，我们可以先比较年，再比较月，再比较日，当然也可以先比较日，再比较月，再比较年。这也就对应了 LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

基数排序的代码是非常直观的

引理1：给定 $n$ 个 $d$ 位数，每一个数位有 $k$ 种可能的值，基数排序算法能以 $\Theta(d(n+k))$ 的时间正确地对这些数进行排序。
引理2：给定 $n$ 个 $b$ 位数和任何正整数 $r\le b$ ，$RADIX-SORT$ 能在 $\Theta(\frac{b(n+2^r)}{r})$ 的时间内正确地对这些数进行排序。

// 来源于 百度百科 https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
public static int[] radixSort(int[] number, int d) {
    int k = 0;
    int n = 1;
    int m = 1; //控制键值排序依据在哪一位
    int[][] temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9
    int[] order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
    while(m <= d) {
        for(int i = 0; i < number.length; i++) {
            int lsd = ((number[i] / n) % 10);
            temp[lsd][order[lsd]] = number[i];
            order[lsd]++;
        }
        for(int i = 0; i < 10; i++) {
            if(order[i] != 0) {
            	for(int j = 0; j < order[i]; j++) {
                    number[k] = temp[i][j];
                    k++;
                }   
            }
            order[i] = 0;
        }
        n *= 10;
        k = 0;
        m++;
    }
    return number;
}

菜鸟教程代码实现

基数排序是否要比基于比较的排序算法(如快速排序)要好呢？如果根据常见的情况有 $b=O(\lg n)$ ，并选择 $r \approx \lg n$ ，则基数排序的运行时间为 $\Theta(n)$ ，这看上去要比快速排序的平均情况 $\Theta(n\lg n)$ 要好一些，但是也不是一定的，在两个排序时间中隐含在 $\Theta$ 中的常数因子是不同的。

5.3 桶排序

当桶排序(bucket sort) 的输入符合均匀分布时，即可以以线性时间运行。与基数排序类似，桶排序也对输入作了某种架设，因而运行的很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序择假设输入由一个随机过程产生，该过程将元素均匀地分布在区间 $[0,1)$ 上。

桶排序的思想就是把区间 $[0,1)$ 划分成 $n$ 个相同大小的子区间，或称为桶。然后，将 $n$ 个输入数分布到各个桶中去。因为输入数均匀分布在 $[0,1)$ 上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

为了说明这个算法是正确的，我们假设两个元素 $A[i]\le A[j]$ 。由于 $\lfloor nA[i] \rfloor \le \lfloor nA[j] \rfloor$ ，元素 $A[i]$ 或者被放入 $A[j]$ 所在桶中，或者被放入一个下标更小的桶中，如果 $A[i],A[j]$ 落在同一个桶中，则第 $7-8$ 行中的 for 循环会将它们按适当的顺序排列；如果 $A[i],A[j]$ 落在不同桶中，则第 $9$ 行会将它们按适当的顺序排列。因此，桶排序是正确的。

除第 $8$ 行外，所有其他各行在最坏情况下的运行时间都是 $O(n)$ ，仍然需要对第 $8$ 行中插入排序的 $n$ 次调用所花的总时间。

为了分析调用插入排序的时间代价，设 $n_i$ 为表示桶 $B[i]$ 中元素个数的随机变量。因为插入排序以二次时间运行，因而桶排序的运行时间：
$$
T(n)=\Theta(n) + \sum_{i=0}^{n-1}O(n_i^2)
$$
对两边的值取期望( 概率论中的期望 $E(x)$ )，并利用期望函数的线性性质，可以得到：
$$
E[T(n)]=E[\Theta(n) + \sum_{i=0}^{n-1}O(n_i^2)]=\Theta(n)+ \sum_{i=0}^{n-1}E[O(n_i^2)]=\Theta(n)+ \sum_{i=0}^{n-1}O(E[n_i^2])
$$
下式对 $i=0,1,\cdots,n-1$ 是成立的(证明略)。
$$
E[n_i^2]=2-\frac{1}{n}
$$
总之最后我们可以得出这样一个结论：即桶排序的期望运行时间为 $\Theta(n) + n·O(2-1/n)=\Theta(n)$ ，于是，整个桶排序算法以线性 期望时间 运行。

// 来源于：https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F#Java%E5%AF%A6%E7%8F%BE%E7%AE%97%E6%B3%95
private int indexFor(int a, int min, int step) {
    return (a - min) / step;
}

public void bucketSort(int[] arr) {

    int max = arr[0], min = arr[0];
    for (int a : arr) {
        if (max < a)
            max = a;
        if (min > a)
            min = a;
    }
    // 該值也可根據實際情況選擇
    int bucketNum = max / 10 - min / 10 + 1;
    List buckList = new ArrayList<List<Integer>>();
    // create bucket
    for (int i = 1; i <= bucketNum; i++) {
        buckList.add(new ArrayList<Integer>());
    }
    // push into the bucket
    for (int i = 0; i < arr.length; i++) {
        int index = indexFor(arr[i], min, 10);
        ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
    }
    ArrayList<Integer> bucket = null;
    int index = 0;
    for (int i = 0; i < bucketNum; i++) {
        bucket = (ArrayList<Integer>) buckList.get(i);
        insertSort(bucket);
        for (int k : bucket) {
            arr[index++] = k;
        }
    }

}

// 把桶內元素插入排序
private void insertSort(List<Integer> bucket) {
    for (int i = 1; i < bucket.size(); i++) {
        int temp = bucket.get(i);
        int j = i - 1;
        for (; j >= 0 && bucket.get(j) > temp; j--) {
            bucket.set(j + 1, bucket.get(j));
        }
        bucket.set(j + 1, temp);
    }
}