归并排序算法的编码和优化,归并排序及其优化

写在眼下

方方面面项目都托管在了 Github
上:

摸索更为有利的本子见:https://alg4.ikesnowy.com

那壹节内容或许会用到的库文件有 Merge,同样在 Github 上得以找到。

善用 Ctrl + F 查找难点。

一 低档排序算法

排序算法关心的重假诺重新排列数组成分,当中每一个成分都有多个主键。排序算法是将享有因素主键按某种方式排列(平时是比照大小或许字母逐1)。排序后索引较大的主键大于等于索引较小的主键。

参考资料

《算法(第4版)》         
— — Robert Sedgewick, Kevin Wayne

 

Q:什么是归并排序?
A:它是建立在统一操作上的一种有效的排序算法;是应用分治法的3个10分优良的使用;是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);
    }
}
  • 排序费用模型:切磋排序算法时,供给总结正如和置换的次数。对于不沟通成分的算法,总结做客数组的次数
  • 外加内部存款和储蓄器使用:排序算法的额外内部存款和储蓄器开支和运行时刻同1首要。排序算法可分两类:除了函数调用所需的栈和固定数指标实例变量之外无需附加内部存款和储蓄器的原地排序算法,以及须要外加内部存款和储蓄器空间来存款和储蓄另一份数组副本的其余排序算法。
  • 数据类型:上述排序算法模板适用于任何达成了Comparable接口的数据类型。例如,Java中封装的Integer和Double,以及String和任何许多尖端数据类型(如File和UTucsonL)都落到实处了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)被调用时分别再次回到2个负整数、零和2个正整数(-一、0和一)。一般的话,若
v 和 w 无法相比可能两方之一是 null,v.compareTo(w) 将会抛出二个相当。

归并排序的定义

归并排序的贯彻自小编是如此来叙述的:先对个别多少个要素通过两两统一的方法展开排序,形成贰个长短稍大片段的有序类别。然后在此基础上,对八个长度稍大学一年级部分的稳步种类再拓展两两合并,形成3个长度越来越大的不变种类,有序体系的的尺寸不断狠抓,直到覆盖整个数组的轻重缓急停止,归并排序就形成了。

 

主导思想

要将2个数组排序,能够先(递归地)将它分为两半分级排序,然后将结果归并起来。

优点?它能保证将随意长度为 N 的数组排序所需时间和 NlogN 成正比;

缺点?所需的附加空间和 N 成正比。

2.2.1

一.一 接纳排序

选拔排序:首先找到数组中小小的的因素,其次,将它和数组的首先个要素沟通地点(假设第叁个成分最小就和和气调换)。再度,在剩余成分中找到最小的要素,将它与数组的第3个成分调换地方。如此往返,直到将全方位数组排序。那种方式叫做接纳排序,因为它在不断选拔剩余成分中的最小者

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

采取排序内循环只是在相比较当前因素与当前已知最小成分(以及将眼下索引加一和自我批评是还是不是代码越界),沟通成分的代码写到了内循环之外,每一遍沟通都能排定三个因素,由此沟通总次数是N。所以算法总的时间效用取决于相比较次数。

  • 长度为 N 的数组,选用排序需求大概 (N^二) / 贰 次相比和 N 次交流

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

  • 分选排序有三个显著特点:
  1. 运作时刻和输入非亲非故。为了找出最小成分而扫描一回数组并无法为下三回扫描提供怎么样音信。那种情况在一些情况下是老毛病,因为三个已经稳步的数组或是主键全体相当于的数组和二个要素随机排列的数组所用的排序时间相同长,而别的算法更擅长运用输入的开端状态。
  2. 数量移动最少。每一遍调换都会变动八个数组成分的值,由此挑选排序用了N次调换——交流次数和数组大小是线性关系,而任何任何算法都不拥有这几个特点(大多数增高数据级都以线性对数或平方级别)。

归并排序的三种实现格局:递归和循环

归并排序有二种实现形式:
基于递归的合并排序和依据循环的合并排序
。(也叫自顶向下的集合排序自底向上的联合排序

 

那二种归并算法纵然实现格局分化,但依然有共同之处的:

 

1.
无论是基于递归依然循环的联结排序,
它们调用的中央措施都是相同的:完毕1趟合并的算法,即八个已经平稳的数组类别合并成三个更大的稳步数组体系 
(前提是五个原系列都是稳步的!)

2.
从排序轨迹上看,联合系列的长短都是从小(二个因素)到大(整个数组)增加

 

 

原地归并的聊以自慰方法

Q:为啥须要原地归并?
A:因为用归并将一个大数组排序时,需求进行几度归并,而且每一趟归并会都创设三个新数组来囤积排序结果会带来难题。

Q:原地归并贯彻了何等?
A:能够先将前半部分排序,再将后半有些排序,然后数组中活动成分而不需求使用额外的空间(将三个不变的数组归并为1个平稳的数组)

Q:怎么样落实归并?
A:成立三个适龄大小的数组,然后将五个输入数组中的元素贰个个经年累月方法那个数组中。

代码完成
根据排序算法类的模板落到实处归并排序(提示:点蓝字查看详情)

    /**
     * 将子数组 arr[lo...mid] 和 arr[mid+1...hi] 归并成一个有序的数组并将结果存放在 arr[lo...hi] 中。
     * 将所有元素复制到一个辅助数组中,再把归并的结果放回原数组中
     */
    private static void merge(Comparable[] arr, int lo, int mid, int hi) {
        // 将 arr[lo...mid] 和 arr[mid+1...hi] 归并
        int indexI = lo;
        int indexJ = mid + 1;
        // 将 a[lo...hi] 复制到 aux[lo...hi]
        // System.arraycopy(arr, lo, aux, lo, hi - lo + 1);
        for (int indexK = lo; indexK <= hi; indexK++) {
            aux[indexK] = arr[indexK];
        }
        // 归并回到 arr[lo...hi]
        for (int indexK = lo; indexK <= hi; indexK++) {
            // 左半边用尽(取右半边的元素)
            if (indexI > mid) {
                arr[indexK] = aux[indexJ++];
            }
            // 右半边用尽(取左半边的元素)
            else if (indexJ > hi) {
                arr[indexK] = aux[indexI++];
            }
            // 右半边的当前元素小于左半边的当前元素(取右半边的元素)
            else if (less(aux[indexJ], aux[indexI])) {
                arr[indexK] = aux[indexJ++];
            }
            // 右半边的当前元素大于左半边的当前元素(取左半边的元素)
            else {
                arr[indexK] = aux[indexI++];
            }
        }
    }
题目

奉公守法本书初阶所示轨迹的格式给出原地归并排序的空洞 merge()
方法是怎么着将数组 A E Q S U Y E I N O S T 排序的。

壹.二 插入排序

插入排序:整理扑克时相似都以一江子磊张来,将每张牌插入到此外已经逐步的牌中的适当地点。在处理器完毕中,为了要给插入元素腾出空间,需求将其它全体因素在插入从前都向右移动1位。那种算法叫做插入排序

  • 与选取排序一样,当前目录左侧全数因素都是一动不动的,但它们最后地点还不鲜明,为了给越来越小成分腾出空间,它们或许会被挪动,但当索引到达数组右端时,数组排序就成功了。
  • 与选用排序分歧的是,插入排序所需时日取决于输入相月素的起先顺序。如对近似平稳的数组排序要比自由数组快很多。

对于随意排列的长度为N且主键不重复的数组,平均情状下插入排序须求 ~ N^2
/ 四$ 次相比以及~N^2 / 四 次交流。最坏情形下需求 ~ N^贰 / 二 次相比较和 ~N^2
/ 贰 次交流,最棒状态下需求 N-壹 次相比较和 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;
        }
    }
}

