（三）排序

1 初级排序算法

排序算法关注的主要是重新排列数组元素，其中每个元素都有一个主键。排序算法是将所有元素主键按某种方式排列（通常是按照大小或是字母顺序）。排序后索引较大的主键大于等于索引较小的主键。

排序算法类的模板

public class Example{
    public static void sort(Comparable a[]){}
    private static boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){
        for(int i = 0;  i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static boolean isSort(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        //从标准输入读入字符串，排序后输出
        Integer[] a = new Integer[]{1,34,55,66,7};
        sort(a);
        assert isSort(a);
        show(a);
    }
}

• 排序成本模型：研究排序算法时，需要计算比较和交换的次数。对于不交换元素的算法，计算访问数组的次数。
• 额外内存使用：排序算法的额外内存开销和运行时间同等重要。排序算法可分两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其它排序算法。
• 数据类型：上述排序算法模板适用于任何实现了Comparable接口的数据类型。例如，Java中封装的Integer和Double，以及String和其他许多高级数据类型（如File和URL）都实现了Comparable接口，因此可以直接调用这些类型的数组作为参数调用我们自己实现的排序方法。

例如——用快排对N个随机的Double数据进行排序：

Doulbe[] a = new Double[N];
for(int i = 0; i < N; i++){
    a[i] = StdRandom.uniform();
    Quick.sort(a);
}

在创建自己的数据类型时，只要实现Comparable接口并实现该接口中的compareTo()方法，来定义目标类型对象的自然次序，如：

public class MyDate implements Comparable<MyDate>{
    private final int day;
    private final int month;
    private final int year;
    public MyDate(int d, int m, int y){
        day = d;
        month = m;
        year = y;
    }
    public int compareTo(MyDate that){
        if(year > that.year) return +1;
        if(year < that.year) return -1;
        if(month > that.month) return +1;
        if(month < that.month) return -1;
        if(day > that.day) return +1;
        if(day < that.day) return -1;
        return 0;
    }
}

对于 v < w、v = w 和 v > w 三种情况，Java习惯是在v.compareTo(w)被调用时分别返回一个负整数、零和一个正整数（-1、0和1）。一般来说，若 v 和 w 无法比较或者两者之一是 null，v.compareTo(w) 将会抛出一个异常。

1.1 选择排序

选择排序：首先找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素最小就和自己交换）。再次，在剩下元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断选择剩余元素中的最小者。

less()、exch()和isSort()的实现见排序算法类的模板

public class Selection {
    public static void sort(Comparable[] a) {
        //将a[]按升序排列
        int N = a.length;
        for (int i = 0; i < N; i++) {
            //将a[i] 和 a[i+1...N]中的最小元素交换
            int min = i;//最小元素索引
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            exch(a, i, min);
        }
    }
    public static void main(String[] args) {
        //从标准输入读入字符串，排序后输出
        Integer[] a = new Integer[]{1,354,55,66,7};
        sort(a);
        assert isSort(a):"Error Information...";
        show(a);
    }
}

选择排序内循环只是在比较当前元素与目前已知最小元素（以及将当前索引加1和检查是否代码越界），交换元素的代码写到了内循环之外，每次交换都能排定一个元素，因此交换总次数是N。所以算法总的时间效率取决于比较次数。

• 长度为 N 的数组，选择排序需要大约 $\frac{N^2}{2}$ 次比较和 N 次交换

0 到 N-1 的任意 i 都会进行一次交换和 N-1-i 次比较，因此总共有 N 次交换以及$(N-1)+(N-2)+…+2+1=\frac{N(N-1)}{2} \sim \frac{N^2}{2}$次比较

• 选择排序有两个鲜明特点：

1. 运行时间和输入无关。为了找出最小元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种情况在某些情况下是缺点，因为一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长，而其它算法更善于利用输入的初始状态。
2. 数据移动最少。每次交换都会改变两个数组元素的值，因此选择排序用了N次交换——交换次数和数组大小是线性关系，而其它任何算法都不具备这个特征（大部分增长数量级都是线性对数或平方级别）。

1.2 插入排序

插入排序：整理扑克时一般都是一张一张来，将每张牌插入到其它已经有序的牌中的适当位置。在计算机实现中，为了要给插入元素腾出空间，需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

• 与选择排序一样，当前索引左边所有元素都是有序的，但它们最终位置还不确定，为了给更小元素腾出空间，它们可能会被移动，但当索引到达数组右端时，数组排序就完成了。
• 与选择排序不同的是，插入排序所需时间取决于输入中元素的初始顺序。如对接近有序的数组排序要比随机数组快很多。

对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~$\frac{N^2}{4}$次比较以及~$\frac{N^2}{4}$次交换。最坏情况下需要~$\frac{N^2}{2}$次比较和~$\frac{N^2}{2}$次交换，最好情况下需要N-1次比较和0次交换。

public class Insertion{
    //第1种实现
    public static void sort1(Comparable[] a){
        int N = a.length;
        for(int i = 1; i < N; i++){
            for(int j = i; j > 0 && less(a[j], a[j - 1]); j--){
                exch(a, j, j - 1);
            }
        }
    }
    // 第2种实现
    public static void sort2(Comparable[] a){
        int N = a.length, j;
        for(int i = 1; i < N; i++){
            Comparable key = a[i];
            j = i - 1;
            //注意 j >= 0
            while(j >= 0 && less(key, a[i])){
                a[j + 1] = a[j];
                j -= 1;
            }
            a[j + 1] = key;
        }
    }
}

考虑一般情况下部分有序的数组。倒置指的是数组中两个顺序颠倒的元素。比如EXAMPLE中有11对倒置：E-A,X-A,X-M,X-P,X-L,X-E,M-L,M-E,P-L,P-E和L-E。若数组中倒置的数量小于数组大小的某个倍数，则这个数组是部分有序。插入排序对这样的数组很有效，事实上，当倒置数量很小时，插入排序可能比其它任何算法都快。

插入排序的交换操作和数组中倒置数量相同，需要比较的次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。要大幅提高插入排序速度并不难，只需在内循环中将较大元素都向右移而不总是交换两个元素（这样访问数组次数就能减半），即上述第2种实现。

1.3 希尔排序

希尔排序：是一种基于插入排序的排序算法。对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，若最小元素在数组末尾，则对其需要移动N-1次。希尔排序改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

• h有序数组：数组中任意间隔为 h 的元素都有序。即一个 h有序数组 就是 h 个互相独立的有序数组编织在一起组成的一个数组。若h很大，则可将元素移到很远位置，为实现更小的h有序创造方便。

public class Shell{
    //第1种实现
    public static void sort1(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++) {
                //注意 j >= h
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h /= 3;
        }
    }
    //less()、exch()和isSort()见排序算法类的模板

    //第2种实现
    public static void sort2(Comparable[] a) {
        int N = a.length;
        //初始化gap，逐步缩小gap，直到1
        for (int gap = N / 2; gap >= 1; gap /= 2) {
            //每组都从第gap个元素开始进行直接插入排序
            for (int i = gap; i < N; i++) {
                //插入排序
                Comparable key = a[i];
                int j = i - gap;
                //注意 j >= 0
                while (j >= 0 && less(key,a[j])){
                    a[j + gap] = a[j];
                    j -= gap;
                }
                a[j + gap] = key;
            }
        }
    }
}

