88必发最新手机客户端 27

算法(第四版)C88必发最新手机客户端#题解——2.2

写在前面

整个项目都托管在了 Github
上:https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp

查找更为方便的版本见:https://alg4.ikesnowy.com

这一节内容可能会用到的库文件有 Merge,同样在 Github 上可以找到。

善用 Ctrl + F 查找题目。

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) 将会抛出一个异常。

2.2.1

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 的数组,选择排序需要大约 (N^2) / 2 次比较和 N 次交换

0 到 N-1 的任意 i 都会进行一次交换和 N-1-i 次比较,因此总共有 N
次交换以及(N-1)+(N-2)+…+2+1 = N(N-1) / 2 ~ N^2 / 2次比较

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

按照本书开头所示轨迹的格式给出原地归并排序的抽象 merge()
方法是如何将数组 A E Q S U Y E I N O S T 排序的。

1.2 插入排序

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

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

对于随机排列的长度为N且主键不重复的数组,平均情况下插入排序需要 ~ N^2
/ 4$ 次比较以及~N^2 / 4 次交换。最坏情况下需要 ~ N^2 / 2 次比较和 ~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种实现。

解答

88必发最新手机客户端 1

 

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;
            }
        }
    }
}

算法实例解释可参考:
白话经典算法系列之三
希尔排序的实现

图解排序算法(二)之希尔排序

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

2.2.2

1.4 归并排序

归并排序:将一个数组排序,可以先(递归地)将它分成两半分别排序,然后将结果归并起来。归并排序将长度为N的数组排序所需时间和
NlogN 成正比;所需额外空间和 N 成正比。

题目

按照算法 2.4 所示轨迹的格式给出自顶向下的归并排序是如何将数组 E A S Y Q
U E S T I O 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个判断:左半边用尽(取右半边元素)、右半边用尽(取左半边元素)、左半边的当前元素小于右半边的当前元素(取左半边元素)以及右半边的当前元素小于左半边的当前元素(取右半边元素)

解答

88必发最新手机客户端 2

 

自顶向下的归并排序

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 的数组,自顶向下的归并排序需要 1/2NlogN 至 NlogN 次比较
  2. 对于长度为 N 的数组,自顶向下的归并排序最多需要访问数组 6NlogN 次

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

2.2.3

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

用自底向上的归并排序解答练习 2.2.2

自底向上的归并排序

先归并微型数组,然后再成对归并得到的子数组,直到将整个数组归并到一起,这比标准递归方法所需代码量少。首先是两两归并(每个元素是大小为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小)。

88必发最新手机客户端 3

自底向上的归并排序的归并结果

长度为 N 的数组,自底向上的归并排序需 1/2NlogN 至 NlogN
次比较,最多访问数组 6NlogN 次。

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

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

解答

88必发最新手机客户端 4

 

排序算法的复杂度

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

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

2.2.4

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;
    }
}

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

解答

是的,必须要两个子数组都有序时归并才能得到正确结果。
如果说数组不有序的话,那么最后只能得到两个数组的混合。
合并后的数组中,属于原有数组的元素的相对顺序不会被改变。
例如子数组 1 3 1 和 2 8 5 原地归并。
结果是 1 2 3 1 8 5,其中 1 3 1 和 2 8 5 的相对顺序不变。

 

快排改进

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

88必发最新手机客户端 5

三向切分示意图

  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);
        }
    }
}

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

2.2.5

《算法导论》上的快排

题目

当输入数组的大小 N=39
时,给出自顶向下和自底向上的归并排序中各次归并子数组的大小及顺序。

快排普通版本
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;
    }
}

88必发最新手机客户端 6

quicksort普通版本

解答

每次归并子数组的大小和顺序如下:

自顶向下

2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 3, 2, 5, 10, 20, 2, 3, 2, 5,
2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 2, 4, 9, 19, 39

自底向上

2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4,
4, 4, 4, 4, 3, 8, 8, 8, 8, 7, 16, 16, 32, 39

 

快排随机化版本

引入随机性,可以使算法对于所有的输入都能获得较好的期望性能。在快排中采用随机抽样的随机化技术——从子数组
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);
    }
}

2.2.6

快排时间复杂度

  • 最坏情况:
    当划分产生的两个子问题分别包含了 n-1 个和 0
    个元素时,划分时间复杂度为 O(n),因为对一个大小为 0
    的数组进行递归调用会直接返回,因此 T(0) =
    O(1),于是算法运行时间的递归式为:T(n) = T(n-1) + T(0) + O(n) =
    T(n-1)+O(n) = O(n^2)。此外,在输入数组完全有序时,快排时间复杂度仍为
    O(n^2),而插入排序则为 O(n)。

  • 最好情况:
    partition 得到的两个子问题规模都不大于 n / 2,子问题规模分别为 n / 2
    和 n / 2 – 1,此时算法运行时间递归式为:T(n) = 2T(n / 2) + O(n) =
    O(nlogn)。

  • 平衡的划分:
    快排平均运行时间更接近于最好情况,而非最坏情况。如按 9:1
    划分,递归树如下:

![](https://upload-images.jianshu.io/upload_images/137261-3798eaf0d152bb7c.png)

quicksort递归树

只要划分是常数比例的,算法的运行时间总是 O(nlogn)。
题目

编写一个程序来计算自顶向下和自底向上的归并排序访问数组的准确次数。
使用这个程序将 N=1 至 512 的结果绘成曲线图,并将其和上限 6NlgN 相比较。

随机化版本
解答

88必发最新手机客户端 7

灰色是上限,蓝点是自顶向下,红点是自底向上。
由于两种排序访问数组的次数是一样的,因此蓝点和红点重合。

1.6 优先队列

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

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

代码

给出绘图部分的代码:

using System;
using System.Windows.Forms;
using System.Drawing;
using Merge;

namespace _2._2._6
{
    /*
     * 2.2.6
     * 
     * 编写一个程序来计算自顶向下和自底向上的归并排序访问数组的准确次数。
     * 使用这个程序将 N=1 至 512 的结果绘成曲线图,
     * 并将其和上限 6NlgN 相比较。
     * 
     */
    static class Program
    {
        /// <summary>
        /// 应用程序的主入口点。
        /// </summary>
        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Compute();
            Application.Run(new Form1());
        }

        static void Compute()
        {
            MergeSort mergeSort = new MergeSort();
            MergeSortBU mergeSortBU = new MergeSortBU();
            int[] mergeResult = new int[10];
            int[] mergeResultBU = new int[10];
            int[] upperBound = new int[10];

            // 进行计算
            int dataSize = 1;
            for (int i = 0; i < 10; i++)
            {
                int[] dataMerge = SortCompare.GetRandomArrayInt(dataSize);
                int[] dataMergeBU = new int[dataSize];
                dataMerge.CopyTo(dataMergeBU, 0);

                mergeSort.ClearArrayVisitCount();
                mergeSortBU.ClearArrayVisitCount();
                mergeSort.Sort(dataMerge);
                mergeSortBU.Sort(dataMergeBU);

                mergeResult[i] = mergeSort.GetArrayVisitCount();
                mergeResultBU[i] = mergeSortBU.GetArrayVisitCount();
                upperBound[i] = (int)(6 * dataSize * Math.Log(dataSize, 2));

                dataSize *= 2;
            }

            // 绘图
            Form2 plot = new Form2();
            plot.Show();
            Graphics graphics = plot.CreateGraphics();

            // 获得绘图区矩形。
            RectangleF rect = plot.ClientRectangle;
            float unitX = rect.Width / 10;
            float unitY = rect.Width / 10;

            // 添加 10% 边距作为文字区域。
            RectangleF center = new RectangleF
                (rect.X + unitX, rect.Y + unitY,
                rect.Width - 2 * unitX, rect.Height - 2 * unitY);

            // 绘制坐标系。
            graphics.DrawLine(Pens.Black, center.Left, center.Top, center.Left, center.Bottom);
            graphics.DrawLine(Pens.Black, center.Left, center.Bottom, center.Right, center.Bottom);
            graphics.DrawString("28000", plot.Font, Brushes.Black, rect.Location);
            graphics.DrawString("1024", plot.Font, Brushes.Black, center.Right, center.Bottom);
            graphics.DrawString("0", plot.Font, Brushes.Black, rect.Left, center.Bottom);

            // 初始化点。
            PointF[] grayPoints = new PointF[10]; // 上限
            PointF[] redPoints = new PointF[10];  // 自顶向下
            PointF[] bluePoints = new PointF[10]; // 自底向上
            unitX = center.Width / 11.0f;
            unitY = center.Height / 28000.0f;

            for (int i = 0; i < 10; i++)
            {
                grayPoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (upperBound[i] * unitY) - 10);
                redPoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (mergeResult[i] * unitY) - 10);
                bluePoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (mergeResultBU[i] * unitY) - 10);
            }

            // 绘制点。
            for (int i = 0; i < 10; i++)
            {
                graphics.FillEllipse(Brushes.Gray, new RectangleF(grayPoints[i], new SizeF(10, 10)));
                graphics.FillEllipse(Brushes.Red, new RectangleF(redPoints[i], new SizeF(10, 10)));
                graphics.FillEllipse(Brushes.Blue, new RectangleF(bluePoints[i], new Size(10, 10)));
            }

            graphics.Dispose();
        }
    }
}

 

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()          //返回优先队列中的元素个数