思考一般情状下1部分有序的数组。倒置指的是数组中八个顺序颠倒的要素。比如EXAMPLE中有1壹对倒置:E-A,X-A,X-M,X-P,X-L,X-E,M-L,M-E,P-L,P-E和L-E。若数组中倒置的数量稍低于数组大小的某些倍数,则这些数组是部分有序。插入排序对那样的数组很实用,事实上,当倒置数量很时辰,插入排序只怕比别的任何算法都快。

插入排序的交流操作和数组中倒置数量一样,供给比较的次数超过等于倒置的数目,小于等于倒置的数码增加数组的大小再减一。要小幅进步插入排序速度并简单,只需在内循环中校较大因素都向右移而不总是交流多少个要素(那样访问数组次数就能减半),即上述第一种达成。

单趟归并算法

 

自顶向下的联合排序(化零为整,递归解决)

鉴于以上的原地归并只能将八个静止的数组归并成三个上行下效的数组,所以得依据原地归并的肤浅去贯彻1种递归归并。

要对子数组 arr[lo…hi] 进行排序,先将它分为 arr[lo…mid] 和
arr[mid+1…hi]
两部分,分别通过递归调用将它们单独排序,最终将有序的子数组归并为最后的排序结果。

Q:为啥它能将正确的排序?
A:假如它能将七个子数组排序,那么它就足以由此归并多个子数组来将全方位数组排序。

解答

亚洲必赢官网 1

 

一.三 希尔排序

希尔排序:是1种基于插入排序的排序算法。对于大规模乱序数组插入排序非常的慢,因为它只会换换相邻的因素,若最小成分在数组最后,则对其急需活动N-三回。Hill排序革新了插入排序,沟通不相邻的要素以对数组的部分进展排序,并最后用插入排序将1部分有序的数组排序。

  • h有序数组:数组中随意间隔为 h 的因素都稳步。即2个 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;
            }
        }
    }
}

算法实例解释可参照:
白话经典算法体系之三Hill排序的达成
图解排序算法(二)之希尔排序

希尔排序更连忙原因是它衡量了子数组的层面和有序性。排序之初,种种子数组都相当的短,排序之后子数组都是一些有序的,那两种状态都严丝合缝插入排序。子数组部分有序的水平在于递增系列的取舍。

单趟排序的贯彻分析

 

下边笔者先介绍二种不一致归并算法调用的公共措施,
即实现单趟归并的算法。(八个已经稳步的数组系列合并成一个越来越大的稳步数组连串)

 

在起初排序前创办有二个和原数组a长度相同的空的帮衬数组aux

 

单趟归并的历程如下:

 

壹. 
率先将原数组中的待排序体系拷贝进协助数组的同等地点中,即将a[low…high]拷贝进aux[low…high]中

2.  帮助数组aux的职分有两项:相比较成分大小,
并在aux中每种获得有序的因素放入原数组a中

(通过1使aux和a在low-high的职位是完全相同的!这是落到实处的底蕴)

3. 
因为aux[low…high]由两段有序的队列:aux[low…mid]和aux[mid…high]重组,
那里称之为aux1和aux二,大家要做的正是从aux1和aux二的头顶成分开头,相比双方成分的轻重。将较小的成分放入原数组a中(若a[0]已被占则放在a[1]…依次类推),并取得较小成分的下三个成分,
和另一个行列中较大的因素比较
。因为前提是aux一和aux2都以一动不动的,所以经过那种艺术我们能取得更加长的稳步类别

4.  若是aux的两段种类中,其中1段中的全部因素都已”相比”完了,
取得另壹段连串中多余的要素,全体放入原数组a的剩余地方。

 

进程叁和四的落实格局

  • 设置多少个游标 i 和 j
    用于“元素比较”
    (在aux中实行):变量,i 和
    j,分别表示左游标和右游标,初叶时分别指向aux[low]和aux[mid]
  • 设置游标k用于显明在a中放置元素的地方(在a中进行),k在起首时候指向a[low]
  • 全体上来说i,
    j, k的来头都以向右移动的

 

进程三和4的图示演说

 

图A

亚洲必赢官网 2

 

 

 

亚洲必赢官网 3

结合方面包车型客车长河三, 
比较 i 和 j 当前所指的aux中的成分的深浅,
取得当中比较大的特别成分(例如上海教室中的i),将其放入数组a中,
此时(在图中假如境况下): i加壹,左游标右移。  同时k也加一,
k游标也向右移动

 

图B

亚洲必赢官网 4

 

 

亚洲必赢官网 5

组成方面包车型大巴进程四,
在 i 和 j 都向右移动的进程中,
在图中倘使景况下,因为j当前所指的因素(图中地点)大于左半边即a[low…mid]的享有因素,导致
i 不断增多(右移)且通过了界限(mid),
所以这时候就不需求相比了,只要把j当前所指地点到high的因素都搬到原数组中,填满原数组中剩下的岗位,
单趟归并就成功了, 在那1段进程中 j 一连加一,右游标一而再右移。 
同时k也接2连三加1, k游标也接连右移, 直到 j == high且k == high结束

 

基于上边的发挥,
总计出单趟归并算法中最重大的多少个规范判断情况:

  1. 左半边用尽(取右半边的成分)
  2. 右半边用尽(取左半边的成分)
  3. 右半边成分小于左半边当前因素(取右半边的元素)
  4. 右半边成分大于等于左半边当前因素(取左半边的因素)

 

 

运作轨迹

自顶向下的合并排序运维轨迹

2.2.2

1.四 归并排序

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

单趟排序算法的代码

 

有了下面的演说,写那些算法就简单了吗

 

/**
   * @description: 完成一趟合并
   * @param a 输入数组
   * @param low,mid,high a[low...high] 是待排序序列, 其中a[low...mid]和 a[mid+1...high]已有序
   */
  private static void merge (int a [],int low,int mid,int high) {
    for(int k=low;k<=high;k++){
      aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置
    }
    int i = low;    // 游标i,开始时指向待排序序列中左半边的头元素
    int j = mid+1;  // 游标j,开始时指向待排序序列中右半边的头元素
    for(int k=low;k<=high;k++){
      if(i>mid){
        a[k] = aux[j++]; // 左半边用尽
      }else if(j>high){
        a[k] = aux[i++]; // 右半边用尽
      }else if(aux[j]<aux[i]){
        a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素
      }else {
        a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素
      }
    }
  }
}
 

 

【注意】在排序之初成立了三个长度和原数组a相同的帮带数组aux,那部分代码上文未提交

 

代码实现

根据排序算法类的模板落到实处采取排序(提示:点蓝字查看详情)

    private static Comparable[] aux;    // 归并所需的辅助数组

    public static void sort(Comparable[] arr) {
        aux = new Comparable[arr.length]; // 一次性分配空间
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int lo, int hi) {
        // 将数组 arr[lo...hi] 排序
        if (hi <= lo) return;
        int mid = lo + ((hi - lo) >> 1);
        sort(arr, lo, mid);          // 将左半边排序
        sort(arr, mid + 1, hi);  // 将右半边排序
        merge(arr, lo, mid, hi);     // 归并结果
    }
题目

遵照算法 2.四 所示轨迹的格式给来自顶向下的联合排序是哪些将数组 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循环)进行了5个判断:左半边用尽(取右半边成分)、右半边用尽(取左半边元素)、左半边的当下因素小于右半边的脚下因素(取左半边成分)以及右半边的此时此刻成分小于左半边的近来因素(取右半边成分)

单趟排序的经过图解

 

为了更详尽的描述单趟排序的进程,上面在地点的图A和图B的根基上提交每一步的图解:

 

我们要排序的行列是
贰 肆 5 玖 壹 三 陆 7, 合并的前提是2 四 5
九 和 一 三 陆 7都以雷打不动的

 

先比较aux中2和1的大小,因为2>1,所以将1放入a[0]。这时,
游标 i 不动, 游标 j 右移, 游标 k 右移

亚洲必赢官网 6

 亚洲必赢官网 7

 

比较aux中2和3的大小,因为2<3,所以将2放入a[1]。这时,
游标 j 不动, 游标 i 右移, 游标 k 右移