算法实例解释可参考：
白话经典算法系列之三 希尔排序的实现
图解排序算法(二)之希尔排序

希尔排序更高效原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都适合插入排序。子数组部分有序的程度取决于递增序列的选择。

1.4 归并排序

归并排序：将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。归并排序将长度为N的数组排序所需时间和$NlogN$成正比；所需额外空间和N成正比。

原地归并的抽象方法——merge()

public static void merge(Comparable[] a, int lo, int mid, int hi){
    //将 a[lo...mid] 和 a[mid...hi] 归并
    int i = lo, j = mid + 1;
    //将 a[lo...hi] 复制到 aux[lo...hi]
    for(int k = lo; k <= hi; k++){
        aux[k] = a[k];
    }
    //归并回到 a[lo...aux]
    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[i], aux[j])){
            a[k] = a[i++];
        }else{
            a[k] = a[j++];
        }
    }
}

上述方法将所有元素复制到一个辅助数组aux[]中，再把归并结果放回原数组a[]中。方法在归并时（第二个for循环）进行了4个判断：左半边用尽（取右半边元素）、右半边用尽（取左半边元素）、左半边的当前元素小于右半边的当前元素（取左半边元素）以及右半边的当前元素小于左半边的当前元素（取右半边元素）

自顶向下的归并排序