2.2.7

优先队列的调用示例

一个优先队列的用例

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);
    }
}
题目

证明归并排序的比较次数是单调递增的(即对于 N>0,C(N+1)>C(N))。

初级实现

88必发最新手机客户端 8

从N个输入找到最大M个元素.png

解答

根据书本给出的命题 G 和命题 H(中文版 P173/176,英文版 P275/279),
比较次数的下限 C(N) = 1/2 * NlgN
N 和 lgN 都是单调递增且大于零的(N>1),因此 C(N) 也是单调递增的

 

堆的定义

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

2.2.8

二叉堆表示法

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

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

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

88必发最新手机客户端 9

堆的表示

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

题目

假设将算法 2.4 修改为:
只要 a[mid] <= a[mid+1] 就不调用 merge() 方法,
请证明用归并排序处理一个已经有序的数组所需的比较次数是线性级别的。

堆的算法

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

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;
}
解答

修改后的算法对已经有序的情况做了优化
数组对半切分并排序后,
如果 a[mid] < a[mid +
1](左半部分的最后一个元素小于右半部分的第一个元素)
那么我们可以直接合并数组,不需要再做多余的操作

现在的输入是一个已经排序的数组
算法唯一的比较发生在判断 a[mid] < a[mid + 1] 这个条件时
假定数组有 N 个元素
比较次数满足 T(N) = 2 * T(N / 2) + 1, T(1) = 0
转化为非递归形式即为:T(N) = cN / 2 + N – 1
其中 c 为任意正整数

 

由下至上的堆有序化(上浮)

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

88必发最新手机客户端 10

上浮

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

2.2.9

由上至下的堆有序化(下沉)

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

88必发最新手机客户端 11

下沉

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;
    }
}

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

88必发最新手机客户端 12

插入元素

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

88必发最新手机客户端 13

删除最大元素

  • 基于堆的优先队列

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。对于路径上的每个节点,删除最大元素需要两次比较(除了堆底元素),一次用来找出较大的子节点,一次用来确定该子节点是否需要上浮。

题目

在库函数中使用 aux[] 这样的静态数组时不妥当的,
因为可能会有多个程序同时使用这个类。
实现一个不用静态数组的 Merge 类,
但也不要将 aux[] 变为 merge() 的局部变量(请见本书的答疑部分)。
提示:可以将辅助数组作为参数传递给递归的 sort() 方法。

多叉堆

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

解答

官方给出的归并排序实现中在 Sort 方法里初始化了 aux 数组。
源码见:https://algs4.cs.princeton.edu/22mergesort/Merge.java.html

C#实现和官方的实现非常类似,

首先定义只接受一个参数的公开 Sort 方法,在这个方法里面初始化 aux
数组。

/// <summary>
/// 利用归并排序将数组按升序排序。
/// </summary>
/// <typeparam name="T">数组元素类型。</typeparam>
/// <param name="a">待排序的数组。</param>
public override void Sort<T>(T[] a)
{
    T[] aux = new T[a.Length];
    Sort(a, aux, 0, a.Length - 1);
}

然后建立一个私有的递归 Sort 方法做实际的排序操作。

/// <summary>
/// 自顶向下地对数组指定范围内进行归并排序,需要辅助数组。
/// </summary>
/// <typeparam name="T">需要排序的元素类型。</typeparam>
/// <param name="a">原数组。</param>
/// <param name="aux">辅助数组。</param>
/// <param name="lo">排序范围起点。</param>
/// <param name="hi">排序范围终点。</param>
private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
{
    if (hi <= lo)
        return;
    int mid = lo + (hi - lo) / 2;
    Sort(a, aux, lo, mid);
    Sort(a, aux, mid + 1, hi);
    Merge(a, aux, lo, mid, hi);
}
调整数组大小

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

代码
using System;

namespace Merge
{
    /// <summary>
    /// 归并排序类。
    /// </summary>
    public class MergeSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSort() { }

        /// <summary>
        /// 利用归并排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];
            Sort(a, aux, 0, a.Length - 1);
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Sort(a, aux, lo, mid);
            Sort(a, aux, mid + 1, hi);
            Merge(a, aux, lo, mid, hi);
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T>
        {
            for (int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                {
                    a[k] = aux[j];
                    j++;
                }
                else if (j > hi)
                {
                    a[k] = aux[i];
                    i++;
                }
                else if (Less(aux[j], aux[i]))
                {
                    a[k] = aux[j];
                    j++;
                }
                else
                {
                    a[k] = aux[i];
                    i++;
                }
            }
        }
    }
}

 

堆排序

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

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

2.2.10

堆的构造

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

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

题目

快速归并。
实现一个 merge() 方法,按降序将 a[] 的后半部分复制到 aux[],
然后将其归并回 a[]
中。这样就可以去掉内循环中检测某半边是否用尽的代码。
注意:这样的排序产生的结果是不稳定的(请见 2.5.1.8 节)。

下沉排序

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

88必发最新手机客户端 14

堆的构造和下沉排序

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 次比较。

解答

官方同样给出了 java 实现,如下:

private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 

   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1];

   int i = lo, j = hi; 
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i])) a[k] = aux[j--];
      else                      a[k] = aux[i++];
}

C# 实现见代码部分。

改进:先下沉后上浮

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

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

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

代码
using System;
using Merge;

namespace _2._2._10
{
    /// <summary>
    /// 归并排序类。
    /// </summary>
    public class MergeSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSort() { }