亚洲必赢官网 8

 亚洲必赢官网 9

 

比较aux中4和3的大小,因为3<4,所以将3放入a[2]。这时,
游标 i 不动, 游标 j 右移, 游标 k 右移

亚洲必赢官网 10

 亚洲必赢官网 11

 

类似上述,
不表明

亚洲必赢官网 12

亚洲必赢官网 13

 

 

恍如上述,
不表达

亚洲必赢官网 14

 亚洲必赢官网 15

 

就像是上述,
不表达

亚洲必赢官网 16

 亚洲必赢官网 17

 

好像上述,
不说明

亚洲必赢官网 18

 

亚洲必赢官网 19

 

只顾, 这那里 j
扩充导致 j> high,  以往的动静是“右半边用尽”,
所以将aux左半边剩余的要素玖放入a剩下的局地a[7]中,
单趟排序完结

亚洲必赢官网 20

 

亚洲必赢官网 21

 

【注意】
上边那些例子中的序列只是数组的壹部分,
并不一定是成套数组

 

 

本身在上头介绍过,三种不相同归并算法:
基于递归的联结和依据循环的合并, 
都是以单趟归并的算法为底蕴的。

 

上面先来讲一下基于递归的合并排序(自顶向下的合并排序)

 

天性分析

最好状态:T(n) = O(n)
最差意况:T(n) = O(nlogn)
平均意况:T(n) = O(nlogn)

对于长度为 N 的任意数组,自顶向下的会合排序供给 1/2NlgN – NlgN
次比较

对此长度为 N 的任意数组,自顶向下的合并排序最多须要访问数组 陆NlgN
(2N 次用来复制、二N
次用来将排好序的成分移动回来、其余最多比较 2N 次)。

Q:首要缺点是怎么
A:接济数组所运用的附加空间和 N 的轻重缓急成正比。

解答

亚洲必赢官网 22

 

自顶向下的联合排序

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 的数组,自顶向下的集合排序需求 五成NlogN 至 NlogN 次比较
  2. 对此长度为 N 的数组,自顶向下的合并排序最多须求拜访数组 陆NlogN 次

归并排序所需时日和 NlogN 成正比,首要缺点是赞助数组所使用的附加空间和
N 的大大小小成正比。

基于递归的联合排序(自顶向下)

 

根据递归的合并排序又称为自顶向下的集合排序

 

自底向上的联合排序(按部就班的缓解)

福寿康宁统壹的另一种办法:先归并那多少个微型数组,然后再成对归并收获子数组。首先两两归并,然后44归并,然后⑧8归并,一向下去。

2.2.3

归并改革:
  • 对小圈圈数组使用插入排序。使用插入排序处理小范围的子数组,一般能够将归并排序运营时刻减少一成~15%。
  • 测试数组是还是不是业已稳步。添加二个论断标准,若 a[mid] <= a[mid + 1]
    则认为数组已经稳步并跳过 merge()
    方法。那几个改变不影响排序的递归调用,但随便有序的子数组算法的运营时刻就变为线性了。
  • 不将成分复制到协理数组。能够节约成分复制到支持数组所用时间(但空间丰硕),此时需调用三种排序方法,一种从输入数组排序到救助数组,1种从支持数组排序到输入数组,技巧是在递归调用的各种层次交流输入数组和援助数组的角色。

递归归并的思辨

亚洲必赢官网 23

 

亚洲必赢官网 24

 

 

最主要的是sort(int
a [], int low,int high)方法里面包车型大巴三行代码:

sort(a,low,mid); 
sort(a,mid+1,high);
merge(a,low,mid,high);

 

分级代表对多数边种类递归、对右半边体系递归、单趟合并操作。

 

全体代码:

/**
* @Author: HuWan Peng
* @Date Created in 9:44 2017/11/29
*/
public class MergeSort {
  private static int aux [];
  /**
   * @description: 1. 初始化辅助数组aux,使其长度和原数组相同
   *               2. 包装sort,向外只暴露一个数组参数
   */
  public static void sort(int a []){
    aux = new int[a.length];
    sort(a,0,a.length-1);
  }
  /**
   * @description: 基于递归的归并排序算法
   */
  private static void sort (int a [], int low,int high) {
    if(low>=high) { return; } // 终止递归的条件
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    sort(a,low,mid);  // 对左半边递归
    sort(a,mid+1,high);  // 对右半边递归
    merge(a,low,mid,high);  // 单趟合并
  }
 
  /**
   * @description:  单趟合并算法
   * @param a 输入数组
   * @param low,mid,high a[low...high] 是待排序序列,其中a[low...mid]和 a[mid+1...high]已有序
   */
  private static void merge (int a [],int low,int mid,int high) {
    int i = low;    // 游标i,开始时指向待排序序列中左半边的头元素
    int j = mid+1;  // 游标j,开始时指向待排序序列中右半边的头元素
    for(int k=low;k<=high;k++){
      aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置
    }
    for(int k=low;k<=high;k++){
      if(i>mid){
        a[k] = aux[j++]; // 左半边用尽
      }else if(j>high){
        a[k] = aux[i++]; // 右半边用尽
      }else if(aux[j]<aux[i]){
        a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素
      }else {
        a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素
      }
    }
  }
}

 

 

测试代码:

 

public class Test {
  public static void main (String args[]){
    int [] a = {1,6,3,2,9,7,8,1,5,0};
    MergeSort.sort(a);
    for(int i=0;i<a.length;i++){
      System.out.println(a[i]);
    }
  }
}

 

 

出口结果

0
1
1
2
3
5
6
7
9

 

归并排序算法的编码和优化,归并排序及其优化。 

运转轨道
题目

用自底向上的合并排序解答演练 二.二.二

自底向上的相会排序

先归并微型数组,然后再成对归并取得的子数组,直到将全体数组归并到一起,那比标准递归方法所需代码量少。首先是两两归并(每种成分是大大小小为一的数组),然后4肆归并(将多个分寸为2的数组归并成三个有多少个要素的数组),然后是8八归并…

    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,每一趟加倍。最后1个子数组大小只有在数组大小是sz的偶好多倍时才相当于sz(不然会比sz小)。

亚洲必赢官网 25

自底向上的集合排序的集合结果

长度为 N 的数组,自底向上的合并排序需 5/10NlogN 至 NlogN
次比较,最多访问数组 六NlogN 次。

  • 当数主管度为二的幂时,自顶向下和自底向上归并排序所用比较和访问次数相同,只是顺序不一样。
  • 自底向上归并排序适合用链表团协会数量。此措施只需再度组织链表连接就能将链表原地排序(不需成立任何新的链表节点)。

用自顶向下或自底向上形式达成其余分治算法都很自然。归并排序表明,当能用一种“化整为零”方法消除时方可试试另一种“鲁人持竿”的法子。

递归栈深度和调用顺序

 

递归导致的结果是,形成了壹体系有层次、有程序调用顺序的merge,  如下图左侧的写入编号的merge列表

从上到下,是各样merge的顺序调用顺序,一初步调用,
15结尾调用

从右到左,
递归栈由深到浅
,例如 壹,2,四,5的递归深度是如出一辙的,
而三比它们浅贰个层次

亚洲必赢官网 26

 

 

亚洲必赢官网 27

(那里是比照字母排序,
A最小, Z最大)

 

对上图可依据代码来掌握

sort(a,low,mid);      // A
sort(a,mid+1,high);   // B
merge(a,low,mid,high);// C

 

 

率先,在首先层递归的时候,先进入的是率先行的sort方法里(A处),然后随着又进来了第贰层递归的首先行sort方法(A处),
如此继续,由(a,
low,mid)的参数列表可见其递归的倾向是直接向左移动的,直到最后1层递归,所以先导执行merge的目的是a[0]和a[1](上海教室编号一),再然后实施的是最终1层递归的第贰行代码(B处),那时候merge的指标是a[2]和a[3](上海教室编号二)。
再接下来,
再次回到上壹层递归,对曾经稳步的a[0]、a[1]和a[2]、a[3]拓展merge。(上海教室编号三)如此继续,递归的深度不断变浅,
直到对任何数组的左右两半开展merge。 (上海教室编号3)

 

 