public class Merge extends Example {
    //归并所需辅助数组
    private static Comparable[] aux;
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        //将a[]复制到aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        //注意：比较元素都用aux[]
        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++];
            }
        }
    }
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 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);
    }
    public static void main(String[] args) {
        //从标准输入读入字符串，排序后输出
        Integer[] a = new Integer[]{49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
        sort(a);
        assert isSort(a) : "Error Information...";
        show(a);
    }
}

1. 对于长度为N的数组，自顶向下的归并排序需要 $\frac{1}{2}NlogN$ 至 $NlogN$ 次比较
2. 对于长度为N的数组，自顶向下的归并排序最多需要访问数组 $6NlogN$次

归并排序所需时间和 $NlogN$ 成正比，主要缺点是辅助数组所使用的额外空间和N的大小成正比。

归并改进：

• 对小规模数组使用插入排序。使用插入排序处理小规模的子数组，一般可以将归并排序运行时间缩短10%~15%。
• 测试数组是否已经有序。添加一个判断条件，若 a[mid] <= a[mid + 1] 则认为数组已经有序并跳过 merge() 方法。这个改动不影响排序的递归调用，但任意有序的子数组算法的运行时间就变为线性了。
• 不将元素复制到辅助数组。可以节省元素复制到辅助数组所用时间（但空间不行），此时需调用两种排序方法，一种从输入数组排序到辅助数组，一种从辅助数组排序到输入数组，技巧是在递归调用的每个层次交换输入数组和辅助数组的角色。

自底向上的归并排序

先归并微型数组，然后再成对归并得到的子数组，直到将整个数组归并到一起，这比标准递归方法所需代码量少。首先是两两归并（每个元素是大小为1的数组），然后四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后是八八归并…

public static void sort(Comparable[] a) {
    int N = a.length;
    aux = new Comparable[N];
    //sz 子数组大小
    for (int sz = 1; sz < N; sz += sz) {
        //lo 子数组索引
        for (int lo = 0; lo < N - sz; lo += sz + sz) {
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
        }
    }
}

自底向上归并排序会多次遍历整个数组，根据子数组大小进行两两归并，子数组大小sz初始值为1，每次加倍。最后一个子数组大小只有在数组大小是sz的偶数倍时才等于sz（否则会比sz小）。

长度为N的数组，自底向上的归并排序需 $\frac{1}{2}NlogN$ 至 $NlogN$ 次比较，最多访问数组 $6NlogN$ 次。

• 当数组长度为2的幂时，自顶向下和自底向上归并排序所用比较和访问次数相同，只是顺序不同。
• 自底向上归并排序适合用链表组织数据。此方法只需重新组织链表连接就能将链表原地排序（不需创建任何新的链表节点）。

用自顶向下或自底向上方式实现任何分治算法都很自然。归并排序说明，当能用一种“化整为零”方法解决时可以试试另一种“循序渐进”的方法。

排序算法的复杂度

研究复杂度的第一步是建立一个计算模型。对排序来说，基于比较的算法对数组操作方式是由主键比较决定。

没有任何基于比较的算法能保证使用少于 $log(N!) \sim NlogN$ 次比较将长度为N的数组排序
归并排序是一种渐进最优的基于比较排序的算法。归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是$\sim NogN$。

Q&A

1. 归并排序比希尔排序快吗？
   在实际应用中，它们运行时间差距在常数级别。
2. 为什么不把数组aux[]声明为merge()方法的局部变量？
   为避免每次归并时，即使归并很小的数组都创建一个新数组，否则创建新数组将成为归并排序运行时间主要部分。更好的方法是将aux[]变为sort()方法的局部变量，并作为参数传给merge()方法。
3. 当数组中存在重复元素时归并排序性能如何？
   若所有元素相同，则归并排序运行时间是线性的。若有多个不同重复值，运行时间是线性对数的（和所有元素都不重复满足相同循环条件）。

1.5 快速排序

快速排序特点包括原地排序（只需一个很小的辅助栈），且将长度为 N 的数组排序所需时间和 $NlogN$ 成正比，内循环比大多数排序算法都要短小。