        /// <summary>
        /// 利用归并排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];
            Sort(a, aux, 0, a.Length - 1);
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Sort(a, aux, lo, mid);
            Sort(a, aux, mid + 1, hi);
            Merge(a, aux, lo, mid, hi);
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T>
        {
            // 前半部分升序复制
            for (int k = lo; k <= mid; k++)
            {
                aux[k] = a[k];
            }
            // 后半部分降序复制
            for (int k = mid + 1; k <= hi; k++)
            {
                aux[k] = a[hi - k + mid + 1];
            }

            // i 指向最左端,j 指向最右端
            int i = lo, j = hi;
            for (int k = lo; k <= hi; k++)
            {
                if (Less(aux[j], aux[i]))
                {
                    a[k] = aux[j];
                    j--;
                }
                else
                {
                    a[k] = aux[i];
                    i++;
                }
            }
        }
    }
}

 

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

2.2.11

将各种数据排序

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

题目

改进。
实现 2.2.2 节所述的对归并排序的三项改进:
加快小数组的排序速度,
检测数组是否已经有序以及通过在递归中交换参数来避免复制。

指针排序

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

解答

官方实现见:https://algs4.cs.princeton.edu/22mergesort/MergeX.java.html

在 MergeSortX 类里添加一个 CUTOFF
字段,排序时如果数组长度小于它则直接调用插入排序进行排序。

在调用归并方法前判断第一个有序数组的最后一个元素是否大于第二个有序数组的第一个元素,
如果大于的话就不需要调用归并了,直接首尾相接即可。

每次归并都需要两个数组,一个用于存放归并结果,这个数组中的内容是无关紧要的;
另一个则保存了归并前的数组,用于实际的归并过程。
归并结束后,前一个数组变成归并后的有序结果(也就是下一次归并时的「归并前数组」),后一个数组中的内容则不再有用。
我们可以看到这两个数组的角色在下一次归并时正好可以互换。

要注意的是,归并次数总是一个奇数(左侧归并+右侧归并+总归并),因此在第一次调用
Sort 方法时应该把 aux 和 a 互换传入。

不可变的键

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

代码
using System;

namespace Merge
{
    /// <summary>
    /// 优化后的归并排序类。
    /// </summary>
    public class MergeSortX : BaseSort
    {
        /// <summary>
        /// 对小于 CUTOFF 的数组使用插入排序。
        /// </summary>
        private static int CUTOFF = 7;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSortX() { }

        /// <summary>
        /// 设置启用插入排序的阈值,小于该阈值的数组将采用插入排序。
        /// </summary>
        /// <param name="cutoff">新的阈值。</param>
        public void SetCutOff(int cutoff) => CUTOFF = cutoff;

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="src">原始数组。</param>
        /// <param name="dst">目标数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] src, T[] dst, int lo, int mid, int hi) where T : IComparable<T>
        {
            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                    dst[k] = src[j++];
                else if (j > hi)
                    dst[k] = src[i++];
                else if (Less(src[j], src[i]))
                    dst[k] = src[j++];
                else
                    dst[k] = src[i++];
            }
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="src">原数组。</param>
        /// <param name="dst">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] src, T[] dst, int lo, int hi) where T : IComparable<T>
        {
            // 小于 CUTOFF 的数组调用插入排序
            if (hi <= lo + CUTOFF)
            {
                InsertionSort insertion = new InsertionSort();
                insertion.Sort(dst, lo, hi);
                return;
            }
            int mid = lo + (hi - lo) / 2;
            // 交换辅助数组和原数组
            Sort(dst, src, lo, mid);
            Sort(dst, src, mid + 1, hi);
            // 已排序的数组直接合并
            if (!Less(src[mid + 1], src[mid]))
            {
                Array.Copy(src, lo, dst, lo, hi - lo + 1);
                return;
            }
            Merge(src, dst, lo, mid, hi);
        }

        /// <summary>
        /// 利用优化后的归并排序对数组 a 排序。
        /// </summary>
        /// <typeparam name="T">数组中的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];
            a.CopyTo(aux, 0);
            // aux 和 a 需要交换
            Sort(aux, a, 0, a.Length - 1);
        }
    }
}

 

廉价的交换

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

2.2.12

多种排序方法

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;
}
题目

次线性的额外空间。用大小 M 的数组分为 N/M 块(简单起见,设 M 是 N
的约数)。
实现一个归并方法,使之所需的额外空间减少到 max(M, N/M):
(i)可以先将一个块看作一个元素,将块的第一个元素作为块的主键,用选择排序将块排序;
(ii)遍历数组,将第一块和第二块归并,完成后将第二块和第三块归并,等等。

使用比较器实现优先队列
  • 为 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;
        }
    }
}
解答

中文版的翻译比较难理解
实际上就是另一种归并排序的实现方式
先把数组分成若干个大小为 M 的块
对于每个块,用选择排序进行排序
随后遍历数组,将各个块归并起来

稳定性

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

代码
using System;
using Merge;

namespace _2._2._12
{
    /// <summary>
    /// 归并排序类。
    /// </summary>
    public class MergeSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSort() { }

        /// <summary>
        /// 利用归并排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Sort(a, 1);
        }

        /// <summary>
        /// 利用分块法进行归并排序。
        /// </summary>
        /// <typeparam name="T">待排序的数组内容。</typeparam>
        /// <param name="a">待排序的数组。</param>
        /// <param name="M">分块大小。</param>
        public void Sort<T>(T[] a, int M) where T : IComparable<T>
        {
            int blockNum = a.Length / M;
            SelectionSort selection = new SelectionSort();
            // 对块进行选择排序。
            for (int i = 0; i < blockNum; i++)
            {
                int lo = i * M;
                int hi = (i + 1) * M - 1;
                selection.Sort(a, lo, hi);
            }
            // 将各个块合并。
            for (int i = 0; i < blockNum - 1; i++)
            {
                Merge(a, 0, (i + 1) * M - 1, (i + 2) * M - 1);
            }
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, int lo, int mid, int hi) where T : IComparable<T>
        {
            T[] aux = new T[hi - lo + 1];
            for (int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                {
                    a[k] = aux[j];
                    j++;
                }
                else if (j > hi)
                {
                    a[k] = aux[i];
                    i++;
                }
                else if (Less(aux[j], aux[i]))
                {
                    a[k] = aux[j];
                    j++;
                }
                else
                {
                    a[k] = aux[i];
                    i++;
                }
            }
        }
    }
}

 

该用哪种排序

88必发最新手机客户端 15

各种排序算法的性能特点

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

2.2.13

问题规约

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

题目

平均情况的下限。请证明任意基于比较的排序算法的预期比较次数至少为
~NlogN(假设输入元素的所有排列的出现概率是均等的)。
提示:比较次数至少是比较树的外部路径的长度(根结点到叶子结点的路径长度之和),当树平衡时该值最小。

找出重复元素

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

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

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

假设对三个数进行排序,这三个数是:35,10,17
三个数排序的决策树如下,结点代表比较对应位置上的数。
88必发最新手机客户端 16
对于 35,10,17 来说,路径遵循右、左、左,最后得到的结果就是 2 3
1(10,17,35)。
我们可以发现决策树上的每一个叶子节点都代表一种排列顺序,对于 N
个数,叶子节点就有 N! 个
根据二叉树的性质,高度为 h 的二叉树最多有 2^h 个叶子节点
那么,对于 N 个数,决策树的高度 h 的最小值可以通过下面这个式子得出来
2^h >= n!
h >= log(n!)
因此可以得到决策树高度 h 的最小值是 log(n!)

接下来我们来计算平均路径长度
我们令函数 H(k) 代表有 k 个叶子节点的平衡决策树的所有路径长度之和
上例中 H(6) = 2 + 2 + 3 + 3 + 3 + 3 = 16
由于平衡决策树的性质,H(k) = 2H(k / 2) + k
(加上 k 的原因:左右子树的高度比整个树的高度小
1,因此每条路径的长度都必须加 1,总共多加了 k 次)
因此 H(k) = klogk
现在令 k = n!
H(n!) = n!log(n!)
由于每次排序时我们只经过某一条路径(上例中我们只经过了右、左、左这条路径)
而且每种路径的出现概率相等
因此平均比较次数应该为 H(n!) / n! = log(n!) = nlog(n)
证明完毕

 