代码达成

根据排序算法类的模版得以实现选用排序(提醒:点蓝字查看详情)

    private static Comparable[] aux;    // 归并所需的辅助数组

    public static void sortBU(Comparable[] arr) {
        int N = arr.length;
        aux = new Comparable[N];
        // sz 的初始值为 1 , 每次加倍
        for (int sz = 1; sz < N; sz = sz + sz) {            // sz子数组大小
            for (int lo = 0; lo < N - sz; lo += sz + sz) {  // lo:子数组索引
                // 最后一个子数组的大小,只有在数组大小是 sz 的偶数倍时,才会等于sz,否则会比 sz 小
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
解答

亚洲必赢官网 28

 

排序算法的复杂度

切磋复杂度的首先步是确立三个乘除模型。对排序来说,基于相比较的算法对数组操作方式是由主键比较决定。

尚未其它依照相比的算法能保障使用简单 log(N!) ~ NlogN 次比较将长度为 N
的数组排序
归并排序是壹种渐进最优的依照相比较排序的算法。归并排序在最坏景况下的比较次数和随意基于比较的排序算法所需的至少相比次数都是
~NogN。

递归归并的轨道图像

 

(上边呈现的联结举办了1部分优化,对小数组使用插入排序)

亚洲必赢官网 29

 

亚洲必赢官网 30

 

 

 

基于上文所讲的递归栈和调用顺序,
上面包车型地铁轨迹图像就不难精通了:
从最右边的因素伊始统1,而且左边的数组种类在率先轮合并后,相邻右侧的数组按同样的轨道实行联合,
直到统一出和左边相同长度的行列后,才和左侧合并(递归栈回涨一层)

 

 

亚洲必赢官网 31

 

亚洲必赢官网 32

 

 

属性分析

对此长度为 N 的任意数组,自底向上的联合排序需求 1/2NlgN – NlgN
次比较
,最多访问数组 6NlgN 次。(每一边走访数组 陆N 次,相比较次数
N/二 – N)

当数首席执行官度为 2
的幂
时,自顶向下和自底向上的集合排序所用的正如次数数组访问次数碰巧相同,只是顺序分裂。

自底向上的会见相比较相符用链表组织的数据。

2.2.4

Q&A

  1. 归并排序比希尔排序快啊?
    在实质上选择中,它们运维时刻距离在常数级别。
  2. 为啥不把数组 aux[] 声明为 merge() 方法的1对变量?
    为制止每一遍归并时,尽管归并十分小的数组都创造二个新数组,否则创制新数组将改成归并排序运转时刻首要部分。越来越好的章程是将
    aux[] 变为 sort() 方法的壹些变量,并作为参数字传送给 merge()
    方法。
  3. 当数组中设有双重成分时归并排序品质怎么着?
    若持有因素相同,则归并排序运营时刻是线性的。若有多少个例外重复值,运转时刻是线性对数的(和装有因素都不另行满意相同循环条件)。

依照递归归并排序的优化措施

 

总结

从不其它根据比较的算法能够保险使用简单 lg(N!) – NlgN 次相比较将长度为
N 的数组排序。

归并排序是一种渐进最优的依据相比较排序的算法。

题目

是或不是当且仅当七个输入的子数组都没有丝毫改变时原地归并的肤浅方法才能获取不错的结果?
表达你的下结论,只怕给出2个反例。

一.伍 急速排序

相当慢排序特点包含原地排序(只需1个十分的小的帮衬栈),且将长度为 N
的数组排序所需时日和 NlogN 成正比,内循环比大部分排序算法都要短小。

十分的快排序:是壹种分治排序算法。将二个数组分成三个子数组,将两有的单独地排序。快排和统壹排序是补偿的,归并排序将数组分成七个子数组分别排序,并将平稳的子数组归并以将整个数组排序;快排的排序情势是当五个子数组都纹丝不动时整个数组也理所当然有序了。前者的递归调用爆发在拍卖整个数组之前;后者递归调用爆发在处理任何数组之后。在归并排序中,1个数组被等分为两半;在快排中,切分地点取决于数组的内容。

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^二 / 3回相比,但随即打乱数组能预防那种地方。每一回切分后两子数组之1总是空的境况下相比次数为:N+(N-1)+…+一= N(N+1) / 2,此时日子是平方级别的,空间是线性的。

优化点壹:对小规模子数组使用插入排序

用差异的章程处理小圈圈难点能改进超越八分之四递归算法的属性,因为递归会使小范围难题中方法调用太过频仍,所以创新对它们的处理形式就能创新整个算法。
因为插入排序卓殊简单
因而壹般的话在小数组上比归并排序更加快
那种优化能使归并排序的运作时刻减少百分之十到15%;

 

怎么切换呢?
只要把作为结束递归条件的

  if(low>=high) { return; }

 

改成

    if(low + M>=high) { // 数组长度小于10的时候
      InsertSort.sort(int a [], int low,int high) // 切换到插入排序
      return;
    }

 

就足以了,那样的话,那条语句就具备了多个效益:

 

1.
在合适时候截至递归

二.
当数高管度小于M的时候(high-low <= M),
不开始展览归并排序,而进展插排

 

现实代码:

  private static void sort (int a [], int low,int high) {
    if(low + 10>=high) { // 数组长度小于10的时候
      InsertSort.sort(int a [], int low,int high) // 切换到插入排序
      return;
    } // 终止递归的条件
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    sort(a,low,mid);  // 对左半边递归
    sort(a,mid+1,high);  // 对右半边递归
    merge(a,low,mid,high);  // 单趟合并
  }

 

 

优化方案

①、直接将扶助数组作为参数字传送入,而不直接运用静态数组。
②、对小规模子数组使用插入排序,壹般能够将归并排序的年月缩小 一成 ~
15%;
③、判断测试数组是还是不是曾经平稳,如果 arr[mid] <=
arr[mid+1],我们就认为数组已经是稳步的并跳过merge()
方法,能够是随意有序的子数组算法的运作时刻变为线性的。
4、merge()
方法中不将成分复制到协助数组,节省数组复制的时刻。调用三种排序方法,1种:将数据从输入数组排序到助手数组;另1种:将数据从接济数组排序到输入数组。
驷比不上舌:在各类层次交换输入数组和扶植数组的剧中人物。

解答

正确,必须求四个子数组都维持原状时归并才能博得不错结果。
若是说数组不平稳的话,那么最终不得不获取七个数组的参差不齐。
联合后的数组中,属于原有数组的因素的相持顺序不会被改变。
比如子数组 一 3 一 和 ② 八 伍 原地归并。
结果是 一 2 三 1 八 五,个中 一 三 1 和 贰 8 5 的周旋顺序不变。

 

快排立异

  • 切换来插入排序。对于小数组,快排比插入排序慢;因为递归,快排的sort()措施在小数组中也会调用本人。因而在排序小数组时可切换成插入排序——将sort()中的
    if (hi <= lo) return; 改为
    if (hi <= lo + M){Insertion.sort(a, lo, hi); return;},M
    最好值和系统相关,伍~1五之间平时较好。
  • 3取样切分。使用子数组的一小部分要素的中位数来切分数组,那样切分更加好,代价是需总计中位数。
  • 熵最优的排序。实际应用平时出现含有多量再次成分的数组,3个成分全体再一次的子数组就不需要后续排序了,但前边的算法还会继续切分成越来越小的数组。简单的缓解办法是将数组切分为3片段(详见Dijkstra三向切分),分别对应小于、等于和过量切分元素的数组成分,那种比最近二分更复杂,相关问题有荷兰国旗问题。

亚洲必赢官网 33

3向切分示意图

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

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

优化点贰:  测试待排序连串中左右半边是不是已平稳

 

经过测试待排序种类中左右半边是还是不是业已稳步,
在一如既往的图景下避免合并方法的调用。

 

比如说对单趟合并,大家对a[low…high]中的a[low…mid]和a[mid…high]进展合并

因为a[low…mid]和a[mid…high]自然正是有序的,存在a[low]<a[low+1]…<a[mid]和a[mid+1]<a[mid+2]…<
a[high]那三种关系,
假设判断出a[mid]<=a[mid+1]的话,
不就足以确认保障从而a[low…high]小编正是不要求排序的稳步系列了吧?

 

  private static void sort (int a [], int low,int high) {
    if(low>=high) {
      return;
    } // 终止递归的条件
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    sort(a,low,mid);  // 对左半边递归
    sort(a,mid+1,high);  // 对右半边递归
    if(a[mid]<=a[mid+1]) return; // 避免不必要的归并
    merge(a,low,mid,high);  // 单趟合并
  }

 

 

优化代码
/**
 * 归并排序优化方案(其实并不是特别明显,稳定性也不好)
 *
 * @author TinyDolphin
 * 2017/11/6 11:45.
 */
public class MergePlus {

    // 经验之谈:数组的长度为 7 时,切换
    private static final int CUTOFF = 7;

    private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
        int indexI = lo;
        int indexJ = mid + 1;
        for (int indexK = lo; indexK <= hi; indexK++) {
            if (indexI > mid) {
                dst[indexK] = src[indexJ++];
            } else if (indexJ > hi) {
                dst[indexK] = src[indexI++];
            } else if (less(src[indexJ], src[indexI])) {
                dst[indexK] = src[indexJ++];
            } else {
                dst[indexK] = src[indexI++];
            }
        }
    }

    // 将数组 arr 排序到数组 aux
    private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
        // 优化方案②:应该在子数组长度为 7 的时候切换到插入排序
        if (hi <= lo + CUTOFF) {
            insertionSort(dst, lo, hi);
            return;
        }
        int mid = lo + ((hi - lo) >> 1);

        // 优化方案④:在每个层次交换输入数组和辅助数组的角色
        sort(dst, src, lo, mid);
        sort(dst, src, mid + 1, hi);

        //优化方案③:判断测试数组是否已经有序
        if (!less(src[mid + 1], src[mid])) {
            System.arraycopy(src, lo, dst, lo, hi - lo + 1);
            return;
        }

        // 优化方案④:merge() 方法中不将元素复制到辅助数组
        merge(src, dst, lo, mid, hi);
    }

    public static void sort(Comparable[] arr) {
        // 优化方案①:直接将辅助数组作为参数传入
        Comparable[] aux = arr.clone();
        sort(aux, arr, 0, arr.length - 1);
    }

    private static void insertionSort(Comparable[] arr, int lo, int hi) {
        for (int indexI = lo; indexI <= hi; indexI++) {
            for (int indexJ = indexI; indexJ > lo && less(arr[indexJ], arr[indexJ - 1]); indexJ--) {
                exch(arr, indexJ, indexJ - 1);
            }
        }
    }

    /**
     * 比较两个元素的大小
     *
     * @param comparableA 待比较元素A
     * @param comparableB 待比较元素B
     * @return 若 A < B,返回 true,否则返回 false
     */
    private static boolean less(Comparable comparableA, Comparable comparableB) {
        return comparableA.compareTo(comparableB) < 0;
    }

    /**
     * 将两个元素交换位置
     *
     * @param arr    待交换元素所在的数组
     * @param indexI 第一个元素索引
     * @param indexJ 第二个元素索引
     */
    private static void exch(Comparable[] arr, int indexI, int indexJ) {
        Comparable temp = arr[indexI];
        arr[indexI] = arr[indexJ];
        arr[indexJ] = temp;
    }

    /**
     * 打印数组的内容
     *
     * @param arr 待打印的数组
     */
    private static void show(Comparable[] arr) {
        for (int index = 0; index < arr.length; index++) {
            System.out.print(arr[index] + " ");
        }
        System.out.println();
    }

    /**
     * 判断数组是否有序
     *
     * @param arr 待判断数组
     * @return 若数组有序,返回 true,否则返回 false
     */
    public static boolean isSort(Comparable[] arr) {
        for (int index = 1; index < arr.length; index++) {
            if (less(arr[index], arr[index - 1])) {
                return false;
            }
        }
        return true;
    }
}

2.2.5

《算法导论》上的快排

优化点叁:去除原数组类别到帮扶数组的正片

在上头介绍的基于递归的集合排序的代码中,
大家在历次调用merge方法时候,我们都把a对应的队列拷贝到支持数组aux中来,即

    for(int k=low;k<=high;k++){
      aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置
    }

 

实则,我们得以经过1种**看起来比较逆天的法子把这几个拷贝进度给去除掉。。。。。**

 

为了完成那或多或少,大家要在递归调用的每一种层次调换输入数组和输出数组的剧中人物,从而持续地把输入数组排序到帮扶数组,再将数据从协助数组排序到输入数组。

 

卧槽?!
还有如此骚的操作要怎么搞?
请看:

 

  public static void sort(int a []){
    aux = a.clone(); // 拷贝一个和a所有元素相同的辅助数组
    sort(a,aux,0,a.length-1);
  }
  /**
   * @description: 基于递归的归并排序算法
   */
  private static void sort (int a[], int aux[], int low,int high) {
    if(low>=high) { return; } // 终止递归的条件
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    sort(aux, a,low,mid);  // 对左半边递归
    sort(aux, a,mid+1,high);  // 对右半边递归
    merge(a, aux, low,mid,high);  // 单趟合并
  }

 

在那边大家做了多个操作:

  • 在排序前拷贝贰个和原数组成分完全平等的赞助数组(不再是成立一个空数组了!)
  • 在递归调用的每一种层次交流输入数组和输出数组的剧中人物

 

 

只顾,
外部的sort方法和其中sort方法接收的a和aux参数刚好是倒转的

亚洲必赢官网 34

 亚洲必赢官网 35

 

这般做的话,
大家就能够去除原数组种类到赞助数组的正片了!

 

但是你大概会问:
骚年, 大家要排序的可是原数组a啊! 你即便一十分的大心最终浑然排序的是扶助数组aux而不是原数组a吗?

 

Don’t worry !! 这种气象不会发出
看图:

 

亚洲必赢官网 36

 亚洲必赢官网 37

 

由图示易知,
因为外表sort和merge的参数顺序是1致的, 所以,无论递归进度中协助数组和原数组的角色怎么替换,对最后二次调用的merge而言(将全方位数组左右半边合为有序的操作),  
最终被排为有序的都以原数组,而不是支援数组!

 

 

一切代码:

 

/**
* @Author: HuWan Peng
* @Date Created in 9:44 2017/11/29
*/
public class MergeSort {
  private static int aux [];
  /**
   * @description: 1. 初始化辅助数组aux,使其和原数组元素完全相同
   *               2. 包装sort,向外只暴露一个数组参数
   */
  public static void sort(int a []){
    aux = a.clone(); // 拷贝一个和a所有元素相同的辅助数组
    sort(a,aux,0,a.length-1);
  }
  /**
   * @description: 基于递归的归并排序算法
   */
 
  private static void sort (int a[], int aux[], int low,int high) {
    if(low>=high) { return; } // 终止递归的条件
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    sort(aux, a,low,mid);  // 对左半边递归
    sort(aux, a,mid+1,high);  // 对右半边递归
    merge(a, aux, low,mid,high);  // 单趟合并
  }
 
  /**
   * @description:  单趟合并算法
   * @param a 输入数组
   * @param low,mid,high a[low...high] 是待排序序列,其中a[low...mid]和 a[mid+1...high]已有序
   */
  private static void merge (int a [],int aux [],int low,int mid,int high) {
    int i = low;    // 游标i,开始时指向待排序序列中左半边的头元素
    int j = mid+1;  // 游标j,开始时指向待排序序列中右半边的头元素
    // 这里的for循环拷贝已经去除掉了
    for(int k=low;k<=high;k++){
      if(i>mid){
        a[k] = aux[j++]; // 左半边用尽
      }else if(j>high){
        a[k] = aux[i++]; // 右半边用尽
      }else if(aux[j]<aux[i]){
        a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素
      }else {
        a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素
      }
    }
  }
}

 

 

测试代码和输出结果同上文。

 

优化测试代码

迅速复制数组的艺术】,提示:点击玉高粱红字体查看方法详情。

public class Main {
    public static void main(String[] args) {
        int length = 10000000;  // 千万数据量级别
        Integer[] arr = new Integer[length];
        Integer[] arr2 = new Integer[length];
        for (int index = 0; index < length; index++) {
            arr[index] = new Random().nextInt(length) + 1;
        }
        //高效复制数组的方法
        System.arraycopy(arr, 0, arr2, 0, arr.length);

        long start = System.currentTimeMillis();
        Merge.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("耗费时间:" + (end - start) + "ms");
        assert Merge.isSort(arr);

        start = System.currentTimeMillis();
        MergePlus.sort(arr2);
        end = System.currentTimeMillis();
        System.out.println("耗费时间:" + (end - start) + "ms");
        assert MergePlus.isSort(arr2);

    }

}
题目

当输入数组的分寸 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;
    }
}