快速排序：是一种分治排序算法。将一个数组分成两个子数组，将两部分独立地排序。快排和归并排序是互补的，归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；快排的排序方式是当两个子数组都有序时整个数组也自然有序了。前者的递归调用发生在处理整个数组之前；后者递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快排中，切分位置取决于数组的内容。

public class Quick extends Example {
    public static void sort(Comparable[] a) {
        //消除对输入的依赖
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);
        //将左半部分a[lo...j-1]排序
        sort(a, lo, j - 1);
        //将右半部分a[j+1...hi]排序
        sort(a, j + 1, hi);
    }
    private static int partition(Comparable[] a, int lo, int hi) {
        //将数组切分成a[lo...i-1], a[i], a[i+1...hi]
        //左右扫描指针
        int i = lo, j = hi + 1;
        //切分元素
        Comparable v = a[lo];
        while (true) {
            //扫描左右，检查扫描是否结束并交换元素
            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }
            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exch(a, i, j);
        }
        //将v = a[j]放入正确的位置
        exch(a, lo, j);
        //a[lo...j-1] <= a[j] <= a[j+1...hi]
        return j;
    }
}

快速排序最多需 $\frac{N^2}{2}$ 次比较，但随即打乱数组能预防这种情况。每次切分后两子数组之一总是空的情况下比较次数为：$N+(N-1)+…+1=\frac{N(N+1)}{2}$，此时时间是平方级别的，空间是线性的。

快排改进

• 切换到插入排序。对于小数组，快排比插入排序慢；因为递归，快排的sort()方法在小数组中也会调用自己。因此在排序小数组时可切换到插入排序——将sort()中的 if (hi <= lo) return; 改为 if (hi <= lo + M){Insertion.sort(a, lo, hi); return;}，M 最佳值和系统相关，5~15之间通常较好。
• 三取样切分。使用子数组的一小部分元素的中位数来切分数组，这样切分更好，代价是需计算中位数。
• 熵最优的排序。实际应用经常出现含有大量重复元素的数组，一个元素全部重复的子数组就不需要继续排序了，但之前的算法还会继续切分成更小的数组。简单的解决方法是将数组切分为三部分（详见Dijkstra三向切分），分别对应小于、等于和大于切分元素的数组元素，这种比目前二分更复杂，相关问题有荷兰国旗问题。

1. a[i] 小于 v，将 a[lt] 和 a[i] 交换，将 lt 和 i 加一
2. a[i] 大于 v，将 a[gt] 和 a[i] 交换，将 gt减一
3. a[i] 等于 v，将 i 加一

这些操作都会保证数组元素不变且缩小 gt-i 的值（这样循环才会结束）。下面是三向切分的具体实现：

public class Quick3way{
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo){
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp < 0){
                exch(a, lt++, i++);
            }else if (cmp > 0){
                exch(a, i , gt--);
            }else {
                i++;
            }
            sort(a, lo, lt - 1);
            sort(a, gt + 1, hi);
        }
    }
}

对于只有若干不同主键的随机数组，归并排序时间复杂度是线性对数，而三向切分快排是线性的。对于任意分布的输入，最优的基于比较的算法平均所需比较次数和三向切分快排平均所需比较次数相互处于常数因子范围内。

《算法导论》上的快排

快排普通版本

public class QuickInCLRS extends Example {
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);
            sort(a, p, q - 1);
            sort(a, q + 1, r);
        }
    }
    private static int partition(Comparable[] a, int p, int r) {
        Comparable x = a[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (less(a[j], x)) {
                i++;
                exch(a, i, j);
            }
        }
        exch(a, i + 1, r);
        return i + 1;
    }
}

快排随机化版本

引入随机性，可以使算法对于所有的输入都能获得较好的期望性能。在快排中采用随机抽样的随机化技术——从子数组 A[p...r] 中随机选择一个元素作为主元。为此，可以将 A[r] 与从 A[p...r] 中随机选出的一个元素交换来保证主元 x = A[r] 是等概率地从子数组的 r-p+1 个元素中获取的。因为主元是随机选的，期望在平均情况下对输入数组的划分是比较均衡的。

