威尼斯人线上娱乐

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

13 4月 , 2019  

写在头里

全套项目都托管在了 Github
上:

搜寻更为方便的本子见:https://alg4.ikesnowy.com

那1节内容也许会用到的库文件有 Merge,同样在 Github 上能够找到。

善用 Ctrl + F 查找难题。

一 起码排序算法

排序算法关心的重大是重新排列数组成分,其中各个成分都有2个主键。排序算法是将有着因素主键按某种情势排列(经常是循序渐进轻重缓急或然字母顺序)。排序后索引较大的主键大于等于索引较小的主键。

参考资料

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

 

Q:什么是归并排序?
A:它是确立在统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和UQX56L)都完结了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)被调用时分别重返三个负整数、零和3个正整数(-一、0和一)。壹般的话,若
v 和 w 不能够相比较大概双方之壹是 null,v.compareTo(w) 将会抛出1个不胜。

归并排序的定义

归并排序的兑现本人是这么来叙述的:先对少数多少个要素通过两两集合的情势展开排序,形成贰个长短稍大片段的不变体系。然后在此基础上,对三个长度稍大学一年级部分的静止系列再开始展览两两合并,形成二个长短更加大的雷打不动类别,有序连串的的长度不断增高,直到覆盖全数数组的分寸结束,归并排序就完了了。

 

着力思虑

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

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

缺点?所需的额外层空间间和 N 成正比。

2.2.1

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

分选排序内循环只是在可比当前成分与当前已知最小成分(以及将近来索引加1和反省是或不是代码越界),交流成分的代码写到了内循环之外,每趟调换都能排定二个因素,由此交流总次数是N。所以算法总的时间功效取决于相比次数。

  • 长度为 N 的数组,选用排序须要大约 (N^二) / 2 次相比较和 N 次调换

0 到 N-一 的任意 i 都会开始展览二次交流和 N-一-i 次比较,因而总共有 N
次调换以及(N-1)+(N-二)+…+2+壹 = N(N-1) / 2 ~ N^2 / 2次比较

  • 采取排序有五个明显特点:
  1. 运维时刻和输入非亲非故。为了找出最小成分而扫描二回数组并无法为下三回扫描提供什么音讯。那种情况在好几景况下是通病,因为3个1度平稳的数组或是主键全体相当于的数组和1个因素随机排列的数组所用的排序时间同1长,而其余算法更擅长利用输入的发端状态。
  2. 数量移动最少。每趟沟通都会转移八个数组元素的值,因而选取排序用了N次沟通——沟通次数和数组大小是线性关系,而任何任何算法都不抱有那么些特性(抢先陆一%提升数量级都以线性对数或平方级别)。

归并排序的二种完成格局:递归和巡回