亚洲必赢官网 38

quicksort普通版本

听他们讲循环的集合排序(自底向上)

 

基于循环的联合排序又称作自底向上的合并排序

 

优化测试结果

注意:优化结果固然大多,可是当其数组接近平稳的时候,速度有了冲天的升级。

相对级别数据量

留意:编译器默许不适用 assert
质量评定(不过junit测试中适用),所以要运用时要增加参数虚拟机运行参数-ea
具体添加进程,请参见eclipse 和 IDEA
设置虚拟机运行参数

解答

每一回归并子数组的尺寸和11如下:

自顶向下

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] 中4意选择一个要素作为主元。为此,能够将 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);
    }
}

循环归并的核心思维

亚洲必赢官网 39

 亚洲必赢官网 40

 

 

依据循环的代码较为简单,那里就不多废话了

 

/**
* @Author: HuWan Peng
* @Date Created in 23:42 2017/11/30
*/
public class MergeSort2 {
  private static int aux [];
 
  public static void sort(int a []){
    int N = a.length;
    aux = new int [N];
    for (int size =1; size<N;size = size+size){
      for(int low =0;low<N-size;low+=size+size) {
        merge(a,low,low+size-1,Math.min(low+size+size-1,N-1));
      }
    }
  }
 
  private static void merge (int a [],int low,int mid,int high) {
    int i = low;    // 游标i,开始时指向待排序序列中左半边的头元素
    int j = mid+1;  // 游标j,开始时指向待排序序列中右半边的头元素
    for(int k=low;k<=high;k++){
      aux[k] = a[k];
    }
    for(int k=low;k<=high;k++){
      if(i>mid){
        a[k] = aux[j++]; // 左半边用尽
      }else if(j>high){
        a[k] = aux[i++]; // 右半边用尽
      }else if(aux[j]<aux[i]){
        a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素, 取右半边元素
      }else {
        a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素
      }
    }
  }
}

 

 