public class RandomQuickInCLRS extends QuickInCLRS {
    private static Random random = new Random();
    private static void sort(Comparable[] a, int p, int r) {
        if (p < r) {
            int q = randomPartition(a, p, r);
            sort(a, p, q - 1);
            sort(a, q + 1, r);
        }
    }
    private static int randomPartition(Comparable[] a, int p, int r) {
        //随机选取主元，这里是获取其位置
        int j = random.nextInt(r) + p;
        //随机选出的主元与a[r]交换
        exch(a, j, r);
        return partition(a, p, r);
    }
}

快排时间复杂度

• 最坏情况：
  当划分产生的两个子问题分别包含了 n-1 个和 0 个元素时，划分时间复杂度为 $\Theta(n)$，因为对一个大小为0的数组进行递归调用会直接返回，因此$T(0)=\Theta(1)$，于是算法运行时间的递归式为：$T(n)=T(n-1)+T(0)+\Theta(n)=T(n-1)+\Theta(n)=\Theta(n^2)$。此外，在输入数组完全有序时，快排时间复杂度仍为 $\Theta(n^2)$，而插入排序则为 $\Theta(n)$。
• 最好情况：
  partition 得到的两个子问题规模都不大于$\frac{n}{2}$，子问题规模分别为 $\lfloor\frac{n}{2}\rfloor$和 $\lceil\frac{n}{2}\rceil-1$，此时算法运行时间递归式为：$T(n)=2T(\frac{n}{2})+\Theta(n)=\Theta(nlogn)$。
• 平衡的划分：
  快排平均运行时间更接近于最好情况，而非最坏情况。如按 9:1 划分，递归树如下： 只要划分是常数比例的，算法的运行时间总是 $O(nlogn)$。

随机化版本

1.6 优先队列

优先队列支持删除最大元素和插入元素。基于二叉堆的优先队列，是用数组保存元素并按照一定条件排序，以实现高效地（对数级别）删除最大元素和插入元素。优先队列实际应用包括模拟系统、任务调度和数值计算等。

通过插入一列元素然后一个个删除其中的最小元素，就可以用优先队列实现排序算法。堆排序来自于基于堆的优先队列的实现。

API

优先队列是一种抽象数据类型，表示了一组值和这些值的操作。优先队列最重要操作是删除最大元素和插入元素，

public class MaxPQ<Key extends Comparable<Key>>
        MaxPQ()             //创建一个优先队列
        MaxPQ(int max)      //创建一个最大容量为 max 的优先队列
        MaxPQ(Key[] a)      //用a[]中的元素创建一个优先队列
        void insert(Key v)  //插入元素
        Key max()           //返回最大元素
        Key delMax()        //删除并返回最大元素
        boolean isEmpty()   //返回队列是否为空
        int size()          //返回优先队列中的元素个数

优先队列的调用示例

一个优先队列的用例

public static void main(String[] args){
    //打印输入流中最大的M行
    int M = Integer.parseInt(args[0]);
    MinPQ<Transaction> pq = new MinPQ<Transaction>(M + 1);
    while(StdIn.hasNextLine()){
        //为下一行输入创建一个元素并放入优先队列中
        pq.insert(new Transaction(StdIn.readLine()));
        //最大的M个元素都在优先队列中
        if(pq.size() > M){
            //若优先队列中存在M+1个元素则删除最小的元素
            pq.delMin();
        }
    }
    Stack<Transaction> stack = new Stack<Transaction>();
    while(!pq.isEmpty()){
        stack.push(pq.delMin());
    }
    for(Transaction t : stack){
        StdOut.println(t);
    }
}

初级实现

堆的定义

在二叉堆数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置元素又至少大于等于数组中另两个元素。
堆有序：一棵二叉树的每个结点都大于等于它的两个子结点，根结点是堆有序的二叉树中的最大结点。

二叉堆表示法

若用指针表示堆有序的二叉树，则每个元素都需三个指针来找它的父节点和两个子节点。但若用完全二叉树，则可只用数组而不需指针。具体方法是将二叉树的节点按层级顺序放入数组，根节点在位置1，其子节点在位置2和3，而子节点的子节点分别在位置4,、5、6和7。

二叉堆是一组能用堆有序的完全二叉树排序的元素，并在数组中按层级存储（不用数组第一个位置）