归并排序有二种达成格局:
基于递归的集合排序和基于循环的集合排序
。(也叫自顶向下的联合排序自底向上的合并排序

 

那两种归并算法即便落成格局各异,但还是有共同之处的:

 

1.
无论是基于递归照旧循环的统壹排序,
它们调用的骨干措施都是相同的:落成1趟合并的算法,即三个曾经平稳的数组体系合并成二个更加大的雷打不动数组系列 
(前提是四个原系列都以铁定的事情的!)

2.
从排序轨迹上看,合并系列的长短都以从小(3个因素)到大(整个数组)增进

 

 

原地归并的抽象方法

Q:为何须求原地归并?
A:因为用归并将三个大数组排序时,须求开始展览数次归并,而且每便归并会都制造3个新数组来囤积排序结果会推动难题。

Q:原地归并实现了哪些?
A:能够先将前半局部排序,再将后半片段排序,然后数组中移动成分而不需求利用额外的上空(将多个静止的数组归并为贰个稳步的数组)

Q:怎样贯彻归并?
A:成立1个适用大小的数组,然后将多少个输入数组中的成分三个个多年方法这几个数组中。

代码达成
根据排序算法类的模版贯彻归并排序(提示:点蓝字查看详情)

    /**
     * 将子数组 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.2 插入排序

插入排序:整理扑克时相似都以一施晓东张来,将每张牌插入到任何已经平稳的牌中的适当地点。在总括机完毕中,为了要给插入成分腾出空间,必要将其它具备因素在插入在此之前都向右移动一人。这种算法叫做插入排序

  • 与接纳排序1样,当前目录左侧全数因素都以稳步的,但它们最后地方还不显明,为了给更加小成分腾出空间,它们或者会被移位,但当索引到达数组右端时,数组排序就达成了。
  • 与选取排序区别的是,插入排序所需时日取决于输入兰月素的开头顺序。如对近似平稳的数组排序要比自由数组快很多。

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

思虑一般意况下部分有序的数组。倒置指的是数组中多少个顺序颠倒的成分。比如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样,必要相比的次数超过等于倒置的多寡,小于等于倒置的数据增进数组的轻重缓急再减1。要大幅进步插入排序速度并简单,只需在内循环军长较大因素都向右移而不一而再交流七个成分(那样访问数组次数就能减半),即上述第一种完成。

单趟归并算法

 

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

由于以上的原地归并只能将多少个不变的数组归并成多个稳步的数组,所以得依据原地归并的空洞去贯彻一种递归归并。

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

Q:为啥它能将正确的排序?
A:假设它能将四个子数组排序,那么它就可以透过归并八个子数组来将全部数组排序。

解答

威尼斯人线上娱乐 1

 

一.三 希尔排序

希尔排序:是一种基于插入排序的排序算法。对于大规模乱序数组插入排序不快,因为它只会换换相邻的要素,若最小成分在数组最后,则对其急需活动N-3遍。希尔排序革新了插入排序,交流不相邻的因素以对数组的壹部分进展排序,并最后用插入排序将壹部分有序的数组排序。

  • h有序数组:数组中自由间隔为 h 的成分都纹丝不动。即贰个 h有序数组
    就是 h
    个相互独立的雷打不动数组编织在一道构成的一个数组。若h极大,则可将成分移到很远地点,为促成越来越小的h有序创立有益于。

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

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

算法实例解释可参照:
白话经典算法类别之③希尔排序的完成
图解排序算法(贰)之希尔排序

希尔排序更敏捷原因是它权衡了子数组的局面和有序性。排序之初,各种子数组都非常的短,排序之后子数组都以有的有序的,那三种景况都适合插入排序。子数组部分有序的程度在于递增类别的选择。

单趟排序的贯彻分析

 

下边作者先介绍三种分裂归并算法调用的国有艺术,
即实现单趟归并的算法。(多个曾经稳步的数组连串合并成三个更加大的不变数组系列)

 

在始发排序前创办有多个和原数组a长度相同的空的拉拉扯扯数组aux

 

单趟归并的经过如下:

 

一. 
率先将原数组中的待排序类别拷贝进帮助数组的如出一辙地方中,即将a[low…high]拷贝进aux[low…high]中

2.  支持数组aux的天职有两项:相比成分大小,
并在aux中各种获得有序的因素放入原数组a中

(通过一使aux和a在low-high的岗位是完全相同的!那是促成的基础)

3. 
因为aux[low…high]由两段有序的行列:aux[low…mid]和aux[mid…high]整合,
那里称之为aux1和aux2,大家要做的便是从aux一和aux2的底部成分开端,相比双方成分的轻重缓急。将较小的要素放入原数组a中(若a[0]已被占则放在a[1]…依次类推),并得到较小成分的下一个成分,
和另二个体系中较大的因素比较
。因为前提是aux一和aux二都以有序的,所以通过那种办法我们能获取更加长的平稳种类

4.  如果aux的两段连串中,在那之中一段中的全数因素都已”相比”完了,
取得另壹段类别中多余的成分,全体放入原数组a的剩余地点。

 

经过三和肆的落真实情状势

  • 安装七个游标 i 和 j
    用于“成分相比较”
    (在aux中进行):变量,i 和
    j,分别表示左游标和右游标,初阶时分别指向aux[low]和aux[mid]
  • 设置游标k用于鲜明在a中放置成分的任务归并排序及其优化,归并排序算法的编码和优化。(在a中进行),k在开头时候指向a[low]
  • 完全上来说i,
    j, k的来头都以向右移动的

 

进度叁和四的图示解说

 

图A

威尼斯人线上娱乐 2

 

 

 

威尼斯人线上娱乐 3

重组方面包车型客车长河③, 
相比较 i 和 j 当前所指的aux中的成分的大大小小,
取得个中相比大的老大成分(例如上海体育场地中的i),将其放入数组a中,
此时(在图中假诺情状下): i加一,左游标右移。  同时k也加一,
k游标也向右移动

 

图B

威尼斯人线上娱乐 4

 

 

威尼斯人线上娱乐 5

组合地点的长河4,
在 i 和 j 都向右移动的长河中,
在图中若是意况下,因为j当前所指的成分(图中地点)大于左半边即a[low…mid]的有所因素,导致
i 不断充实(右移)且通过了分界(mid),
所以那时候就不要求比较了,只要把j当前所指地点到high的成分都搬到原数组中,填满原数组中剩下的职位,
单趟归并就到位了, 在那一段进度中 j 延续加1,右游标延续右移。 
同时k也延续加一, k游标也总是右移, 直到 j == high且k == high截至

 

据书上说上边的发挥,
总括出单趟归并算法中最重点的5个规范判断情形:

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

 

 

运转轨道

自顶向下的联结排序运营轨道

2.2.2

1.四 归并排序

归并排序:将3个数组排序,能够先(递归地)将它分成两半分头排序,然后将结果归并起来。归并排序将长度为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,那1部分代码上文未提交

 

代码达成

根据排序算法类的模版福寿康宁采纳排序(提示:点蓝字查看详情)

    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);     // 归并结果
    }
题目

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

单趟排序的进度图解

 

为了更详实的叙说单趟排序的长河,下边在上边的图A和图B的根底上交给每一步的图解:

 

小编们要排序的队列是
2 肆 伍 九 一 三 陆 柒, 统一的前提是二 肆 5
玖 和 一 3 陆 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 的数组,自顶向下的联结排序须求 2/四NlogN 至 NlogN 次正如
  2. 对此长度为 N 的数组,自顶向下的集合排序最多须求拜访数组 6NlogN 次

归并排序所需时间和 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

 

 

运行轨道
题目

用自底向上的集合排序解答练习 贰.二.二

自底向上的联合排序

先归并微型数组,然后再成对归并得到的子数组,直到将全部数组归并到1起,这比标准递归方法所需代码量少。首先是两两归并(每种成分是高低为一的数组),然后4肆归并(将多少个高低为贰的数组归并成贰个有五个成分的数组),然后是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初步值为一,每一遍加倍。最终3个子数组大小只有在数组大小是sz的偶好多倍时才也正是sz(不然会比sz小)。

威尼斯人线上娱乐 25

自底向上的见面排序的会晤结果

长度为 N 的数组,自底向上的统1排序需 四分之二NlogN 至 NlogN
次正如,最多访问数组 陆NlogN 次。

  • 当数COO度为贰的幂时,自顶向下和自底向上归并排序所用相比较和走访次数相同,只是顺序差异。
  • 自底向上归并排序适合用链表团组织数量。此情势只需重新协会链表连接就能将链表原地排序(不需成立任何新的链表节点)。

用自顶向下或自底向上格局贯彻任何分治算法都很自然。归并排序表达,当能用壹种“化整为零”方法消除时能够尝试另一种“奉公守法”的主意。

递归栈深度和调用顺序

 

递归导致的结果是,形成了1多元有层次、井井有理调用顺序的merge,  如下图左侧的写入编号的merge列表

从上到下,是各样merge的顺序调用顺序,一初叶调用,
壹5终极调用

从右到左,
递归栈由深到浅
,例如 1,二,4,五的递归深度是均等的,
而三比它们浅二个层次

威尼斯人线上娱乐 26

 

 

威尼斯人线上娱乐 27

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

 

对上航海用体育场地可依据代码来明白

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

 

 

第3,在率先层递归的时候,先进入的是第3行的sort方法里(A处),然后随即又进入了第二层递归的率先行sort方法(A处),
如此继续,由(a,
low,mid)的参数列表可见其递归的大方向是一向向左移动的,直到最后1层递归,所以首先执行merge的靶子是a[0]和a[1](上航海用体育地方编号一),再然后进行的是最后一层递归的第一行代码(B处),这时候merge的靶子是a[2]和a[3](上图编号2)。
再接下来,
再次回到上一层递归,对曾经平稳的a[0]、a[1]和a[2]、a[3]举行merge。(上图编号三)如此继续,递归的深度不断变浅,
直到对任何数组的左右两半开始展览merge。 (上海教室编号三)

 

 

代码达成

根据排序算法类的模板兑现选择排序(提示:点蓝字查看详情)

    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

 

排序算法的复杂度

钻探复杂度的首先步是创建1个划算模型。对排序来说,基于比较的算法对数组操作格局是由主键相比决定。

未曾别的依照相比的算法能保障使用有限 log(N!) ~ NlogN 次相比较将长度为 N
的数组排序
归并排序是一种渐进最优的基于比较排序的算法。归并排序在最坏情状下的相比较次数和4意基于比较的排序算法所需的足足相比较次数皆以
~NogN。

递归归并的轨迹图像

 

(上边体现的联合实行了1些优化,对小数组使用插入排序)

威尼斯人线上娱乐 29

 

威尼斯人线上娱乐 30

 

 

 

故事上文所讲的递归栈和调用顺序,
上边的轨道图像就简单领会了:
从最左边的元素早先联合,而且左侧的数组系列在首先轮合并后,相邻左侧的数组按同样的轨迹举办统一,
直到联合出和左手相同长度的体系后,才和左边合并(递归栈上涨1层)

 

 

威尼斯人线上娱乐 31

 

威尼斯人线上娱乐 32

 

 

性情分析

对于长度为 N 的任意数组,自底向上的晤面排序供给 1/2NlgN – NlgN
次比较
,最多做客数组 陆NlgN 次。(每一边走访数组 陆N 次,相比较次数
N/贰 – N)

当数老总度为 2
的幂
时,自顶向下和自底向上的合并排序所用的比较次数数组访问次数赶巧相同,只是顺序分化。

自底向上的统一相比相符用链表协会的数据。

2.2.4

Q&A

  1. 归并排序比希尔排序快啊?
    在实际应用中,它们运维时刻距离在常数级别。
  2. 何以不把数组 aux[] 声明为 merge() 方法的壹部分变量?
    为幸免每一遍归并时,就算归并一点都不大的数组都创制叁个新数组,不然创设新数组将改成归并排序运转时刻首要部分。更加好的办法是将
    aux[] 变为 sort() 方法的壹些变量,并视作参数字传送给 merge()
    方法。
  3. 当数组中存在重新成分时归并排序品质怎么样?
    若持有因素相同,则归并排序运营时刻是线性的。若有四个区别重复值,运营时刻是线性对数的(和富有因素都不另行知足相同循环条件)。

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

 

总结

平素不其他据悉比较的算法能够确认保障使用简单 lg(N!) – NlgN 次相比较将长度为
N 的数组排序。

归并排序是一种渐进最优的遵照比较排序的算法。

题目

是否当且仅当七个输入的子数组都稳步时原地归并的抽象方法才能博得正确的结果?
证实你的定论,或许给出贰个反例。

一.5 急忙排序

迅猛排序特点包涵原地排序(只需二个非常的小的协理栈),且将长度为 N
的数组排序所需时日和 NlogN 成正比,内循环比半数以上排序算法都要短小。

迅猛排序:是壹种分治排序算法。将2个数组分成四个子数组,将两部分单独地排序。快排和归并排序是填补的,归并排序将数组分成七个子数组分别排序,并将有序的子数组归并以将全部数组排序;快排的排序方式是当三个子数组都原封不动时整个数组也自然有序了。前者的递归调用爆发在拍卖整个数组在此以前;后者递归调用发生在处理任何数组之后。在归并排序中,三个数组被等分为两半;在快排中,切分地点取决于数组的始末。

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^二 / 1次相比较,但随即打乱数组能预防那种气象。每趟切分后两子数组之壹总是空的图景下比较次数为:N+(N-壹)+…+1= N(N+一) / 二,此时光阴是平方级其余,空间是线性的。

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

用不一样的法子处理小框框难点能革新大部分递归算法的习性,因为递归会使小圈圈难点中方法调用太过多次,所以立异对它们的处理办法就能立异整个算法。
因为插入排序非凡不难
由此一般的话在小数组上比归并排序越来越快
那种优化能使归并排序的周转时刻减少1/10到15%;

 

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

  if(low>=high) { return; }

 

改成

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

 

就足以了,那样的话,那条语句就颇具了八个成效:

 

一.
在方便时候停止递归

二.
当数老板度小于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);  // 单趟合并
  }

 

 

优化方案

①、直白将援救数组作为参数字传送入,而不直接动用静态数组。
②、对小规模子数组使用插入排序,1般可以将归并排序的岁月收缩 1/10 ~
15%;
③、看清测试数组是或不是已经稳步,如果 arr[mid] <=
arr[mid+1],大家就觉着数组已经是严守原地的并跳过merge()
方法,可以是随意有序的子数组算法的运行时刻变为线性的。
4、merge()
方法中不将元素复制到帮忙数组,节约数组复制的时刻。调用三种排序方法,1种:将数据从输入数组排序到援助数组;另1种:将数据从支持数组排序到输入数组。
重要:在每种层次沟通输入数组和帮扶数组的剧中人物。

解答

是的,供给求多少个子数组都稳步时归并才能博得正确结果。
如若说数组不平稳的话,那么最终不得不获取五个数组的交集。
集合后的数组中,属于原有数组的要素的对峙顺序不会被改变。
比如说子数组 一 三 一 和 二 八 伍 原地归并。
结果是 1 二 三 一 八 ⑤,个中 壹 叁 壹 和 二 八 伍 的周旋顺序不变。

 

快排立异

  • 切换来插入排序。对于小数组,快排比插入排序慢;因为递归,快排的sort()方法在小数组中也会调用自身。由此在排序小数组时可切换成插入排序——将sort()中的
    if (hi <= lo) return; 改为
    if (hi <= lo + M){Insertion.sort(a, lo, hi); return;},M
    最好值和系统相关,伍~15之间平时较好。
  • 3取样切分。使用子数组的一小部分成分的中位数来切分数组,这样切分越来越好,代价是需总计中位数。
  • 熵最优的排序。实际应用平时出现含有大批量再一次成分的数组,一个成分全体重新的子数组就不须求延续排序了,但前边的算法还会一连切分成越来越小的数组。不难的消除情势是将数组切分为三部分(详见Dijkstra三向切分),分别对应小于、等于和超乎切分成分的数组成分,那种比当下二分更复杂,相关题材有荷兰王国国旗问题。

威尼斯人线上娱乐 33

叁向切分示意图

  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向切分快排是线性的。对于随意分布的输入,最优的基于比较的算法平均所需相比较次数和3向切分快排平均所需相比次数相互处于常数因子范围内。

优化点2:  测试待排序种类中左右半边是还是不是已板上钉钉

 

经过测试待排序连串中左右半边是还是不是业已稳步,
在有序的意况下防止合并方法的调用。

 

诸如对单趟合并,大家对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]拷贝到辅助数组的相同位置
    }

 

其实,大家得以经过一种**看起来相比逆天的主意把那么些拷贝进程给去除掉。。。。。**

 

为了达到这点,大家要在递归调用的各样层次沟通输入数组和出口数组的角色,从而持续地把输入数组排序到帮忙数组,再将数据从协理数组排序到输入数组。

 

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

 

  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);  // 单趟合并
  }

 

在那里大家做了五个操作:

  • 在排序前拷贝2个和原数组成分完全等同的帮手数组(不再是创造一个空数组了!)
  • 在递归调用的各类层次沟通输入数组和输出数组的剧中人物

 

 

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

威尼斯人线上娱乐 34

 威尼斯人线上娱乐 35

 

那样做的话,
大家就足以去除原数组连串到帮助数组的正片了!

 

但是您可能会问:
骚年, 大家要排序的可是原数组a啊! 你就算1极大心最终浑然排序的是协理数组aux而不是原数组a吗?

 

Don’t worry !! 那种景色不会生出
看图:

 

威尼斯人线上娱乐 36

 威尼斯人线上娱乐 37

 

由图示易知,
因为表面sort和merge的参数顺序是平等的, 所以,无论递归进程中扶助数组和原数组的剧中人物怎么替换,对最后二次调用的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=3九时,给来自顶向下和自底向上的集合排序中各次归并子数组的轻重缓急及顺序。

快排普通版本
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
设置虚拟机运行参数

解答

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

自顶向下

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

自底向上

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

 

快排随机化版本

引进随机性,能够使算法对于拥有的输入都能博取较好的愿意品质。在快排中接纳私行取样的随机化技术——从子数组
A[p...r] 中随意选拔三个要素作为主元。为此,能够将 A[r] 与从
A[p...r] 中随心所欲选出的三个成分交流来保险主元 x = A[r]
是等可能率地从子数组的 r-p+3个因素中赢得的。因为主元是随机选的,期望在平均情形下对输入数组的撤销合并是相比较均衡的。

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(1),于是算法运转时刻的递归式为:T(n) = T(n-一) + T(0) + O(n) =
    T(n-壹)+O(n) = O(n^2)。其它,在输入数组完全有序时,快排时间复杂度仍为
    O(n^二),而插入排序则为 O(n)。

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

  • 平衡的分开:
    快排平均运维时刻更接近于最佳状态,而非最坏情形。如按 玖:一分割,递归树如下:

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

quicksort递归树

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

循环归并的轨道图像

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

 

威尼斯人线上娱乐 41

 

 

威尼斯人线上娱乐 42

 威尼斯人线上娱乐 43

 威尼斯人线上娱乐 44

 

 

题目

编纂二个主次来总括自顶向下和自底向上的联合排序访问数组的精确次数。
采用那一个程序将 N=壹 至 512 的结果绘成曲线图,并将其和上限 6NlgN 相相比。

随机化版本
解答

威尼斯人线上娱乐 45

藏蓝色是上限,蓝点是自顶向下,红点是自底向上。
由于三种排序访问数组的次数是1致的,由此蓝点和红点重合。

1.陆 优先队列

优先队列援助删除最大要素和插入元素。基于二叉堆的优先队列,是用数组保存成分并服从一定标准排序,以完成火速地(对数级别)删除最大要素和插入成分。优先队列实际行使包罗模拟系统、职务调度和数值总括等。

经过插入1列成分然后一个个刨除个中的细微元素,就可以用事先队列完结排序算法。堆排序起点于依照堆的先期队列的贯彻。

代码

交由绘图部分的代码:

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

预先队列的调用示例

一个先行队列的用例

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/176,英文版 P275/27九),
正如次数的下限 C(N) = 八分之四 * NlgN
N 和 lgN 都以枯燥递增且高于零的(N>壹),因而 C(N) 也是乏味递增的

 

堆的定义

在2叉堆数组中,每种成分都要有限支撑大于等于另八个特定岗位的成分。相应地,那一个地方成分又至少超越等于数组中另八个要素。
堆有序:1棵二叉树的每种结点都超越等于它的多少个子结点,根结点是堆有序的二叉树中的最大结点。

2.2.8

2叉堆表示法

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

二叉堆是壹组能用堆有序的一心二叉树排序的因素,并在数组中按层级存储(不用数组第二个职位)

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

威尼斯人线上娱乐 47

堆的意味

壹棵大小为 N 的一心2叉树的可观为 $\lfloor logN\rfloor$

题目

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

堆的算法

堆完毕的可比和置换方法:

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

修改后的算法对已经稳步的景色做了优化
数组对半切分并排序后,
如果 a[mid] < a[mid +
1](左半片段的尾声1个成分小于右半部分的首先个因素)
那么大家得以一向统一数组,不须要再做多余的操作

现在的输入是二个已经排序的数组
算法唯一的比较发生在认清 a[mid] < a[mid + 1] 那几个规则时
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

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

若堆的不变状态因某些节点比它的三个子节点或内部之壹越来越小而被打破,则可透过将它和它的八个子节点较大者调换到过来堆。重复该进度,直到它的子节点都比它越来越小或到达了堆的底部。

威尼斯人线上娱乐 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+1回比较,去除最大因素操作内需不当先 2lgN 次相比。

证实:两种操作都亟需在根节点和堆底之间活动成分,而路径长度不超过lgN。对于路径上的每一种节点,去除最大要素需求三回相比较(除了堆底成分),3次用来找出较大的子节点,三遍用来规定该子节点是或不是须要上浮。

题目

在库函数中应用 aux[] 那样的静态数组时不妥善的,
因为恐怕会有多少个程序同时选用那几个类。
贯彻3个不用静态数组的 Merge 类,
但也休想将 aux[] 变为 merge() 的壹部分变量(请见本书的回应部分)。
唤醒:能够将扶持数组作为参数字传送递给递归的 sort() 方法。

多叉堆

统统3叉堆:对于数组中1至 N 的 N 个要素,地方 k 的节点大于等于位于
三k-一、3k 和 3k+一 的节点,小于等于位于 (k+一) / 三的节点。须要在树高
log_d(N) 和在各种节点的 d
个子节点找到最大者的代价之间找到折中,这取决于完结细节以及分裂操作的意料相对频仍程度。

解答

合法给出的会师排序落成中在 Sort 方法里发轫化了 aux 数组。
源码见:

C#达成和合法的兑现丰富接近,

先是定义只接受八个参数的公开 Sort 方法,在这几个法子里面开始化 aux
数组。

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

接下来建立三个私有的递归 Sort 方法抓实在的排序操作。

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

累加一个未曾子舆数的构造函数,在 insert() 中添加将数老总度加倍的代码,在
delMax() 中添加将数经理度减半的代码。

代码
using System;

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

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

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

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

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

 

堆排序

能够把自由优先队列变成1种排序方法,将具备因素插入二个摸索最小元素的事先队列,然后再重新调用剔除最小成分的操作按梯次删除。用冬日数组达成优先队列这么做一定于实行2次插入排序,用堆完结获得堆排序。堆排序分四个级次:

  • 堆的构造:将原始数组重新组织陈设进五个堆中。
  • 下沉排序:从堆中按递减顺序取出全数因素并获得排序结果。

2.2.10

堆的结构

接连向优先队列插入成分可行,但更连忙的主意是从右到左用 sink()
函数构造子堆。数组各种地方都早已是3个子堆的根节点了,sink()
对于这么些子堆也适用。若一个节点的四个子节点都早已是堆了,则在该节点上调用
sink()
可将它们成为三个堆。起始时只需扫描数组中一半要素,因为能够跳过大小为一的子堆。最终在职位1上调用
sink()
方法,扫描甘休。在排序第二阶段,堆的构造方法和大家不知不觉想象的不等,因为大家目的是布局多个堆有序的数组并使最大因素位于数组的起来(次大的成分在周围)而非构造函数截至的最后。

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

题目

飞速归并。
落到实处3个 merge() 方法,按降序将 a[] 的后半有个别复制到 aux[],
下一场将其归并回 a[]
中。这样就能够去掉内循环中检查评定某半边是还是不是用尽的代码。
注意:那样的排序发生的结果是不稳定的(请见 二.伍.壹.8 节)。

下沉排序

将堆中最大要素删除,然后放入堆裁减后数组中空出的职位,该进程和甄选排序类似(按降序而非升序取出全数因素),但因为堆提供了一种未有排序部分找到最大要素的有效个性局,所需比较次数少得多。

威尼斯人线上娱乐 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 一96四年发现能够经过免去反省成分是不是到达正确地方来节省时间。在下沉中接2连三直接提高较大的子节点直至到达堆底,然后再使成分上浮到正确地方,那样能够将比较次数收缩二分之一——接近了归并排序所需相比较次数(随机数组)。该格局需额外层空间间,因而实际应用中唯有当相比操作代价比较高时才用(例如:将字符串或其余键值较长类型的因素排序时)。

堆排序在排序复杂性研商中有根本地位,因为它是绝无仅有能而且最优地利用空间和时间的法子——最坏情形下能确认保证使用
~②NlgN
次相比和平昔的额外空间。当空间很是不安时(如嵌入式系统或低本钱移动装备)极流行,因为它只用几行就能落到实处较好的个性(甚至机器码也是)。但现代连串很少用,因为它无法运用缓存。数组成分很少和隔壁的其余元素比较,由此缓存未命中的次数要远高于大多数相比都在左近元素间实行的算法,如快排、归并排序、甚至是希尔排序。

在大数据量下,要处理 TopK 和 Multiway
难题,无法排序(或无法全装进内部存款和储蓄器),如 10 亿要素中选最大 拾三个,则只用贰个能储存13个成分的类别即可。

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

 

一.柒 排序算法和先行队列的选择

2.2.11

将各样数据排序

眼前实现的排序对象是由完毕了Comparable接口的对象组成的数组,那样能够采纳Java 的回调机制将轻易完成了
Comparable接口的数据类型排序。完成Comparable接口只需定义五个compareTo()函数并在里边定义该数据类型的深浅关系。Java
中的 String、Integer、Double、File 和 URL都完结了Comparable接口。

题目

改进。
兑现 二.二.二 节所述的对归并排序的3项改进:
加快小数组的排序速度,
检查评定数组是或不是已经稳步以及通过在递归中沟通参数来防止复制。

指南针排序

前面使用的点子被号称指南针排序,因为只处理成分的引用而不活动数据小编。在C/C++中,必要明显建议操作的是数据只怕指向数据的指针,在
Java
中,指针的操作是隐式的。除了原有数字类型外,操作的连接数据的引用(指针)而非数据小编。

解答

官方实现见:

在 MergeSortX 类里添加叁个 CUTOFF
字段,排序时倘使数首席执行官度小于它则一贯调用插入排序进行排序。

在调用归并措施前判断第一个有序数组的最后3个要素是或不是超过第二个有序数组的第四个因素,
设若过量的话就不供给调用归并了,直接首尾相接即可。

每趟归并都亟需多个数组,2个用来存放归并结果,这一个数组中的内容是不值1提的;
另2个则保留了归并前的数组,用于实际的集合进程。
归并停止后,前3个数组变成归并后的静止结果(也正是下一次归并时的「归并前数组」),后四个数组中的内容则不再实用。
咱俩能够观望那八个数组的剧中人物在下1次归并时刚好能够沟通。

要注意的是,归并次数延续三个奇数(左边归并+右边归并+总归并),由此在率先次调用
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个便宜是能够不必移动整个因素。对于元素大而键小的数组来说节约是宏伟的,因为相比只需访问成分一小部分,而排序进度超越3/6因素都不会被访问到。对于大约任意大小的要素,引用在形似情况下交流开销和相比费用大致等同(代价是必要万分空间存款和储蓄引用)。

2.2.12

多样排序方法

Java 的 Comparator 接口允许在叁个类中完结四种排序方法。它唯有1个
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)可以先将3个块看作1个成分,将块的首先个因素作为块的主键,用选拔排序将块排序;
(ii)遍历数组,将率先块和第一块归并,完毕后将第一块和第2块归并,等等。

使用比较器达成优先队列
  • 为 MaxPQ 添加一个实例变量 comparator
    以及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(假使输入元素的有所排列的面世几率是均等的)。
提醒:相比次数至少是相比树的表面路径的尺寸(根结点到叶子结点的路径长度之和),当树平衡时该值最小。

找出双重成分

在二个 Comparable
对象的数组中是或不是存在双重成分?有稍许重复成分?哪个值出现最频仍?

通过两两相比较能够在平方级别化解,但经过排序可在线性对数时间内化解。

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

借使对三个数实行排序,那多个数是:3伍,10,17
多少个数排序的决策树如下,结点代表相比较对应地方上的数。
威尼斯人线上娱乐 54
对于 35,十,一柒 来说,路径服从右、左、左,最终获得的结果正是 二 3
壹(十,一7,35)。
我们得以发现决策树上的每一个纸牌节点都意味着一种排列顺序,对于 N
个数,叶子节点就有 N! 个
基于二叉树的习性,中度为 h 的二叉树最多有 二^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 / 2) + k
(加上 k 的原由:左右子树的可观比全部树的可观小
1,因而每条路线的尺寸都必须加 壹,总共多加了 k 次)
因此 H(k) = klogk
现在令 k = n!
H(n威尼斯人线上娱乐,!) = n!log(n!)
出于每一回排序时大家只透过某一条路子(上例中我们只通过了右、左、左那条途径)
同时种种途径的出现可能率相等
从而平均相比较次数应当为 H(n!) / n! = log(n!) = nlog(n)
证实达成

 

排名

逆序对数难点

2.2.14

中位数与各样总结

一个和排序有关但又不须求完全的主要性应用正是找出壹组成分的中位数,有1种非常选取:找到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 个成分,依照等比数列求和公式该和鲜明低于 二N。

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

本篇介绍的算法的全体代码地址:
代码地址

以下是可供参考的博客:
各样排序算法时间复杂度
面试中的排序算法总括
八大排序算法
非得通晓的八大种排序算法【java完毕】
坐在马桶上看算法:飞速排序

题目

归并一如既往的行列。
编辑五个静态方法,将五个静止的行列作为参数,重临八个统壹后的稳步队列。

解答

正如七个静止队列的第二个成分,取较小的三个出队并放入额外建立的行列中。
再也上述手续直到三个连串都为空。

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

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

    return sortedQueue;
}

 

2.2.15

题目

自底向上的雷打不动队列归并排序。
用下边包车型大巴点子编写二个自底向上的联结排序:
给定 N 个元素,成立 N 个连串,每个队列包括当中贰个因素。
成立2个由那 N 个类别组成的队列,然后不断用练习 2.二.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个自底向上的相会排序,当需求将四个子数组排序时能够采纳数组中曾经平稳的局地。
首先找到七个稳步的子数组(移动指针直到当前因素比上1个因素小甘休),
然后再找出另三个并将它们归并。
听别人讲数组大小和数组中递增子数组的最大尺寸分析算法的运营时刻。

解答

自然归并排序的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

题目

链表排序。
落到实处对链表的自然排序
(那是将链表排序的最佳措施,因为它不须求格外的长空且运营时刻是线性对数级其余)。

解答

排序格局和 2.贰.16 拾一分近似,不再赘述,那里介绍一下归并方法。
威尼斯人线上娱乐 57
如 gif
图所示,先把要统一的四个链表拆出来,随后鲜明表头地点,然后实行联合即可。
归并结束后回到 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

题目

打乱链表。
落成一个分治算法,使用线性对数级其他时辰和对数级别的额外空间随意打乱一条链表。

解答

能够在用归并排序的点子做。
将归并时取两边较小的要素改为随机取一侧的值,即可兑现打乱的功效。
算法的解析和平时归并排序壹致,满意标题供给。

代码

分治法打乱链表的落到实处。

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 节)。
本条数据和 Kendall tau 距离有关,请见 二.伍 节。

解答

合法完结:

实际借使在归并排序的时候总计 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

题目

直接排序。
编排1个不更改数组的统1排序,
它回到3个 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

题目

一式三份。
加以多少个列表,每一种列表中含有 N 个名字,
编写三个线性对数级其余算法来判定三分列表中是或不是含有公共的名字,
倘诺有,重回第贰个被找到的那种名字。

解答

对三份列表实行归并排序(O(nlogn)),随后遍历一次个中的1份表,
用二分查找检查在其余五个表中是或不是留存1样的全名(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

题目

3向归并排序。
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

题目

改进。
用试验评估正文中所提到的合并排序的3项更始(请见练习 二.2.11)的效应,
并相比较正文中贯彻的联合排序和演习 2.二.10 所完成的联结排序之间的属性。
基于经验给出应该在哪天为子数组切换来插入排序。

解答

威尼斯人线上娱乐 60
阈值合适时,大约会有1/10的品质进步。
阈值在 10 以下都是比较适合的。

代码
using System;
using Merge;

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

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

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

 

2.2.24

题目

一字不苟的平稳测试。
在实验中用巨型随机数组评估练习 二.贰.八 所做的修改的机能。
依据经验用 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
算法大概能够分为以下多少个步骤
第2将数组划为 k 份,用一个数组 mids 记录那 k 个子数组的细分地点
随之递归的调用 Sort 方法,将那 k 个子数组排序
接着将那 k 个子数组归并,
老是归并时遍历取 k 个子数组中值最小的一个,然后对应子数组的提示器 + 一
地点这一步是 O(k) 的,能够用堆也许败者树优化为对数级别

代码
using System;
using System.Diagnostics;

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

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

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

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

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

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

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

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

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

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

 

2.2.26

题目

创建数组。使用 SortCompare 粗略相比在您的微处理器上在 merge() 卯月在
sort() 中开创 aux[] 的习性差别。

解答

差别仍旧相比明显的,由于 Merge 会调用数次,而用于运营递归的 Sort
方法只会调用1遍。

威尼斯人线上娱乐 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

题目

子数主任度。
用归并将重型随机数组排序,
基于经验用 N
(某次归并时多个子数组的长短之和)的函数揣摸当二个子数组用尽时另一个子数组的平均长度。

解答

大概上会是贰个对数函数,用 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^3、10^陆 和 10^玖,类型为 Long
的任意主键数组,依据经验给出自然的统1排序(请见练习2.二.1陆)所须要的遍数。
提醒:不必要贯彻那几个排序(甚至不供给转变全体完整的 陆十六个人主键)也能成功那道演练。

解答

1齐有序时只要求一遍归并(直接出口),
逆序时索要 n – 一 次归并(退化为插入排序),
平均须要 n/二 次归并。
于是个别必要 500,陆仟00,600000000 次归并。


相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图