2.2.6

快排时间复杂度

  • 最坏意况:
    当划分发生的四个子难题分别包括了 n-一 个和 0
    个成分时,划分时间复杂度为 O(n),因为对二个高低为 0
    的数组进行递归调用会直接回到,因而 T(0) =
    O(一),于是算法运维时刻的递归式为:T(n) = T(n-一) + T(0) + O(n) =
    T(n-一)+O(n) = O(n^二)。其余,在输入数组完全有序时,快排时间复杂度仍为
    O(n^二),而插入排序则为 O(n)。

  • 最棒状态:
    partition 获得的五个子难点规模都不超出 n / 二,子难题规模分别为 n / 二和 n / 二 – ①,此时算法运维时刻递归式为:T(n) = 二T(n / 贰) + O(n) =
    O(nlogn)。

  • 平衡的撤销合并:
    快排平均运营时刻更近乎于最佳状态,而非最坏情状。如按 9:1划分,递归树如下:

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

quicksort递归树

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

循环归并的轨道图像

(下图中的sz同地点的变量size)

 

亚洲必赢官网 41

 

 

亚洲必赢官网 42

 亚洲必赢官网 43

 亚洲必赢官网 44

 

 

题目

编排叁个顺序来计量自顶向下和自底向上的集合排序访问数组的准确次数。
行使那几个程序将 N=一 至 51贰 的结果绘成曲线图,并将其和上限 陆NlgN 相相比。

随机化版本
解答

亚洲必赢官网 45

青白是上限,蓝点是自顶向下,红点是自底向上。
鉴于二种排序访问数组的次数是均等的,由此蓝点和红点重合。

一.陆 优先队列

先期队列帮忙除去最大要素和插入成分。基于二叉堆的先行队列,是用数组保存成分并依据一定原则排序,以促成火速地(对数级别)删除最大因素和插入成分。优先队列实际应用包罗模拟系统、职务调度和数值总结等。

透过插入一列成分然后贰个个刨除当中的微乎其微成分,就足以用事先队列实现排序算法。堆排序发源于根据堆的先期队列的落实。

代码

交付绘图部分的代码:

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

先行队列是壹种抽象数据类型,表示了1组值和这一个值的操作。优先队列最器重操作是剔除最大要素和插入成分,

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

先行队列的调用示例

2个优先队列的用例

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

注解归并排序的相比较次数是干Baba递增的(即对于 N>0,C(N+1)>C(N))。

初级完毕

亚洲必赢官网 46

从N个输入找到最大M个成分.png

解答

依据书本给出的命题 G 和命题 H(粤语版 P173/17陆,英文版 P275/27九),
正如次数的下限 C(N) = 四分之二 * NlgN
N 和 lgN 都是干瘪递增且超过零的(N>一),因而 C(N) 也是枯燥递增的

 

堆的定义

在二叉堆数组中,种种成分都要保险大于等于另四个特定岗位的因素。相应地,那一个岗位成分又至少当先等于数组中另三个元素。
堆有序:1棵二叉树的种种结点都超出等于它的八个子结点,根结点是堆有序的贰叉树中的最大结点。

2.2.8

二叉堆表示法

若用指针表示堆有序的2叉树,则各个成分都需两个指针来找它的父节点和四个子节点。但若用完全二叉树,则可只用数组而不需指针。具体方法是将2叉树的节点按层级顺序放入数组,根节点在地点一,其子节点在岗位二和三,而子节点的子节点分别在任务肆,、5、6和七。

二叉堆是一组能用堆有序的一点1滴贰叉树排序的成分,并在数组中按层级存款和储蓄(不用数组第一个职位)

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

亚洲必赢官网 47

堆的代表

壹棵大小为 N 的通通贰叉树的莫斯中国科学技术大学学为 $\lfloor logN\rfloor$

题目

比方将算法 二.4 修改为:
只要 a[mid] <= a[mid+1] 就不调用 merge() 方法,
请证实用归并排序处理二个1度平稳的数组所需的比较次数是线性级别的。

堆的算法

堆达成的相比和置换方法:

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](左半部分的最终2个要素小于右半部分的率先个要素)
那么我们得以从来统壹数组,不需求再做多余的操作

今昔的输入是2个早已排序的数组
算法唯一的可比发生在认清 a[mid] < a[mid + 1] 这些原则时
万壹数组有 N 个因素
正如次数满意 T(N) = 贰 * T(N / 2) + 1, T(1) = 0
转车为非递归格局即为:T(N) = cN / 贰 + N – 一
中间 c 为随机正整数

 

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

若堆的有气象因有些节点变得比它的父节点更加大而被打破,则需经过置换它和它的父节点来修补堆。交流后,该节点比它的四个子节点都大。重复该进程,直到遭受越来越大的父节点。