排名

逆序对数问题

2.2.14

中位数与顺序统计

一个和排序有关但又不需要完全的重要应用就是找出一组元素的中位数,有一种特殊选择:找到一组数中第
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实现】
坐在马桶上看算法:快速排序

题目

归并有序的队列。
编写一个静态方法,将两个有序的队列作为参数,返回一个归并后的有序队列。

解答

比较两个有序队列的第一个元素,取较小的一个出队并放入额外建立的队列中。
重复上述步骤直到两个队列都为空。

代码
/// <summary>
/// 归并两个有序队列。输入队列将被清空。
/// </summary>
/// <typeparam name="T">有序队列的元素类型。</typeparam>
/// <param name="a">需要归并的队列。</param>
/// <param name="b">需要归并的队列。</param>
/// <returns>归并后的新队列。</returns>
static Queue<T> Merge<T>(Queue<T> a, Queue<T> b) where T : IComparable<T>
{
    Queue<T> sortedQueue = new Queue<T>();
    while (!a.IsEmpty() && !b.IsEmpty())
    {
        if (a.Peek().CompareTo(b.Peek()) < 0)
            sortedQueue.Enqueue(a.Dequeue());
        else
            sortedQueue.Enqueue(b.Dequeue());
    }

    while (!a.IsEmpty())
        sortedQueue.Enqueue(a.Dequeue());
    while (!b.IsEmpty())
        sortedQueue.Enqueue(b.Dequeue());

    return sortedQueue;
}

 

2.2.15

题目

自底向上的有序队列归并排序。
用下面的方法编写一个自底向上的归并排序:
给定 N 个元素,创建 N 个队列,每个队列包含其中一个元素。
创建一个由这 N 个队列组成的队列,然后不断用练习 2.2.14
中的方法将队列的头两个元素归并,
并将结果重新加入到队列结尾,直到队列的队列只剩下一个元素为止。

解答

程序思路题目已经给出,按照题意实现即可。
Merge 方法可以直接使用前一题的实现。

代码
using System;

namespace _2._2._15
{
    /// <summary>
    /// 利用队列归并实现的自底向上的归并排序。
    /// </summary>
    class MergeSortQueue
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSortQueue() { }

        /// <summary>
        /// 利用队列归并进行自底向上的归并排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public void Sort<T>(T[] a) where T : IComparable<T>
        {
            Queue<Queue<T>> queueList = new Queue<Queue<T>>();
            for (int i = 0; i < a.Length; i++)
            {
                Queue<T> temp = new Queue<T>();
                temp.Enqueue(a[i]);
                queueList.Enqueue(temp);
            }

            while (queueList.Size() != 1)
            {
                int times = queueList.Size() / 2;
                for (int i = 0; i < times; i++)
                {
                    Queue<T> A = queueList.Dequeue();
                    Queue<T> B = queueList.Dequeue();
                    queueList.Enqueue(Merge(A, B));
                }
            }

            Queue<T> result = queueList.Dequeue();
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = result.Dequeue();
            }
        }

        /// <summary>
        /// 归并两个有序队列。输入队列将被清空。
        /// </summary>
        /// <typeparam name="T">有序队列的元素类型。</typeparam>
        /// <param name="a">需要归并的队列。</param>
        /// <param name="b">需要归并的队列。</param>
        /// <returns>归并后的新队列。</returns>
        public static Queue<T> Merge<T>(Queue<T> a, Queue<T> b) where T : IComparable<T>
        {
            Queue<T> sortedQueue = new Queue<T>();
            while (!a.IsEmpty() && !b.IsEmpty())
            {
                if (a.Peek().CompareTo(b.Peek()) < 0)
                    sortedQueue.Enqueue(a.Dequeue());
                else
                    sortedQueue.Enqueue(b.Dequeue());
            }

            while (!a.IsEmpty())
                sortedQueue.Enqueue(a.Dequeue());
            while (!b.IsEmpty())
                sortedQueue.Enqueue(b.Dequeue());

            return sortedQueue;
        }
    }
}

 

2.2.16

题目

自然的归并排序。
88必发最新手机客户端,编写一个自底向上的归并排序,当需要将两个子数组排序时能够利用数组中已经有序的部分。
首先找到一个有序的子数组(移动指针直到当前元素比上一个元素小为止),
然后再找出另一个并将它们归并。
根据数组大小和数组中递增子数组的最大长度分析算法的运行时间。

解答

自然归并排序的一个示例如下图所示:

88必发最新手机客户端 17
基本过程和自底向上的归并排序类似,只是每次归并的块大小不一定相同。

时间分析

88必发最新手机客户端 18

随着有序块的变大,排序耗时会缩短,但增长的数量级会变高(归并的平均块大小变大了)。

代码
using System;
using System.Diagnostics;

namespace Merge
{
    /// <summary>
    /// 自然的归并排序。
    /// </summary>
    public class MergeSortNatural : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSortNatural() { }

        /// <summary>
        /// 利用自然的归并排序进行自底向上的排序。
        /// </summary>
        /// <typeparam name="T">用于排序的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];

            while (true)
            {
                // 找到第一个块
                int lo = 0;
                int mid = FindBlock(lo, a) - 1;
                if (mid == a.Length - 1)
                    break;

                while (mid < a.Length - 1)
                {
                    int hi = FindBlock(mid + 1, a) + mid;
                    Merge(lo, mid, hi, a, aux);
                    lo = hi + 1;
                    mid = FindBlock(lo, a) + lo - 1;
                }
            }
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 将两个块归并。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="lo">第一个块的开始下标。</param>
        /// <param name="mid">第一个块的结束下标(第二个块的开始下标 - 1)。</param>
        /// <param name="hi">第二个块的结束下标。</param>
        /// <param name="a">需要归并的数组。</param>
        /// <param name="aux">辅助数组。</param>
        private void Merge<T>(int lo, int mid, int hi, T[] a, T[] aux) where T : IComparable<T>
        {
            for (int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                {
                    a[k] = aux[j];
                    j++;
                }
                else if (j > hi)
                {
                    a[k] = aux[i];
                    i++;
                }
                else if (Less(aux[j], aux[i]))
                {
                    a[k] = aux[j];
                    j++;
                }
                else
                {
                    a[k] = aux[i];
                    i++;
                }
            }
        }

        /// <summary>
        /// 获取下一个有序块。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="lo">查找起点。</param>
        /// <param name="a">用于查找的数组。</param>
        /// <returns>块的大小。</returns>
        private int FindBlock<T>(int lo, T[] a) where T : IComparable<T>
        {
            int size = 1;
            for (int i = lo; i < a.Length - 1; i++)
            {
                if (Less(a[i], a[i + 1]) || a[i].Equals(a[i + 1]))
                    size++;
                else
                    break;
            }
            return size;
        }
    }
}

 

2.2.17

题目

链表排序。
实现对链表的自然排序
(这是将链表排序的最好方法,因为它不需要额外的空间且运行时间是线性对数级别的)。

解答

排序方式和 2.2.16 十分类似,不再赘述,这里介绍一下归并方法。
88必发最新手机客户端 19
如 gif
图所示,先把要归并的两个链表拆出来,随后确定表头位置,然后进行归并即可。
归并结束后返回 first。