在一个堆（后文都指二叉堆），位置 k 的节点的父节点在 $\lfloor\frac{k}{2}\rfloor$，两个子节点分别为 2k 和 2k+1。

一棵大小为 N 的完全二叉树的高度为 $\lfloor logN\rfloor$

堆的算法

堆实现的比较和交换方法：

private boolean less(int i, int j){
    return pq[i].compareTo(pa[j]) < 0;
}
private void exch(int i, int j){
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}

由下至上的堆有序化（上浮）

若堆的有状态因某个节点变得比它的父节点更大而被打破，则需通过交换它和它的父节点来修复堆。交换后，该节点比它的两个子节点都大。重复该过程，直到遇到更大的父节点。

private void swim(int k){
    while(k > 1 && less(k/2, k)){
        exch(k/2, k);
        k = k/2;
    }
}

由上至下的堆有序化（下沉）

若堆的有序状态因某个节点比它的两个子节点或其中之一更小而被打破，则可通过将它和它的两个子节点较大者交换来恢复堆。重复该过程，直到它的子节点都比它更小或到达了堆的底部。

private void sink(int k){
    while(2*k <= N){
        int j = 2*k;
        if(j < N && less(j, j+1)){
            j++;
        }
        if(!less(k, j)){
            break;
        }
        exch(k, j);
        k = j;
    }
}

插入元素：将新元素加到数组末尾，增加堆的大小并让该新元素上浮到合适位置。

删除最大元素：从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适位置。

• 基于堆的优先队列

public class MaxPQ<Key extends Comparable<Key>> {
    /**
     * 基于堆的完全二叉树
     */
    private Key[] pq;
    /**
     * 存储于pq[1...N]中，pq[0]没有使用
     */
    private int N = 0;
    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN + 1];
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }
    public Key delMax() {
        //从根节点得到最大元素
        Key max = pq[1];
        //pq[1] = pq[N--];
        //将其和最后一个节点交换
        exch(1, N--);
        //防止越界
        pq[N + 1] = null;
        sink(1);
        return max;
    }
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }
    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(j, j + 1)) {
                j++;
            }
            if (!less(k, j)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }
    private void show(){
        Stack<Key> stack = new Stack<>();
        while(!isEmpty()){
            stack.push(delMax());
        }
        for(Key t : stack){
            System.out.println(t);
        }
    }
     public static void main(String[] args) {
//        int[] a = new int[]{1,100,1,1, 26, 1,100,13, 27, 49, 55, 4};
        int[] a = new int[]{ 2 ,8, 2, 4, 3, 5, 2, 4};
         MaxPQ<Integer> maxPQ =  new MaxPQ<>(a.length);
         for (int i = 0; i < a.length; i++) {
            maxPQ.insert(a[i]);
         }
         maxPQ.show();
    }
}

命题：对于一个含有 N 个元素的基于堆的优先队列，插入元素操作只需不超过 $lgN+1$ 次比较，删除最大元素操作需要不超过 $2lgN$ 次比较。
证明：两种操作都需要在根节点和堆底之间移动元素，而路径长度不超过 $lgN$。对于路径上的每个节点，删除最大元素需要两次比较（除了堆底元素），一次用来找出较大的子节点，一次用来确定该子节点是否需要上浮。

多叉堆

完全三叉堆：对于数组中1至 N 的 N 个元素，位置 k 的节点大于等于位于 $3k-1、3k$ 和 $3k+1$ 的节点，小于等于位于 $\lfloor\frac{k+1}{3}\rfloor$的节点。需要在树高 $log_dN$ 和在每个节点的 d 个子节点找到最大者的代价之间找到折中，这取决于实现细节以及不同操作的预期相对频繁程度。

调整数组大小

添加一个没有参数的构造函数，在 insert() 中添加将数组长度加倍的代码，在 delMax() 中添加将数组长度减半的代码。

堆排序

可以把任意优先队列变成一种排序方法，将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作按顺序删除。用无序数组实现优先队列这么做相当于进行一次插入排序，用堆实现得到堆排序。堆排序分两个阶段：

• 堆的构造：将原始数组重新组织安排进一个堆中。
• 下沉排序：从堆中按递减顺序取出所有元素并得到排序结果。