亚洲必赢官网 48

上浮

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

2.2.9

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

若堆的雷打不动状态因有个别节点比它的七个子节点或内部之1更加小而被打破,则可透过将它和它的三个子节点较大者交流来回复堆。重复该进度,直到它的子节点都比它更加小或到达了堆的底层。

亚洲必赢官网 49

下沉

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

安顿成分:将新元素加到数组末尾,扩展堆的高低并让该新元素上浮到优异岗位。

亚洲必赢官网 50

布署成分

剔除最大要素:从数组顶端删去最大的要素并将数组的最后多个成分放到顶端,减小堆的轻重缓急并让这几个因素下沉到合适岗位。

亚洲必赢官网 51

删去最大因素

  • 听他们讲堆的先行队列

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+3回相比较,删除最大要素操作急需不超越 二lgN 次比较。

表明:两种操作都急需在根节点和堆底之间活动成分,而路径长度不当先lgN。对于路径上的各样节点,删除最大要素急需五回比较(除了堆底元素),贰遍用来找出较大的子节点,二遍用来分明该子节点是还是不是供给上浮。

题目

在库函数中选取 aux[] 那样的静态数组时不稳当的,
因为大概会有多个程序同时利用这几个类。
兑现贰个决不静态数组的 Merge 类,
但也绝不将 aux[] 变为 merge() 的部分变量(请见本书的回应部分)。
提醒:能够将扶助数组作为参数字传送递给递归的 sort() 方法。

多叉堆

一齐三叉堆:对于数组中1至 N 的 N 个成分,位置 k 的节点大于等于位于
三k-一、三k 和 3k+壹 的节点,小于等于位于 (k+一) / 三的节点。须要在树高
log_d(N) 和在每种节点的 d
个子节点找到最大者的代价之间找到折中,这取决于达成细节以及区别操作的预料绝对频繁程度。

解答

合法给出的统1排序达成中在 Sort 方法里起先化了 aux 数组。
源码见:

C#贯彻和法定的贯彻丰硕接近,

首先定义只接受3个参数的公开 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++;
                }
            }
        }
    }
}

 

堆排序

能够把自由优先队列变成壹种排序方法,将有着因素插入3个搜寻最小元素的先期队列,然后再重复调用删去最小成分的操作按顺序删除。用冬日数组达成优先队列这么做一定于实行贰回插入排序,用堆完毕得到堆排序。堆排序分七个等级:

  • 堆的构造:将原始数组重新协会陈设进二个堆中。
  • 下沉排序:从堆中按递减顺序取出全体因素并拿走排序结果。

2.2.10

堆的结构

连年向优先队列插入成分可行,但更火速的艺术是从右到左用 sink()
函数构造子堆。数组各类位置都早已是1个子堆的根节点了,sink()
对于这几个子堆也适用。若3个节点的四个子节点都早正是堆了,则在该节点上调用
sink()
可将它们成为2个堆。开端时只需扫描数组中13分之5因素,因为能够跳过大小为一的子堆。最终在岗位一上调用
sink()
方法,扫描结束。在排序第二品级,堆的构造方法和大家不知不觉想象的例外,因为我们指标是组织3个堆有序的数组并使最大因素位于数组的开头(次大的要素在紧邻)而非构造函数结束的末尾。

用下沉操作由 N 个因素构造堆只需少于 二N 次相比以及个别 N 次调换

题目

神速归并。
兑现一个 merge() 方法,按降序将 a[] 的后半片段复制到 aux[],
接下来将其归并回 a[]
中。那样就足以去掉内循环中检查测试某半边是不是用尽的代码。
留神:那样的排序发生的结果是不地西泮的(请见 二.5.一.⑧ 节)。

下沉排序

将堆中最大要素删除,然后放入堆收缩后数组中空出的岗位,该进程和抉择排序类似(按降序而非升序取出全部因素),但因为堆提供了1种没有排序部分找到最大因素的有效措施,所需比较次数少得多。

亚洲必赢官网 52

堆的布局和下沉排序

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个因素排序,堆排序只需少于 二NlgN+贰N
次比较(以及五分之三次数的沟通),2N 项来自于堆的构造,二NlgN
出自于每回下沉操作最大只怕供给 二lgN 次相比较。

解答

法定同样给出了 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 1九陆3年发现能够经过免去检查成分是或不是到达正确地方来节省时间。在下沉中接二连三直接升级较大的子节点直至到达堆底,然后再使成分上浮到科学地方,那样可以将比较次数缩短八分之四——接近了归并排序所需相比较次数(随机数组)。该方法需额外层空间间,因此实际采纳中唯有当相比较操作代价比较高时才用(例如:将字符串或任何键值较长类型的因素排序时)。

堆排序在排序复杂性商量中有关键地位,因为它是唯一能而且最优地利用空间和岁月的章程——最坏情状下能保障使用
~2NlgN
次比较和永恒的附加空间。当空间相当浮动时(如嵌入式系统或低本钱移动装备)很盛行,因为它只用几行就能兑现较好的习性(甚至机器码也是)。但现代系统很少用,因为它心中无数运用缓存。数组成分很少和相近的别的成分相比较,由此缓存未命中的次数要远超过大多数比较都在相邻成分间进行的算法,如快排、归并排序、甚至是希尔排序。

在大数据量下,要拍卖 TopK 和 Multiway
难点,无法排序(或不也许全装进内部存款和储蓄器),如 十 亿因素中选最大 十二个,则只用七个能积存拾个要素的队列即可。

代码
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.七 排序算法和事先队列的使用

2.2.11

将各个数码排序

前边完毕的排序对象是由实现了Comparable接口的指标组成的数组,那样能够使用
Java 的回调机制将随意落成了
Comparable接口的数据类型排序。达成Comparable接口只需定义1个compareTo()函数并在里面定义该数据类型的分寸关系。Java
中的 String、Integer、Double、File 和 URL都落到实处了Comparable接口。

题目

改进。
落到实处 二.二.二 节所述的对归并排序的三项改进:
加速小数组的排序速度,
检查评定数组是或不是早已平稳以及通过在递归中交流参数来防止复制。

指南针排序

前边使用的不二等秘书籍被喻为指南针排序,因为只处理元素的引用而不运动多少小编。在C/C++中,须求显著建议操作的是多少恐怕指向数据的指针,在
Java
中,指针的操作是隐式的。除了原有数字类型外,操作的连天数据的引用(指针)而非数据作者。

解答

法定达成见:

在 MergeSortX 类里添加二个 CUTOFF
字段,排序时1旦数高管度小于它则平素调用插入排序进行排序。

在调用归并措施前判断第2个有序数组的末尾一个成分是或不是超出第叁个有序数组的首先个因素,
设若超出的话就不必要调用归并了,直接首尾相接即可。

老是归并都急需七个数组,多少个用于存放归并结果,这几个数组中的内容是无所谓的;
另1个则保留了归并前的数组,用于实际的合并进度。
归并甘休后,前三个数组变成归并后的平稳结果(相当于下3次归并时的「归并前数组」),后3个数组中的内容则不再有效。
咱俩能够看到那多少个数组的角色在下3遍归并时刚刚能够交流。

要留心的是,归并次数接二连三三个奇数(右边归并+左边归并+总归并),由此在第三回调用
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);
        }
    }
}

 

打折的调换

动用引用另1个功利是足以无需移动整个因素。对于成分大而键小的数组来说节约是高大的,因为正如只需访问成分一小部分,而排序进度大部分因素都不会被访问到。对于差不多任意大小的要素,引用在一般景象下沟通花费和相比开销大致一样(代价是索要卓殊空间存储引用)。

2.2.12

各样排序方法

Java 的 Comparator 接口允许在2个类中完成两种排序方法。它唯有二个
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
的约数)。
落到实处1个联结措施,使之所需的附加空间压缩到 max(M, N/M):
(i)能够先将1个块看作一个因素,将块的首先个因素作为块的主键,用选拔排序将块排序;
(ii)遍历数组,将第3块和第二块归并,完毕后将第一块和第贰块归并,等等。