结果分析如下图所示:
88必发最新手机客户端 20
随着有序部分的增加,对于相同大小的数组自然归并排序的耗时会缩短。
对于有序部分相同的情况,随着数组大小的倍增,耗时呈现了O(nlogn)的趋势。

代码
using System;
using System.Diagnostics;
using Merge;

namespace _2._2._17
{
    /// <summary>
    /// 自然的归并排序。
    /// </summary>
    public class MergeSortNatural : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSortNatural() { }

        /// <summary>
        /// 利用自然的归并排序进行自底向上的排序。
        /// </summary>
        /// <typeparam name="T">用于排序的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];

            while (true)
            {
                // 找到第一个块
                int lo = 0;
                int mid = FindBlock(lo, a) - 1;
                if (mid == a.Length - 1)
                    break;

                while (mid < a.Length - 1)
                {
                    int hi = FindBlock(mid + 1, a) + mid;
                    Merge(lo, mid, hi, a, aux);
                    lo = hi + 1;
                    mid = FindBlock(lo, a) + lo;
                }
            }
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 利用自然的归并排序将链表排序。
        /// </summary>
        /// <typeparam name="T">链表元素类型。</typeparam>
        /// <param name="a">等待排序的链表。</param>
        public void Sort<T>(LinkedList<T> a) where T : IComparable<T>
        {
            while (true)
            {
                // 找到第一个块
                Node<T> lo = a.GetFirst();
                Node<T> mid = FindBlock(lo);

                if (mid.next == null)
                    break;

                while (mid.next != null)
                {
                    Node<T> hi = FindBlock(mid.next);
                    if (lo == a.GetFirst())
                        a.SetFirst(Merge(lo, mid, hi));
                    else
                        lo.next = Merge(lo.next, mid, hi);

                    // 跳到表尾
                    if (Less(hi.item, mid.item))
                        lo = mid;
                    else
                        lo = hi;

                    if (lo.next != null)
                        mid = FindBlock(lo.next);
                }
            }
        }

        /// <summary>
        /// 将两个块归并。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="lo">第一个块的开始下标。</param>
        /// <param name="mid">第一个块的结束下标(第二个块的开始下标 - 1)。</param>
        /// <param name="hi">第二个块的结束下标。</param>
        /// <param name="a">需要归并的数组。</param>
        /// <param name="aux">辅助数组。</param>
        private void Merge<T>(int lo, int mid, int hi, T[] a, T[] aux) where T : IComparable<T>
        {
            for (int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                {
                    a[k] = aux[j];
                    j++;
                }
                else if (j > hi)
                {
                    a[k] = aux[i];
                    i++;
                }
                else if (Less(aux[j], aux[i]))
                {
                    a[k] = aux[j];
                    j++;
                }
                else
                {
                    a[k] = aux[i];
                    i++;
                }
            }
        }

        /// <summary>
        /// 将两个有序链表块归并,返回新的表头。
        /// </summary>
        /// <typeparam name="T">链表元素类型。</typeparam>
        /// <param name="lo">第一个有序块起点。</param>
        /// <param name="mid">第一个有序块终点(第二个有序块起点的前驱)。</param>
        /// <param name="hi">第二个有序块的终点。</param>
        /// <returns>新的表头。</returns>
        private Node<T> Merge<T>(Node<T> lo, Node<T> mid, Node<T> hi) where T : IComparable<T>
        {
            Node<T> after = hi.next; // 要合并的两个块之后的元素
            Node<T> first = null;
            Node<T> i = lo;          // 链表1
            Node<T> j = mid.next;    // 链表2

            // 切割链表
            mid.next = null;
            hi.next = null;

            Node<T> current = null;
            // 决定新的表头
            if (Less(i.item, j.item))
            {
                current = i;
                i = i.next;
            }
            else
            {
                current = j;
                j = j.next;
            }

            first = current;

            // 归并表
            while (i != null && j != null)
            {
                if (Less(i.item, j.item))
                {
                    current.next = i;
                    i = i.next;
                    current = current.next;
                }
                else
                {
                    current.next = j;
                    j = j.next;
                    current = current.next;
                }
            }

            if (i == null)
                current.next = j;
            else
                current.next = i;

            // 连接表尾(链表 1 的尾部或者链表 2 的尾部)
            if (mid.next == null)
                mid.next = after;
            else
                hi.next = after;

            return first;
        }

        /// <summary>
        /// 获取下一个有序块。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="lo">查找起点。</param>
        /// <param name="a">用于查找的数组。</param>
        /// <returns>块的大小。</returns>
        private int FindBlock<T>(int lo, T[] a) where T : IComparable<T>
        {
            int size = 1;
            for (int i = lo; i < a.Length - 1; i++)
            {
                if (Less(a[i], a[i + 1]) || a[i].Equals(a[i + 1]))
                    size++;
                else
                    break;
            }
            return size;
        }

        /// <summary>
        /// 获取链表的下一个有序块。
        /// </summary>
        /// <typeparam name="T">链表的元素类型。</typeparam>
        /// <param name="lo">查找的起始结点。</param>
        /// <returns>有序块的最后一个元素结点。</returns>
        private Node<T> FindBlock<T>(Node<T> lo) where T : IComparable<T>
        {
            Node<T> hi = lo;
            while (hi.next != null)
            {
                if (Less(hi.item, hi.next.item) || hi.item.Equals(hi.next.item))
                    hi = hi.next;
                else
                    break;
            }
            return hi;
        }
    }
}

 

2.2.18

题目

打乱链表。
实现一个分治算法,使用线性对数级别的时间和对数级别的额外空间随机打乱一条链表。

解答

可以在用归并排序的方法做。
将归并时取两边较小的元素改为随机取一侧的值,即可实现打乱的效果。
算法的分析和普通归并排序一致,满足题目要求。

代码

分治法打乱链表的实现。

using System;

namespace _2._2._18
{
    /// <summary>
    /// 分治法打乱链表。

/// </summary>
    public class MergeShuffle
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeShuffle() { }

        /// <summary>
        /// 利用分治法打乱链表。
        /// </summary>
        /// <typeparam name="T">链表元素类型。</typeparam>
        /// <param name="a">等待打乱的链表。</param>
        public void Shuffle<T>(LinkedList<T> a)
        {
            int blockLen = 1;
            Random random = new Random();
            while (blockLen <= a.Size())
            {
                // 找到第一个块
                Node<T> lo = a.GetFirst();
                Node<T> mid = FindBlock(lo, blockLen);

                if (mid.next == null)
                    break;

                while (mid.next != null)
                {
                    Node<T> hi = FindBlock(mid.next, blockLen);
                    Node<T>[] result;
                    if (lo == a.GetFirst())
                    {
                        result = Merge(lo, mid, hi, random);
                        a.SetFirst(result[0]);
                    }
                    else
                    {
                        result = Merge(lo.next, mid, hi, random);
                        lo.next = result[0];
                    }


                    // 跳到表尾
                    lo = result[1];

                    if (lo.next != null)
                        mid = FindBlock(lo.next, blockLen);
                    else
                        mid = lo;
                }
                blockLen *= 2;
            }
        }