堆的构造

连续向优先队列插入元素可行，但更高效的方法是从右到左用 sink() 函数构造子堆。数组每个位置都已经是一个子堆的根节点了，sink() 对于这些子堆也适用。若一个节点的两个子节点都已经是堆了，则在该节点上调用 sink() 可将它们变成一个堆。开始时只需扫描数组中一半元素，因为可以跳过大小为1的子堆。最后在位置1上调用 sink() 方法，扫描结束。在排序第一阶段，堆的构造方法和我们潜意识想象的不同，因为我们目标是构造一个堆有序的数组并使最大元素位于数组的开头（次大的元素在附近）而非构造函数结束的末尾。

用下沉操作由 N 个元素构造堆只需少于 2N 次比较以及少于 N 次交换

下沉排序

将堆中最大元素删除，然后放入堆缩小后数组中空出的位置，该过程和选择排序类似（按降序而非升序取出所有元素），但因为堆提供了一种从未排序部分找到最大元素的有效办法，所需比较次数少得多。

public static void sort(Comparable[] a){
    //构造堆
    int N = a.length;
    for(int k = N/2; k >= 1; k--){
        sink(a, k, N);
    }
    //下沉排序
    while(N > 1){
        exch(a, 1, N--);
        sink(a, 1, N);
    }
}

将N个元素排序，堆排序只需少于 2NlgN+2N 次比较（以及一半次数的交换），2N 项来自于堆的构造，2NlgN 来自于每次下沉操作最大可能需要 2lgN 次比较。

改进：先下沉后上浮

大多数在下沉排序期间重新插入堆的元素会被直接加入堆底。Floyd 1964 年发现可以通过免去检查元素是否到达正确位置来节省时间。在下沉中总是直接提升较大的子节点直至到达堆底，然后再使元素上浮到正确位置，这样可以将比较次数减少一半——接近了归并排序所需比较次数（随机数组）。该方法需额外空间，因此实际应用中只有当比较操作代价比较高时才用（例如：将字符串或其它键值较长类型的元素排序时）。

堆排序在排序复杂性研究中有重要地位，因为它是唯一能同时最优地利用空间和时间的方法——最坏情况下能保证使用 ~2NlgN 次比较和恒定的额外空间。当空间十分紧张时（如嵌入式系统或低成本移动设备）很流行，因为它只用几行就能实现较好的性能（甚至机器码也是）。但现代系统很少用，因为它无法利用缓存。数组元素很少和相邻的其它元素比较，因此缓存未命中的次数要远高于大多数比较都在相邻元素间进行的算法，如快排、归并排序、甚至是希尔排序。

在大数据量下，要处理 TopK 和 Multiway 问题，无法排序（或无法全装进内存），如 10 亿元素中选最大 10 个，则只用一个能存储十个元素的队列即可。

1.7 排序算法和优先队列的应用

将各种数据排序

前面实现的排序对象是由实现了Comparable接口的对象组成的数组，这样可以利用 Java 的回调机制将任意实现了 Comparable接口的数据类型排序。实现Comparable接口只需定义一个compareTo()函数并在其中定义该数据类型的大小关系。Java 中的 String、Integer、Double、File 和 URL都实现了Comparable接口。

指针排序

前面使用的方法被称为指针排序，因为只处理元素的引用而不移动数据本身。在C/C++中，需要明确指出操作的是数据还是指向数据的指针，在 Java 中，指针的操作是隐式的。除了原始数字类型外，操作的总是数据的引用（指针）而非数据本身。

不可变的键

若排序后用例还能修改键值，那么数组就不再有序了。Java 中可用不可变数据类型作为键来避免该问题，如String、Integer、Double和 File 都是不可变的。

廉价的交换

使用引用另一个好处是可以不必移动整个元素。对于元素大而键小的数组来说节约是巨大的，因为比较只需访问元素一小部分，而排序过程大部分元素都不会被访问到。对于几乎任意大小的元素，引用在一般情况下交换成本和比较成本几乎相同（代价是需要额外空间存储引用）。

多种排序方法