选拔相比较器达成优先队列
  • 为 马克斯PQ 添加三个实例变量 comparator
    以及1个构造函数,该构造函数接受2个相比较器作为参数并用它将
    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 的块
对此各样块,用选取排序实行排序
继而遍历数组,将相继块归并起来

稳定性

若一个排序算法能保留数组中重新成分的相对地点则可被称呼稳定的。1部分算法是安静的——插入排序和统壹排序,但选择排序、希尔排序、火速排序和堆排序不稳定。

代码
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++;
                }
            }
        }
    }
}

 

该用哪一类排序

亚洲必赢官网 53

种种排序算法的属性特点

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

2.2.13

标题规约

在使用消除难题 B 的措施来解决难题 A 时,都在将 A 规约为 B。

题目

平均意况的下限。请表达自由基于相比的排序算法的预料相比次数至少为
~NlogN(固然输入成分的装有排列的产出可能率是均等的)。
提醒:比较次数至少是相比较树的外部路径的长度(根结点到叶子结点的不二秘诀长度之和),当树平衡时该值最小。

找出双重成分

在3个 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,十,17
多少个数排序的决策树如下,结点代表相比对应地点上的数。
亚洲必赢官网 54
对此 3五,10,壹7 来说,路径遵从右、左、左,最终取得的结果正是 二 3
一(十,一7,3五)。
大家得以窥见决策树上的每贰个叶子节点都代表1种排列顺序,对于 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) = 二H(k / 二) + k
(加上 k 的来由:左右子树的中度比总体树的莫斯中国科学技术大学学小
一,因而每条路子的长短都必须加 一,总共多加了 k 次)
因此 H(k) = klogk
现在令 k = n!
H(n!) = n!log(n!)
由于每趟排序时咱们只通过某一条路径(上例中大家只经过了右、左、左那条路线)
而且每个途径的面世可能率相等
为此平均比较次数应当为 H(n!) / n! = log(n!) = nlog(n)
证实实现

 

排名

逆序对数难点

2.2.14

中位数与种种计算

一个和排序有关但又不供给完全的要害应用正是找出壹组成分的中位数,有一种万分选拔:找到1组数中第
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/二+N/肆+…)直到找到第
k 个元素,依照等比数列求和公式该和显明低于 2N。

平均来说,基于切分的精选算法运维时刻是线性级其余。

本篇介绍的算法的欧洲经济共同体代码地址:
代码地址

以下是可供参考的博客:
各类排序算法时间复杂度
面试中的排序算法总结
八大排序算法
必须了解的八大种排序算法【java达成】
坐在马桶上看算法:飞快排序

题目

归并1如既往的行列。
编辑3个静态方法,将八个不变的队列作为参数,重回1个集合后的平稳队列。

解答

正如五个静止队列的率先个要素,取较小的三个出队并放入额外建立的连串中。
重新上述手续直到四个连串都为空。

代码
/// <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 个体系,每种队列包涵在那之中3个要素。
始建三个由那 N 个系列组成的种类,然后不断用演习 二.二.1四中的方法将队列的头四个要素归并,
并将结果重新插手到行列结尾,直到队列的种类只剩余三个因素停止。

解答

次第思路标题已经交付,依照题意完毕即可。
Merge 方法能够直接行使前1题的落实。

代码
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

题目

本来的集合排序。
编辑叁个自底向上的联结排序,当供给将多少个子数组排序时可以采纳数组中早已平稳的局地。
先是找到一个平稳的子数组(移动指针直到最近因素比上3个要素小截至),
接下来再找出另多个并将它们归并。
听别人说数组大小和数组中递增子数组的最大尺寸分析算法的运转时刻。

解答

当然归并排序的三个示范如下图所示:

亚洲必赢官网 55
主导历程和自底向上的联合排序类似,只是每一回归并的块大小不肯定相同。

日子分析

亚洲必赢官网 56

随着有序块的变大,排序耗费时间会减少,但增强的数额级会变高(归并的平分块大小变大了)。

代码
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

题目

链表排序。
兑现对链表的本来排序
(那是将链表排序的最佳点子,因为它不须要相当的空中且运转时刻是线性对数级别的)。

解答

排序情势和 二.二.1⑥ 10分类似,不再赘言,那里介绍一下归并方法。
亚洲必赢官网 57
如 gif
图所示,先把要统1的五个链表拆出来,随后鲜明表头地点,然后进行联合即可。
归并终止后回到 first。

结果分析如下图所示:
亚洲必赢官网 58
乘势有序部分的增多,对于同样大小的数组自然归并排序的耗费时间会缩小。
对于有序部分同样的境况,随着数组大小的倍增,耗费时间显示了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

题目

打乱链表。
完成二个分治算法,使用线性对数级别的时日和对数级别的附加空间随意打乱一条链表。

解答

能够在用归并排序的章程做。
亚洲必赢官网 ,将归并时取两边较小的因素改为随机取1侧的值,即可达成打乱的效果。
算法的分析和平常归并排序1致,满足标题要求。

代码

分治法打乱链表的落实。

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

题目

倒置。
编写制定1个线性对数级别的算法总计给定数组中“倒置”数量
(即插入排序所需的交流次数,请见 二.1 节)。
其1数目和 Kendall tau 距离有关,请见 2.5 节。

解答

官方完毕:

实质上假设在归并排序的时候总结 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

题目

直接排序。
编辑一个不更改数组的集合排序,
它回到2个 int[] 数组 perm,其中 perm[i] 的值是原数组中第 i
小的要素的地点。

解答

合法完结:

把 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

题目

壹式3份。
加以七个列表,各类列表中包蕴 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

题目

三向归并排序。
1经每回我们是把数组分成八个部分而不是八个部分并将它们分别排序。
然后开展3向归并。
那种算法的运维时刻的增高数量级是稍微。

解答

亚洲必赢官网 59
增强数据级为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

题目

改进。
用试验评估正文中所提到的合并排序的三项改革(请见练习 二.贰.1壹)的意义,
并相比正文中落到实处的联结排序和练习 二.贰.10 所落成的合并排序之间的性质。
依据经验给出应该在曾几何时为子数组切换来插入排序。

解答

亚洲必赢官网 60
阈值合适时,大致会有1/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

题目

句斟字酌的静止测试。
在尝试中用大型随机数组评估练习 贰.二.八 所做的改动的功效。
基于经验用 N(被排序的原始数组的大大小小)的函数描述条件语句(a[mid] <=
a[mid + 1])创建(无论数组是还是不是有序)的次数。

解答

亚洲必赢官网 61
约为 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 的取值无关首要,实验也验证了那或多或少。
亚洲必赢官网 62
算法大概能够分为以下多少个步骤
首先将数组划为 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 会调用数11遍,而用于运维递归的 Sort
方法只会调用二次。

亚洲必赢官网 63

代码
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

题目

子数CEO度。
用归并将重型随机数组排序,
基于经验用 N
(某次归并时四个子数组的长短之和)的函数预计当1个子数组用尽时另一个子数组的平均长度。

解答

大体上会是三个对数函数,用 Excel 做了简便易行的拟合。
亚洲必赢官网 64

代码
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 比较自顶向下和自底向上的联合排序的特性。

解答

自底向上会快壹些,省去了递归进程中函数重复调用的时光。
亚洲必赢官网 65

代码
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^三、10^陆 和 十^九,类型为 Long
的任意主键数组,根据经验给出自然的晤面排序(请见练习二.2.1陆)所急需的遍数。
升迁:不须求实现这些排序(甚至不要求转移全体完整的 63位主键)也能到位那道练习。

解答

全然有序时只必要1遍归并(直接出口),
逆序时必要 n – 一 次归并(退化为插入排序),
平均需求 n/2 次归并。
所以个别供给 500,四千00,四千00000 次归并。

网站地图xml地图