        /// <summary>
        /// 将两个有序链表块随机归并,返回新的表头。
        /// </summary>
        /// <typeparam name="T">链表元素类型。</typeparam>
        /// <param name="lo">第一个块起点。</param>
        /// <param name="mid">第一个块终点(第二个块起点的前驱)。</param>
        /// <param name="hi">第二个块的终点。</param>
        /// <returns>新的表头。</returns>
        private Node<T>[] Merge<T>(Node<T> lo, Node<T> mid, Node<T> hi, Random random)
        {
            Node<T> after = hi.next; // 要合并的两个块之后的元素
            Node<T> first = null;
            Node<T>[] result = new Node<T>[2];
            Node<T> i = lo;          // 链表1
            Node<T> j = mid.next;    // 链表2

            // 切割链表
            mid.next = null;
            hi.next = null;

            Node<T> current = null;
            // 决定新的表头
            if (random.NextDouble() >= 0.5)
            {
                current = i;
                i = i.next;
            }
            else
            {
                current = j;
                j = j.next;
            }

            first = current;

            // 归并表
            while (i != null && j != null)
            {
                if (random.NextDouble() >= 0.5)
                {
                    current.next = i;
                    i = i.next;
                    current = current.next;
                }
                else
                {
                    current.next = j;
                    j = j.next;
                    current = current.next;
                }
            }

            if (i == null)
                current.next = j;
            else
                current.next = i;

            // 连接表尾(链表 1 的尾部或者链表 2 的尾部)
            if (mid.next == null)
            {
                mid.next = after;
                result[1] = mid;
            }
            else
            {
                hi.next = after;
                result[1] = hi;
            }
            result[0] = first;

            return result;
        }

        /// <summary>
        /// 获取从指定位置开始定长的链表。
        /// </summary>
        /// <typeparam name="T">链表的元素类型。</typeparam>
        /// <param name="lo">链表的起始结点。</param>
        /// <param name="length">需要获取的链表长度。</param>
        /// <returns>结果链表的最后一个元素结点。</returns>
        private Node<T> FindBlock<T>(Node<T> lo, int length)
        {
            Node<T> hi = lo;
            for (int i = 0; i < length - 1 && hi.next != null; i++)
            {
                hi = hi.next;
            }

            return hi;
        }
    }
}

 

2.2.19

题目

倒置。
编写一个线性对数级别的算法统计给定数组中“倒置”数量
(即插入排序所需的交换次数,请见 2.1 节)。
这个数量和 Kendall tau 距离有关,请见 2.5 节。

解答

官方实现:https://algs4.cs.princeton.edu/22mergesort/Inversions.java.html

事实上只要在归并排序的时候统计 Less(aux[j], aux[i])
满足的次数即可,这个次数就是我们要的值。

代码
using System;
using Merge;

namespace _2._2._19
{
    /// <summary>
    /// 归并排序类。
    /// </summary>
    public class MergeSort : BaseSort
    {
        public int Counter = 0;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSort() { }

        /// <summary>
        /// 利用归并排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];
            Sort(a, aux, 0, a.Length - 1);
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Sort(a, aux, lo, mid);
            Sort(a, aux, mid + 1, hi);
            Merge(a, aux, lo, mid, hi);
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T>
        {
            for (int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                {
                    a[k] = aux[j];
                    j++;
                }
                else if (j > hi)
                {
                    a[k] = aux[i];
                    i++;
                }
                else if (Less(aux[j], aux[i]))
                {
                    a[k] = aux[j];
                    this.Counter += mid - i + 1;    // 统计逆序对数
                    j++;
                }
                else
                {
                    a[k] = aux[i];
                    i++;
                }
            }
        }
    }
}

 

2.2.20

题目

间接排序。
编写一个不改变数组的归并排序,
它返回一个 int[] 数组 perm,其中 perm[i] 的值是原数组中第 i
小的元素的位置。

解答

官方实现:https://algs4.cs.princeton.edu/22mergesort/Merge.java.html

把 Sort 方法中传入的 a 数组换成一个 index 数组,将 Merge
方法中的判断改为 Less(a[aux[j]], a[aux[i]]) 即可。

代码
using System;
using Merge;

namespace _2._2._20
{
    /// <summary>
    /// 归并排序类。
    /// </summary>
    public class MergeSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSort() { }

        /// <summary>
        /// 利用归并排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        public int[] IndexSort<T>(T[] a) where T : IComparable<T>
        {
            int[] aux = new int[a.Length];
            int[] index = new int[a.Length];
            for (int i = 0; i < a.Length; i++)
            {
                index[i] = i;
            }
            Sort(a, index, aux, 0, a.Length - 1);
            return index;
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] a, int[] index, int[] aux, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Sort(a, index, aux, lo, mid);
            Sort(a, index, aux, mid + 1, hi);
            Merge(a, index, aux, lo, mid, hi);
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, int[] index, int[] aux, int lo, int mid, int hi) where T : IComparable<T>
        {
            for (int k = lo; k <= hi; k++)
            {
                aux[k] = index[k];
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                {
                    index[k] = aux[j];
                    j++;
                }
                else if (j > hi)
                {
                    index[k] = aux[i];
                    i++;
                }
                else if (Less(a[aux[j]], a[aux[i]]))
                {
                    index[k] = aux[j];
                    j++;
                }
                else
                {
                    index[k] = aux[i];
                    i++;
                }
            }
        }

        public override void Sort<T>(T[] a)
        {
            throw new NotImplementedException();
        }
    }
}

 

2.2.21

题目

一式三份。
给定三个列表,每个列表中包含 N 个名字,
编写一个线性对数级别的算法来判定三分列表中是否含有公共的名字,
如果有,返回第一个被找到的这种名字。

解答

对三份列表进行归并排序(O(nlogn)),随后遍历一遍其中的一份表,
用二分查找检查在其余两个表中是否存在相同的姓名(O(nlogn))

代码
using System;
using Merge;