Java 的 Comparator 接口允许在一个类中实现多种排序方法。它只有一个 compare() 方法来比较两个对象，用 Comparator 接口代替Comparable接口可以将数据类型定义和两个该数据类型的比较的定义区分开。例如 Insertion.sort(a, String.CASE_INSENSITIVE_ORDER)，对 Transaction 对象数组按时间排序 Insertion.sort(a, new Transaction.WhenOrder())，按金额排序 Insertion.sort(a, new Transaction.HowMuchOrder()) 等。sort() 方法每次都会回调 Transaction 类中的用例指定的 compare() 方法，为避免每次排序都创建新的 Comparator 对象，使用 public final 来定义这些比较器（就像使用 String.CASE_INSENSITIVE_ORDER 一样）

public static void sort(Object[] a, Comparator c){
    int N = a.length;
    for(int i = 1; i < N; i++){
        for(int j  = i; j > 0 && less(c, a[j], a[j-1]);j--){
            exch(a, j, j-1);
        }
    }
}
private static boolean less(Comparator c, Object v, Object w){
    return c.compare(v, w) < 0;
}
private static void exch(Object[] a, int i, int j){
    Object t = a[i];
    a[i] = a[j];
    a[j] = t;
}

使用比较器实现优先队列

• 为 MaxPQ 添加一个实例变量 comparator 以及一个构造函数，该构造函数接受一个比较器作为参数并用它将 comparator 初始化。
• 在 less() 中检查 comparator 属性是否为 null（如果不是就用它比较）

使用了 Comparator 的插入排序：

public class Transaction{
    private final String who;
    private final Date when;
    private final Double amount;
    public static class WhoOrder implements Comparator<Transaction>{
        public int compare(Transaction v, Transaction w){
            return v.who.compareTo(w.who);
        }
    }
    public static class WhenOrder implements Comparator<Transaction>{
        public int compare(Transaction v, Transaction w){
            return v.when.compareTo(w.when);
        }
    }
    public static class HowMuchOrder implements Comparator<Transaction>{
        public int compare(Transaction v, Transaction w){
            if(v.amount < w.amount) return -1;
            if(v.amount > w.amount) return 1;
            return 0;
        }
    }
}

稳定性

若一个排序算法能保留数组中重复元素的相对位置则可被称为稳定的。一部分算法是稳定的——插入排序和归并排序，但选择排序、希尔排序、快速排序和堆排序不稳定。

该用哪种排序

快排是最快的通用排序算法

问题规约

在使用解决问题 B 的方法来解决问题 A 时，都在将 A 规约为 B。

找出重复元素

在一个 Comparable 对象的数组中是否存在重复元素？有多少重复元素？哪个值出现最频繁？

通过两两比较可以在平方级别解决，但通过排序可在线性对数时间内解决。

Quick.sort(a);
int count = 1;
for(int i = 1; i < a.length; i++){
    if(a[i].compareTo(a[i-1])!=0){
        count++;
    }
}

排名

逆序对数问题

中位数与顺序统计

一个和排序有关但又不需要完全的重要应用就是找出一组元素的中位数，有一种特殊选择：找到一组数中第 k 小的元素。通过前面的 TopM 问题用优先队列可以解决，或者排序后获取第 k 个元素也可以解决，但都是线性对数时间。实际上，当 k 很小或很大时可以在线性时间找到：

public static Comparable select(Comparable[] a, int k){
    StdRandom.suhffle(a);
    int lo = 0, hi = a.length - 1;
    while(hi > lo){
        int j = partition(a, lo, hi);
        if(j == k){
            return a[k];
        }else if(j > k){
            hi = j - 1;
        }else{
            lo = j + 1;
        }
    }
    return a[k];
}

不断切分知道子数组只含有第 k 个元素，此时 a[k] 含有最小的（k+1）个元素，a[0] 到 a[k-1] 都小于等于 a[k]，而 a[k+1] 及其后的元素都大于等于 a[k]。假设每次都正好将数组二分，则比较总次数是（N+N/2+N/4+…）直到找到第 k 个元素，根据等比数列求和公式该和显然小于 2N。

平均来说，基于切分的选择算法运行时间是线性级别的。

本篇介绍的算法的完整代码地址：
代码地址

以下是可供参考的博客：
各种排序算法时间复杂度
面试中的排序算法总结
八大排序算法
必须知道的八大种排序算法【java实现】
坐在马桶上看算法：快速排序