namespace _2._2._21
{
    /*
     * 2.2.21
     * 
     * 一式三份。
     * 给定三个列表,
     * 每个列表中包含 N 个名字,
     * 编写一个线性对数级别的算法来判定三份列表中是否含有公共的名字,
     * 如果有,返回第一个被找到的这种名字。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] name1 = new string[] { "Noah", "Liam", "Jacob", "Mason" };
            string[] name2 = new string[] { "Sophia", "Emma", "Mason", "Ava" };
            string[] name3 = new string[] { "Mason", "Marcus", "Alexander", "Ava" };

            MergeSort mergeSort = new MergeSort();
            mergeSort.Sort(name1);
            mergeSort.Sort(name2);
            mergeSort.Sort(name3);

            for (int i = 0; i < name1.Length; i++)
            {
                if (BinarySearch(name1[i], name2, 0, name1.Length) != -1 &&
                    BinarySearch(name1[i], name3, 0, name1.Length) != -1)
                {
                    Console.WriteLine(name1[i]);
                    break;
                }

            }
        }

        /// <summary>
        /// 二分查找,返回目标元素的下标,没有结果则返回 -1。
        /// </summary>
        /// <typeparam name="T">查找的元素类型。</typeparam>
        /// <param name="key">要查找的目标值。</param>
        /// <param name="array">用于查找的目标范围。</param>
        /// <param name="lo">查找的起始下标。</param>
        /// <param name="hi">查找的终止下标。</param>
        /// <returns>找到则返回元素下标,否则返回 -1。</returns>
        static int BinarySearch<T>(T key, T[] array, int lo, int hi) where T : IComparable<T>
        {
            while (lo <= hi)
            {
                int mid = lo + (hi - lo) / 2;
                if (array[mid].Equals(key))
                    return mid;
                else if (array[mid].CompareTo(key) < 0)
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
            return -1;
        }
    }
}

 

2.2.22

题目

三向归并排序。
假设每次我们是把数组分成三个部分而不是两个部分并将它们分别排序。
然后进行三向归并。
这种算法的运行时间的增长数量级是多少。

解答

88必发最新手机客户端 21
增长数量级为O(nlogn)。

代码
using System;
using System.Diagnostics;

namespace Merge
{
    /// <summary>
    /// 三向归并排序。
    /// </summary>
    public class MergeSortThreeWay : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSortThreeWay() { }

        /// <summary>
        /// 利用三项归并排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">数组中的元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            T[] aux = new T[a.Length];
            Sort(a, aux, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行三向归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)       // 小于或等于一个元素
                return;
            int lmid = lo + (hi - lo) / 3;
            int rmid = hi - (hi - lo) / 3;
            Sort(a, aux, lo, lmid);
            Sort(a, aux, lmid + 1, rmid);
            Sort(a, aux, rmid + 1, hi);
            Merge(a, aux, lo, lmid, rmid, hi);
        }

        /// <summary>
        /// 返回两个元素中较小的那个。
        /// </summary>
        /// <typeparam name="T">比较的元素类型。</typeparam>
        /// <param name="a">用于比较的元素。</param>
        /// <param name="b">用于比较的元素。</param>
        /// <returns>较小的元素。</returns>
        private T Min<T>(T a, T b) where T : IComparable<T>
        {
            if (Less(a, b))
                return a;
            return b;
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="lmid">范围三分之一点。</param>
        /// <param name="rmid">范围三分之二点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, T[] aux, int lo, int lmid, int rmid, int hi) where T : IComparable<T>
        {
            for (int l = lo; l <= hi; l++)
            {
                aux[l] = a[l];
            }

            int i = lo, j = lmid + 1, k = rmid + 1;
            for (int l = lo; l <= hi; l++)
            {
                int flag = 0;
                if (i > lmid)
                    flag += 1;
                if (j > rmid)
                    flag += 10;
                if (k > hi)
                    flag += 100;
                switch (flag)
                {
                    case 0:         // 三个数组都还没有取完
                        T min = Min(aux[i], Min(aux[j], aux[k]));
                        if (min.Equals(aux[i]))
                            a[l] = aux[i++];
                        else if (min.Equals(aux[j]))
                            a[l] = aux[j++];
                        else
                            a[l] = aux[k++];
                        break;
                    case 1:         // 只有第一个数组取完了
                        if (Less(aux[j], aux[k]))
                            a[l] = aux[j++];
                        else
                            a[l] = aux[k++];

                        break;
                    case 10:        // 只有第二个数组取完了
                        if (Less(aux[i], aux[k]))
                            a[l] = aux[i++];
                        else
                            a[l] = aux[k++];
                        break;
                    case 100:       // 只有第三个数组取完了
                        if (Less(aux[i], aux[j]))
                            a[l] = aux[i++];
                        else
                            a[l] = aux[j++];
                        break;
                    case 11:        // 第一、二个数组取完了
                        a[l] = aux[k++];
                        break;
                    case 101:       // 第一、三个数组取完了
                        a[l] = aux[j++];
                        break;
                    case 110:       // 第二、三个数组取完了
                        a[l] = aux[i++];
                        break;
                }
            }
        }
    }
}

 

2.2.23

题目

改进。
用实验评估正文中所提到的归并排序的三项改进(请见练习 2.2.11)的效果,
并比较正文中实现的归并排序和练习 2.2.10 所实现的归并排序之间的性能。
根据经验给出应该在何时为子数组切换到插入排序。

解答

88必发最新手机客户端 22
阈值合适时,大约会有10%的性能提升。
阈值在 10 以下都是比较合适的。

代码
using System;
using Merge;

namespace _2._2._23
{
    /*
     * 2.2.23
     * 
     * 改进。
     * 用实验评估正文中所提到的归并排序的三项改进(请见练习 2.2.11)的效果,
     * 并比较正文中实现的归并排序和练习 2.2.10 所实现的归并排序之间的性能。
     * 根据经验给出应该在何时为子数组切换到插入排序。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            MergeSort mergeSort = new MergeSort();
            MergeSortX mergeSortX = new MergeSortX();
            MergeSortUnstable mergeSortUnstable = new MergeSortUnstable();

            int n = 1000000;
            int cutoff = 2;
            int trialTime = 4;
            Console.WriteLine("归并排序改进前与改进后的比较:");
            Console.WriteLine("数组\t耗时1\t耗时2\t阈值\t比率");
            for (int i = 0; i < 20; i++)
            {
                double mergeSortTime = 0;
                double mergeSortXTime = 0;
                mergeSortX.SetCutOff(cutoff);
                for (int j = 0; j < trialTime; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(n);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    mergeSortTime += SortCompare.Time(mergeSort, a);
                    mergeSortXTime += SortCompare.Time(mergeSortX, b);
                }
                mergeSortTime /= trialTime;
                mergeSortXTime /= trialTime;
                Console.WriteLine(n + "\t" + mergeSortTime + "\t" + mergeSortXTime + "\t" + cutoff + "\t" + mergeSortTime / mergeSortXTime);
                cutoff++;
            }

            n = 100000;
            Console.WriteLine("稳定归并排序与不稳定版本的比较:");
            Console.WriteLine("数组\t耗时1\t耗时2\t比率");
            for (int i = 0; i < 6; i++)
            {
                double mergeSortTime = 0;
                double mergeSortUnstableTime = 0;
                for (int j = 0; j < trialTime; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(n);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    mergeSortTime += SortCompare.Time(mergeSort, a);
                    mergeSortUnstableTime += SortCompare.Time(mergeSortUnstable, b);
                }
                mergeSortTime /= trialTime;
                mergeSortUnstableTime /= trialTime;
                Console.WriteLine(n + "\t" + mergeSortTime + "\t" + mergeSortUnstableTime + "\t" + mergeSortTime / mergeSortUnstableTime);
                n *= 2;
            }
        }
    }
}

 

2.2.24

题目

改进的有序测试。
在实验中用大型随机数组评估练习 2.2.8 所做的修改的效果。
根据经验用 N(被排序的原始数组的大小)的函数描述条件语句(a[mid] <=
a[mid + 1])成立(无论数组是否有序)的次数。

解答

88必发最新手机客户端 23
约为 lgN 次

代码
using System;
using Merge;

namespace _2._2._24
{
    /*
     * 2.2.24
     * 
     * 改进的有序测试。
     * 在实验中用大型随机数组评估练习 2.2.8 所做的修改的效果。
     * 根据经验用 N(被排序的原始数组的大小)的函数描述条件语句
     * (a[mid] <= a[mid + 1])成立(无论数组是否有序)的次数。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            MergeSortX mergeSortX = new MergeSortX();
            int n = 10000;
            int trialTimes = 10;
            Console.WriteLine("数组\t平均命中次数");
            for (int i = 0; i < 4; i++)
            {
                int avgHit = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    mergeSortX.ResetHitTime();
                    int[] a = SortCompare.GetRandomArrayInt(n);
                    mergeSortX.Sort(a);
                    avgHit += mergeSortX.GetHitTime();
                }

                Console.WriteLine(n + "\t" + avgHit / trialTimes);
                n *= 10;
            }
        }
    }
}

 

2.2.25

题目

多向归并排序。
实现一个 k 向(相对双向而言)归并排序程序。
分析你的算法,估计最佳的 k 值并通过实验验证猜想。

解答

事实上 k 的取值无关紧要,实验也证明了这一点。
88必发最新手机客户端 24
算法大致可以分为以下几个步骤
首先将数组划为 k 份,用一个数组 mids 记录这 k 个子数组的分割位置
随后递归的调用 Sort 方法,将这 k 个子数组排序
随后将这 k 个子数组归并,
每次归并时遍历取 k 个子数组中值最小的一个,然后对应子数组的指示器 + 1
上面这一步是 O(k) 的,可以用堆或者败者树优化为对数级别

代码
using System;
using System.Diagnostics;

namespace Merge
{
    /// <summary>
    /// k 路归并排序。
    /// </summary>
    public class MergeSortKWay : BaseSort
    {
        /// <summary>
        /// 同时归并的数组数目。
        /// </summary>
        public int K { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSortKWay() { this.K = 2; }

        /// <summary>
        /// 用 k 向归并排序对数组 a 进行排序。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="a"></param>
        /// <exception cref="ArgumentOutOfRangeException">数组长度小于 K 值时抛出异常。</exception>
        public override void Sort<T>(T[] a)
        {
            if (this.K > a.Length)
                throw new ArgumentOutOfRangeException("数组长度不能小于 K 值!");

            T[] aux = new T[a.Length];
            Sort(a, aux, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 自顶向下地对数组指定范围内进行 k 向归并排序,需要辅助数组。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">排序范围起点。</param>
        /// <param name="hi">排序范围终点。</param>
        private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)       // 小于或等于一个元素
                return;
            int[] mids = new int[this.K - 1];
            int steps = (hi - lo) / this.K;
            mids[0] = lo + steps;
            for (int i = 1; i < this.K - 1; i++)
            {
                mids[i] = mids[i - 1] + steps;
                if (mids[i] > hi)               // 防止溢出
                    mids[i] = hi;
            }

            Sort(a, aux, lo, mids[0]);
            for (int i = 1; i < this.K - 1; i++)
            {
                Sort(a, aux, mids[i - 1] + 1, mids[i]);
            }
            Sort(a, aux, mids[this.K - 2] + 1, hi);
            Merge(a, aux, lo, mids, hi);
        }

        /// <summary>
        /// 将指定范围内的元素归并。
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">原数组。</param>
        /// <param name="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mids">范围中间点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, T[] aux, int lo, int[] mids, int hi) where T : IComparable<T>
        {
            for (int l = lo; l <= hi; l++)
            {
                aux[l] = a[l];
            }

            int[] pointers = new int[this.K]; // 标记每个数组的当前归并位置
            pointers[0] = lo;                 // 开始时归并位置处于每个子数组的起始
            for (int i = 1; i < this.K; i++)
            {
                pointers[i] = mids[i - 1] + 1;
            }
            // 开始归并
            for (int i = lo; i <= hi; i++)
            {
                // 找到最小值
                T min;
                int minPointerIndex = 0;
                bool isInit = true;
                if (pointers[this.K - 1] > hi)
                {
                    min = default(T);                 // 初始化以避免编译错误
                }
                else
                {
                    min = aux[pointers[this.K - 1]];
                    minPointerIndex = this.K - 1;
                    isInit = false;
                }

                for (int j = 0; j < this.K - 1; j++)
                {
                    if (pointers[j] > mids[j])      // 当前数组已经用完
                        continue;
                    if (isInit)                     // 第一次赋值
                    {
                        isInit = false;
                        min = aux[pointers[j]];
                        minPointerIndex = j;
                        continue;
                    }
                    if (Less(aux[pointers[j]], min))
                    {
                        min = aux[pointers[j]];
                        minPointerIndex = j;
                    }
                }

                // 将最小值赋给归并数组,对应子数组的归并位置+1
                a[i] = min;
                pointers[minPointerIndex]++;
            }
        }
    }
}

 

2.2.26

题目

创建数组。使用 SortCompare 粗略比较在你的计算机上在 merge() 中和在
sort() 中创建 aux[] 的性能差异。

解答

差距还是比较明显的,由于 Merge 会调用多次,而用于启动递归的 Sort
方法只会调用一次。

88必发最新手机客户端 25

代码
using System;
using Merge;

namespace _2._2._26
{
    /*
     * 2.2.26
     * 
     * 创建数组。
     * 使用 SortCompare 粗略比较在你的计算机上
     * 在 merge() 中和在 sort() 中创建 aux[] 的性能差异。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            AuxInSortMergeSort auxInSort = new AuxInSortMergeSort();
            AuxInMergeMergeSort auxInMerge = new AuxInMergeMergeSort();
            int[] data1 = SortCompare.GetRandomArrayInt(100000);
            int[] data2 = new int[data1.Length];
            data1.CopyTo(data2, 0);
            Console.WriteLine("在Sort中创建aux[]\t" + SortCompare.Time(auxInSort, data1) + "ms");
            Console.WriteLine("在Merge中创建aux[]\t" + SortCompare.Time(auxInMerge, data2) + "ms");

        }
    }
}

 

2.2.27

题目

子数组长度。
用归并将大型随机数组排序,
根据经验用 N
(某次归并时两个子数组的长度之和)的函数估计当一个子数组用尽时另一个子数组的平均长度。

解答

大致上会是一个对数函数,用 Excel 做了简单的拟合。
88必发最新手机客户端 26

代码
using System;
using Merge;

namespace _2._2._27
{
    /*
     * 2.2.27
     * 
     * 子数组长度。
     * 用归并将大型随机数组排序,
     * 根据经验用 N (某次归并时两个子数组的长度之和)
     * 的函数估计当一个子数组用尽时另一个子数组的平均长度。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int arraySize = 1000000;
            NotifiedMergeSort sort = new NotifiedMergeSort(arraySize);
            for (int i = 0; i < 100; i++)
            {
                int[] data = SortCompare.GetRandomArrayInt(arraySize);
                sort.Sort(data);
            }

            Console.WriteLine("n\trest\ttimes");
            for (int i = 0; i < sort.NArraySize.Length; i++)
            {
                if (sort.NArraySize[i] != 0)
                    Console.WriteLine(i + "\t" + sort.NArraySize[i] / sort.NArraySizeTime[i] + "\t" + sort.NArraySizeTime[i]);
            }
            // 大致上是一个对数函数
        }
    }
}

 

2.2.28

题目

自顶向下和自底向上。
对于 N=10^3、10^4、10^5 和 10^6,
使用 SortCompare 比较自顶向下和自底向上的归并排序的性能。

解答

自底向上会快一些,省去了递归过程中函数重复调用的时间。
88必发最新手机客户端 27

代码
using System;
using Merge;

namespace _2._2._28
{
    /*
     * 2.2.28
     * 
     * 自顶向下和自底向上。
     * 对于 N=10^3、10^4、10^5 和 10^6,
     * 使用 SortCompare 比较自顶向下和自底向上的归并排序的性能。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int n = 1000;
            MergeSort topBottomMergeSort = new MergeSort();
            MergeSortBU bottomUpMergeSort = new MergeSortBU();
            int trialTimes = 100;
            for (int i = 0; i < 4; i++)
            {
                Console.Write("数组大小:" + n + "\t");
                int time1 = 0, time2 = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    double[] data1 = SortCompare.GetRandomArrayDouble(n);
                    double[] data2 = new double[n];
                    data1.CopyTo(data2, 0);
                    time1 += (int)SortCompare.Time(topBottomMergeSort, data1);
                    time2 += (int)SortCompare.Time(bottomUpMergeSort, data2);
                }

                Console.WriteLine("自顶向下:" + time1 / trialTimes + "ms\t自底向上:" + time2 / trialTimes + "ms");
                n *= 10;
            }
        }
    }
}

 

2.2.29

题目

自然的归并排序。对于 N=10^3、10^6 和 10^9,类型为 Long
的随机主键数组,根据经验给出自然的归并排序(请见练习
2.2.16)所需要的遍数。
提示:不需要实现这个排序(甚至不需要生成所有完整的 64
位主键)也能完成这道练习。

解答

完全有序时只需要一次归并(直接输出),
逆序时需要 n – 1 次归并(退化为插入排序),
平均需要 n/2 次归并。
所以分别需要 500,500000,500000000 次归并。