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

写在日前

整个项目都托管在了 Github
上:

寻找更为有利于的本子见:https://alg4.ikesnowy.com

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

善用 Ctrl + F 查找问题。

一 初级排序算法

排序算法关怀的要害是重新排列数组成分,在那之中每一个成分都有2个主键。排序算法是将拥有因素主键按某种格局排列(常常是依照轻重缓急或然字母顺序)。排序后索引较大的主键大于等于索引较小的主键。

参考资料

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

 

Q:什么是归并排序?
A:它是起家在集合操作上的一种有效的排序算法;是选拔分治法的贰个格外出色的使用;是一种祥和的

习题&题解

排序算法类的模板

public class Example{
    public static void sort(Comparable a[]){}
    private static boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){
        for(int i = 0;  i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static boolean isSort(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        //从标准输入读入字符串,排序后输出
        Integer[] a = new Integer[]{1,34,55,66,7};
        sort(a);
        assert isSort(a);
        show(a);
    }
}
  • 排序花费模型:商量排序算法时,要求计算正如和置换的次数。对于不交流成分的算法,计算做客数组的次数
  • 额外内部存储器使用:排序算法的附加内部存款和储蓄器费用和周转时刻相同首要。排序算法可分两类:除了函数调用所需的栈和固定数目标实例变量之外无需额外内部存款和储蓄器的原地排序算法,以及必要外加内部存款和储蓄器空间来储存另壹份数组副本的别的排序算法。
  • 数据类型:上述排序算法模板适用于别的达成了Comparable接口的数据类型。例如,Java中封装的Integer和Double,以及String和别的过多高等数据类型(如File和U奇骏L)都达成了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和壹)。1般的话,若
v 和 w 不也许相比较恐怕双方之1是 null,v.compareTo(w) 将会抛出2个非凡。

归并排序的定义

归并排序的落实笔者是那般来叙述的:先对少数多少个要素通过两两统1的方法展开排序,形成二个长短稍大片段的不变系列。然后在此基础上,对七个长度稍大学一年级部分的静止连串再拓展两两联结,形成多个长短越来越大的雷打不动系列,有序系列的的长度不断增高,直到覆盖全部数组的轻重缓急停止,归并排序就做到了。

 

骨干考虑

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

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

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

2.2.1

一.一 选用排序

采用排序:首先找到数组中型小型小的的成分,其次,将它和数组的首先个因素调换地点(假使第一个要素最小就和投机沟通)。再度,在结余成分中找到最小的成分,将它与数组的第3个因素交流地方。如此往复,直到将全方位数组排序。那种艺术叫做慎选排序,因为它在绵绵采纳剩余成分中的最小者

归并排序及其优化,归并排序算法的编码和优化。less()、exch()和isSort()的贯彻见排序算法类的模板

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

分选排序内循环只是在比较当前因素与如今已知最小成分(以及将近日索引加①和检查是或不是代码越界),沟通元素的代码写到了内循环之外,每趟沟通都能排定叁个要素,因而调换总次数是N。所以算法总的时间功能取决于相比较次数。

  • 长度为 N 的数组,采取排序必要差不多 (N^二) / 2 次比较和 N 次交流

0 到 N-壹 的任意 i 都会进展一回交流和 N-一-i 次比较,由此总共有 N
次调换以及(N-一)+(N-2)+…+二+一 = N(N-一) / 贰 ~ N^2 / 2次比较

  • 分选排序有多个显明特点:
  1. 运作时刻和输入非亲非故。为了找出最小元素而扫描3回数组并不能够为下一回扫描提供怎么着信息。那种情状在1些情形下是通病,因为贰个1度稳步的数组或是主键全体等于的数组和一个要素随机排列的数组所用的排序时间壹模一样长,而别的算法更善于利用输入的启幕状态。
  2. 多少移动最少。每一次调换都会改变七个数组成分的值,因而采纳排序用了N次交流——调换次数和数组大小是线性关系,而其他任何算法都不持有那些特点(当先2/4抓好数量级都以线性对数或平方级别)。

归并排序的两种达成情势:递归和巡回

归并排序有两种完结方式:
基于递归的集合排序和基于循环的会见排序
。(也叫自顶向下的联合排序自底向上的合并排序

 

那三种归并算法就算落成格局各异,但依旧有共同之处的:

 

1.
无论是基于递归依旧循环的统1排序,
它们调用的主干措施都是一致的:完毕壹趟合并的算法,即四个已经稳步的数组连串合并成一个越来越大的静止数组连串 
(前提是三个原连串都以不变的!)

2.
从排序轨迹上看,统1类别的长短都以从小(贰个成分)到大(整个数组)增加

 

 

原地归并的肤浅方法

Q:为啥必要原地归并?
A:因为用归并将3个大数组排序时,供给开始展览几度归并,而且每一趟归并会都创建三个新数组来储存排序结果会推动难点。

Q:原地归并落到实处了何等?
A:能够先将前半有的排序,再将后半局地排序,然后数组中移动成分而不须要利用额外的空间(将五个静止的数组归并为二个稳步的数组)

Q:怎么着兑现归并?
A:创制3个适度大小的数组,然后将三个输入数组中的成分四个个多年方法这几个数组中。

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

    /**
     * 将子数组 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^2 / 肆 次交流。最坏景况下供给 ~ N^二 / 二 次相比较和 ~N^2
/ 二 次沟通,最棒状态下必要 N-一 次相比较和 0 次交流。

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

思量一般景色下一部分有序的数组。倒置指的是数组中四个顺序颠倒的成分。比如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。要急剧进步插入排序速度并简单,只需在内循环中校较大要素都向右移而不接二连三交换五个要素(那样访问数组次数就能减半),即上述第3种实现。

单趟归并算法

 

美高梅开户网址 ,自顶向下的晤面排序(化零为整,递归消除)

鉴于上述的原地归并只能将多少个静止的数组归并成一个1如既往的数组,所以得依据原地归并的虚幻去完结1种递归归并。

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

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

解答

美高梅开户网址 1

 

1.三 希尔排序

希尔排序:是1种基于插入排序的排序算法。对于大规模乱序数组插入排序非常的慢,因为它只会换换相邻的因素,若最小成分在数组最后,则对其索要活动N-叁遍。希尔排序立异了插入排序,调换不相邻的成分以对数组的局部进展排序,并最后用插入排序将部分有序的数组排序。

  • h有序数组:数组中任意间隔为 h 的成分都纹丝不动。即三个 h有序数组
    正是 h
    个相互独立的静止数组编织在壹块儿构成的四个数组。若h十分大,则可将元素移到很远位置,为落实更加小的h有序创设有利于。

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

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

算法实例解释可参照:
空话经典算法种类之三希尔排序的兑现
图解排序算法(2)之Hill排序

希尔排序更加高速原因是它衡量了子数组的局面和有序性。排序之初,各样子数组都不够长,排序之后子数组都以有的有序的,那三种景况都符合插入排序。子数组部分有序的水准在于递增连串的选取。

单趟排序的兑现分析

 

上边笔者先介绍三种不相同归并算法调用的共用艺术,
即实现单趟归并的算法。(多个已经稳步的数组系列合并成四个更加大的雷打不动数组连串)

 

在始发排序前创办有3个和原数组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和aux二,大家要做的正是从aux一和aux二的头顶成分起头,相比较双方成分的大小。将较小的因素放入原数组a中(若a[0]已被占则放在a[1]…依次类推),并取得较小成分的下贰个因素,
和另贰个行列中较大的要素相比较
。因为前提是aux1和aux二都以雷打不动的,所以经过那种方法大家能博得更加长的平稳类别

4.  如若aux的两段类别中,个中一段中的全体因素都已”比较”完了,
取得另壹段体系中多余的成分,全部放入原数组a的剩余位置。

 

经过三和肆的兑现格局

  • 安装五个游标 i 和 j
    用于“成分比较”
    (在aux中实行):变量,i 和
    j,分别表示左游标和右游标,起先时分别指向aux[low]和aux[mid]
  • 设置游标k用于明确在a中放置成分的职位(在a中进行),k在开头时候指向a[low]
  • 完整上来说i,
    j, k的趋势都以向右移动的

 

经过3和四的图示演说

 

图A

美高梅开户网址 2

 

 

 

美高梅开户网址 3

组成地点的经过三, 
比较 i 和 j 当前所指的aux中的成分的高低,
取得在那之中比较大的不胜成分(例如上海教室中的i),将其放入数组a中,
此时(在图中假使意况下): i加一,左游标右移。  同时k也加一,
k游标也向右移动

 

图B

美高梅开户网址 4

 

 

美高梅开户网址 5

整合方面包车型大巴经过肆,
在 i 和 j 都向右移动的经过中,
在图中尽管景况下,因为j当前所指的要素(图中地方)大于左半边即a[low…mid]的保有因素,导致
i 不断扩大(右移)且通过了边界(mid),
所以那时候就不须要比较了,只要把j当前所指地点到high的元素都搬到原数组中,填满原数组中剩下的岗位,
单趟归并就完事了, 在那一段进程中 j 延续加壹,右游标一连右移。 
同时k也接2连三加一, k游标也接连右移, 直到 j == high且k == high结束

 

依照上边的公布,
总计出单趟归并算法中最要害的五个规格判断情状:

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

 

 

运营轨道

自顶向下的合并排序运转轨道

2.2.2

1.4 归并排序

归并排序:将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,那有的代码上文未提交

 

代码实现

根据排序算法类的模板完毕选用排序(提示:点蓝字查看详情)

    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循环)进行了6个判断:左半边用尽(取右半边成分)、右半边用尽(取左半边元素)、左半边的此时此刻成分小于右半边的近日因素(取左半边成分)以及右半边的日前元素小于左半边的近期因素(取右半边成分)

单趟排序的经过图解

 

为了更详实的讲述单趟排序的进程,上面在上头的图A和图B的功底上付出每一步的图解:

 

我们要排序的队列是
2 4 五 九 1 三 陆 7, 联合的前提是2 肆 5
玖 和 1 三 陆 七都是上行下效的

 

先比较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

 

【注意】
上边那些事例中的系列只是数组的1有的,
并不一定是全体数组

 

 

本人在上头介绍过,二种分裂归并算法:
基于递归的集合和基于循环的汇合, 
都以以单趟归并的算法为底蕴的。

 

上边先来讲一下依照递归的统一排序(自顶向下的统壹排序)

 

特性分析

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

对于长度为 N 的任意数组,自顶向下的统1排序须求 1/2NlgN – NlgN
次比较

对此长度为 N 的任意数组,自顶向下的联合排序最多须求访问数组 陆NlgN
(2N 次用来复制、2N
次用来将排好序的因素移动回去、此外最多比较 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 的数组,自顶向下的相会排序须要 1/2NlogN 至 NlogN 次相比
  2. 对此长度为 N 的数组,自顶向下的集合排序最多需求拜访数组 陆NlogN 次

归并排序所需时日和 NlogN 成正比,首要症结是扶助数组所使用的额外层空间间和
N 的大小成正比。

传闻递归的合并排序(自顶向下)

 

依照递归的集合排序又称作自顶向下的联合排序

 

自底向上的合并排序(鲁人持竿的化解)

福寿齐天合并的另一种方式:先归并那些微型数组,然后再成对归并获得子数组。首先两两归并,然后四4归并,然后8八归并,一向下去。

2.2.3

归并立异:
  • 对小范围数组使用插入排序。使用插入排序处理小框框的子数组,1般能够将归并排序运营时刻减少百分之十~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

 

 

运作轨迹
题目

用自底向上的统一排序解答演练 2.2.贰

自底向上的会面排序

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

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

自底向上归并排序会频仍遍历整个数组,依照子数组大小进行两两归并,子数组大小sz开始值为1,每回加倍。最后二个子数组大小只有在数组大小是sz的偶好几倍时才约等于sz(不然会比sz小)。

美高梅开户网址 25

自底向上的会面排序的碰面结果

长度为 N 的数组,自底向上的合并排序需 十一分之伍NlogN 至 NlogN
次正如,最多访问数组 陆NlogN 次。

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

用自顶向下或自底向上格局达成别的分治算法都很自然。归并排序表达,当能用一种“化整为零”方法消除时方可试试另一种“循途守辙”的办法。

递归栈深度和调用顺序

 

递归导致的结果是,形成了一名目繁多有层次、有条不紊调用顺序的merge,  如下图左侧的写入编号的merge列表

从上到下,是逐壹merge的程序调用顺序,一开头调用,
15末尾调用

从右到左,
递归栈由深到浅
,例如 1,二,四,5的递归深度是千篇一律的,
而3比它们浅四个层次

美高梅开户网址 26

 

 

美高梅开户网址 27

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

 

对上海体育场所可依照代码来明白

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

 

 

首先,在第3层递归的时候,先进入的是首先行的sort方法里(A处),然后紧接着又进入了第三层递归的第一行sort方法(A处),
如此继续,由(a,
low,mid)的参数列表可见其递归的趋向是平昔向左移动的,直到最终一层递归,所以首先执行merge的对象是a[0]和a[1](上海体育场面编号一),再然后执行的是最终壹层递归的第3行代码(B处),那时候merge的靶子是a[2]和a[3](上海体育场面编号贰)。
再接下来,
重回上一层递归,对已经平稳的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

 

排序算法的复杂度

研讨复杂度的第壹步是赤手空拳2个计算模型。对排序来说,基于相比的算法对数组操作办法是由主键相比决定。

从不任何依照相比的算法能担保使用简单 log(N!) ~ NlogN 次相比较将长度为 N
的数组排序
归并排序是壹种渐进最优的基于相比排序的算法。归并排序在最坏情状下的可比次数和四意基于相比较的排序算法所需的足足比较次数都以
~NogN。

递归归并的轨道图像

 

(下边体现的合并进行了一些优化,对小数组使用插入排序)

美高梅开户网址 29

 

美高梅开户网址 30

 

 

 

基于上文所讲的递归栈和调用顺序,
上边包车型大巴轨迹图像就容易明白了:
从最左边的成分早先联合,而且左边的数组种类在首先轮合并后,相邻左侧的数组按同样的轨道举办统一,
直到统1出和左手相同长度的连串后,才和右侧合并(递归栈回升壹层)

 

 

美高梅开户网址 31

 

美高梅开户网址 32

 

 

品质分析

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

当数主管度为 2
的幂
时,自顶向下和自底向上的汇合排序所用的正如次数数组访问次数赶巧相同,只是顺序分歧。

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

2.2.4

Q&A

  1. 归并排序比Hill排序快吧?
    在骨子里运用中,它们运营时刻距离在常数级别。
  2. 干什么不把数组 aux[] 声明为 merge() 方法的部分变量?
    为防止每一遍归并时,尽管归并非常小的数组都创立三个新数组,不然创制新数组将改成归并排序运维时刻重点部分。越来越好的办法是将
    aux[] 变为 sort() 方法的有的变量,并作为参数字传送给 merge()
    方法。
  3. 当数组中存在重新成分时归并排序品质怎样?
    若有所因素相同,则归并排序运行时刻是线性的。若有八个分歧重复值,运转时刻是线性对数的(和富有因素都不重复满意相同循环条件)。

据说递归归并排序的优化措施

 

总结

平素不别的基于相比较的算法能够保障使用有限 lg(N!) – NlgN 次比较将长度为
N 的数组排序。

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

题目

是不是当且仅当多少个输入的子数组都稳步时原地归并的肤浅方法才能博取正确的结果?
证实您的定论,或许给出三个反例。

一.伍 火速排序

高效排序特点包含原地排序(只需1个十分小的帮忙栈),且将长度为 N
的数组排序所需时间和 NlogN 成正比,内循环比一大半排序算法都要短小。

高效排序:是一种分治排序算法。将1个数组分成多个子数组,将两片段单独地排序。快排和合并排序是补偿的,归并排序将数组分成四个子数组分别排序,并将有序的子数组归并以将整个数组排序;快排的排序格局是当八个子数组都稳步时整个数组也自然有序了。前者的递归调用产生在拍卖任何数组以前;后者递归调用爆发在处理整个数组之后。在归并排序中,二个数组被等分为两半;在快排中,切分地点取决于数组的始末。

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

迅猛排序最多需 N^二 / 三遍比较,但随之打乱数组能预防那种情状。每趟切分后两子数组之一总是空的情事下相比较次数为:N+(N-1)+…+1= N(N+一) / 2,此时岁月是平方级别的,空间是线性的。

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

用差异的方法处理小范围难题能改善超过十一分之5递归算法的性质,因为递归会使小圈圈难题中方法调用太过数次,所以立异对它们的拍卖方法就能革新整个算法。
因为插入排序分外不难
因而一般的话在小数组上比归并排序更加快
那种优化能使归并排序的运维时刻减弱一成到1伍%;

 

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

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

 

 

优化方案

①、一向将扶持数组作为参数字传送入,而不直接使用静态数组。
②、对小规模子数组使用插入排序,一般能够将归并排序的年月减少 一成 ~
15%;
③、判定测试数组是不是曾经平稳,如果 arr[mid] <=
arr[mid+1],大家就认为数组已经是不变的并跳过merge()
方法,能够是随机有序的子数组算法的运作时刻变为线性的。
肆、merge()
方法中不将成分复制到扶助数组,节约数组复制的岁月。调用两种排序方法,一种:将数据从输入数组排序到帮扶数组;另一种:将数据从帮忙数组排序到输入数组。
要害:在种种层次交流输入数组和推来推去数组的剧中人物。

解答

没有错,必须求七个子数组都维持原状时归并才能赢得正确结果。
即便说数组不平稳的话,那么最后只得取得五个数组的鱼目混珠。
联合后的数组中,属于原有数组的要素的相持顺序不会被改成。
比如说子数组 一 叁 一 和 贰 八 5 原地归并。
结果是 一 二 三 壹 八 伍,当中 一 3 一 和 2 八 伍 的相对顺序不变。

 

快排革新

  • 切换成插入排序。对于小数组,快排比插入排序慢;因为递归,快排的sort()方法在小数组中也会调用自个儿。因此在排序小数组时可切换来插入排序——将sort()中的
    if (hi <= lo) return; 改为
    if (hi <= lo + M){Insertion.sort(a, lo, hi); return;},M
    最好值和系统相关,5~15之间常常较好。
  • 3取样切分。使用子数组的一小部分要素的中位数来切分数组,那样切分越来越好,代价是需总括中位数。
  • 熵最优的排序。实际使用平常出现含有多量重复成分的数组,3个要素全体双重的子数组就不需求继续排序了,但前边的算法还会两次三番切分成更加小的数组。不难的消除措施是将数组切分为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向切分快排是线性的。对于自由分布的输入,最优的根据比较的算法平均所需相比次数和叁向切分快排平均所需相比较次数相互处于常数因子范围内。

优化点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]拷贝到辅助数组的相同位置
    }

 

事实上,大家得以因此1种**看起来相比逆天的方法把这么些拷贝进程给去除掉。。。。。**

 

为了实现那或多或少,大家要在递归调用的每个层次交流输入数组和出口数组的剧中人物,从而不断地把输入数组排序到辅助数组,再将数据从支持数组排序到输入数组。

 

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

 

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

 

在此处我们做了三个操作:

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

 

 

小心,
外部的sort方法和内部sort方法接收的a和aux参数刚好是相反的

美高梅开户网址 34

 美高梅开户网址 35

 

这么做的话,
大家就足以去除原数组系列到协助数组的正片了!

 

但是您恐怕会问:
骚年, 大家要排序的而是原数组a啊! 你正是壹相当大心最终浑然排序的是帮忙数组aux而不是原数组a吗?

 

Don’t worry !! 那种意况不会时有产生
看图:

 

美高梅开户网址 36

 美高梅开户网址 37

 

由图示易知,
因为外表sort和merge的参数顺序是均等的, 所以,无论递归进度中扶助数组和原数组的剧中人物怎么替换,对最后2回调用的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
设置虚拟机运营参数

解答

每一趟归并子数组的尺寸和一1如下:

自顶向下

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] 中自由挑选1个要素作为主元。为此,能够将 A[r] 与从
A[p...r] 中随机选出的3个要素调换到担保主元 x = A[r]
是等概率地从子数组的 r-p+二个成分中获取的。因为主元是随机选的,期望在平均情形下对输入数组的划分是相比较平均的。

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),因为对1个轻重为 0
    的数组进行递归调用会直接回到,因而 T(0) =
    O(一),于是算法运维时刻的递归式为:T(n) = T(n-1) + T(0) + O(n) =
    T(n-一)+O(n) = O(n^2)。别的,在输入数组完全有序时,快排时间复杂度仍为
    O(n^二),而插入排序则为 O(n)。

  • 最佳状态:
    partition 获得的八个子难点规模都不高于 n / 二,子难题规模分别为 n / 二和 n / 贰 – 一,此时算法运营时刻递归式为:T(n) = 2T(n / 贰) + O(n) =
    O(nlogn)。

  • 平衡的分开:
    快排平均运转时刻更类似于最棒状态,而非最坏意况。如按 九:1分开,递归树如下:

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

quicksort递归树

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

循环归并的轨迹图像

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

 

美高梅开户网址 41

 

 

美高梅开户网址 42

 美高梅开户网址 43

 美高梅开户网址 44

 

 

题目

编辑贰个主次来总括自顶向下和自底向上的合并排序访问数组的可信次数。
运用那些程序将 N=一 至 51二 的结果绘成曲线图,并将其和上限 陆NlgN 比较。

随机化版本
解答

美高梅开户网址 45

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

一.陆 优先队列

事先队列支持删除最大要素和插入成分。基于二叉堆的事先队列,是用数组保存成分并服从一定标准排序,以实现神速地(对数级别)删除最大要素和插入成分。优先队列实际利用包涵模拟系统、职务调度和数值总计等。

经过插入一列成分然后三个个刨除在那之中的小不点儿成分,就足以用事先队列实现排序算法。堆排序发源于依照堆的预先队列的贯彻。

代码

提交绘图部分的代码:

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

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

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

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

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

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

                dataSize *= 2;
            }

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

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

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

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

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

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

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

            graphics.Dispose();
        }
    }
}

 

API

预先队列是一种抽象数据类型,表示了壹组值和这么些值的操作。优先队列最要紧操作是去除最大要素和插入成分,

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

优先队列的调用示例

3个先期队列的用例

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

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

中低档完成

美高梅开户网址 46

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

解答

依照书本给出的命题 G 和命题 H(粤语版 P173/17陆,英文版 P275/279),
相比次数的下限 C(N) = 5/10 * NlgN
N 和 lgN 都以干瘪递增且超越零的(N>一),由此 C(N) 也是单调递增的

 

堆的概念

在贰叉堆数组中,每一个成分都要确认保障大于等于另七个特定岗位的成分。相应地,这几个地方成分又至少超越等于数组中另四个要素。
堆有序:一棵贰叉树的各样结点都超出等于它的四个子结点,根结点是堆有序的二叉树中的最大结点。

2.2.8

二叉堆表示法

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

二叉堆是1组能用堆有序的完全二叉树排序的因素,并在数组中按层级存款和储蓄(不用数组第二个岗位)

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

美高梅开户网址 47

堆的象征

1棵大小为 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](左半部分的末梢3个因素小于右半部分的率先个要素)
那么大家得以向来统一数组,不供给再做多余的操作

现行反革命的输入是八个1度排序的数组
算法唯一的可比发生在认清 a[mid] < a[mid + 1] 那么些条件时
设若数组有 N 个成分
正如次数满足 T(N) = 二 * T(N / 2) + 1, T(1) = 0
转折为非递归格局即为:T(N) = cN / 二 + N – 壹
个中 c 为专断正整数

 

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

若堆的有事态因某些节点变得比它的父节点越来越大而被打破,则需经过置换它和它的父节点来修复堆。调换后,该节点比它的两个子节点都大。重复该进程,直到遇见更加大的父节点。

美高梅开户网址 48

上浮

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

2.2.9

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

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

美高梅开户网址 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();
    }
}

命题:对于3个涵盖 N
个因素的遵照堆的先行队列,插入成分操作只需不抢先 lgN+1次相比较,剔除最大因素操作内需不超越 二lgN 次相比较。

表达:二种操作都亟待在根节点和堆底之间活动成分,而路径长度不超越lgN。对于路径上的各样节点,剔除最大要素内需一遍比较(除了堆底成分),1回用来找出较大的子节点,一回用来规定该子节点是或不是须要上浮。

题目

在库函数中应用 aux[] 那样的静态数组时不服帖的,
因为恐怕会有三个程序同时选用这一个类。
兑现一个并非静态数组的 Merge 类,
但也绝不将 aux[] 变为 merge() 的壹部分变量(请见本书的对答部分)。
唤醒:能够将援助数组作为参数字传送递给递归的 sort() 方法。

多叉堆

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

解答

官方给出的集合排序达成中在 Sort 方法里初叶化了 aux 数组。
源码见:

C#达成和官方的兑现丰硕周围,

先是定义只接受2个参数的公开 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.10

堆的构造

总是向优先队列插入成分可行,但更急迅的秘籍是从右到左用 sink()
函数构造子堆。数组各样岗位都已经是三个子堆的根节点了,sink()
对于那么些子堆也适用。若二个节点的八个子节点都已经是堆了,则在该节点上调用
sink()
可将它们成为1个堆。起首时只需扫描数组中2/④要素,因为能够跳过大小为一的子堆。最后在岗位壹上调用
sink()
方法,扫描甘休。在排序第三品级,堆的构造方法和大家不知不觉想象的不等,因为大家目标是构造二个堆有序的数组并使最大因素位于数组的起始(次大的要素在周围)而非构造函数停止的末段。

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

题目

登时归并。
福寿年高三个 merge() 方法,按降序将 a[] 的后半有的复制到 aux[],
然后将其归并回 a[]
中。那样就能够去掉内循环中检查评定某半边是还是不是用尽的代码。
留意:那样的排序发生的结果是不安定的(请见 2.五.1.8 节)。

下沉排序

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

美高梅开户网址 52

堆的构造和下沉排序

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

将N个因素排序,堆排序只需少于 贰NlgN+贰N
次相比(以及十分之五次数的交流),二N 项来自于堆的协会,2NlgN
来源于于每便下沉操作最大恐怕须求 二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 1962年发现可以因此免去反省成分是还是不是到达正确地点来节省时间。在下沉中总是直接晋级较大的子节点直至到达堆底,然后再使成分上浮到正确地方,那样能够将相比较次数减弱5/10——接近了归并排序所需相比次数(随机数组)。该方法需额外层空间间,由此实际应用中只有当比较操作代价相比高时才用(例如:将字符串或其余键值较长类型的因素排序时)。

堆排序在排序复杂性研商中有根本地位,因为它是绝无仅有能同时最优地利用空间和岁月的办法——最坏情状下能保险使用
~2NlgN
次比较和固化的附加空间。当空间非常浮动时(如嵌入式系统或低本钱移动装备)很盛行,因为它只用几行就能完毕较好的本性(甚至机器码也是)。但现代种类很少用,因为它不知所可选择缓存。数组成分很少和隔壁的别样成分比较,由此缓存未命中的次数要远超过超过2伍%相比都在相近元素间展开的算法,如快排、归并排序、甚至是Hill排序。

在大数据量下,要拍卖 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接口只需定义1个compareTo()函数并在当中定义该数据类型的轻重关系。Java
中的 String、Integer、Double、File 和 URL都落到实处了Comparable接口。

题目

改进。
兑现 2.贰.2 节所述的对归并排序的三项改进:
加紧小数组的排序速度,
检查测试数组是还是不是业已稳步以及通过在递归中调换参数来防止复制。

指南针排序

日前使用的章程被称呼指南针排序,因为只处理成分的引用而不移步数据笔者。在C/C++中,须要鲜明提出操作的是数量也许指向数据的指针,在
Java
中,指针的操作是隐式的。除了原有数字类型外,操作的连年数据的引用(指针)而非数据本人。

解答

法定完结见:

在 MergeSortX 类里添加一个 CUTOFF
字段,排序时若是数主任度小于它则向来调用插入排序举办排序。

在调用归并措施前判断第一个有序数组的末梢3个因素是不是超越首个有序数组的率先个要素,
一旦超出的话就不要求调用归并了,直接首尾相接即可。

老是归并都急需七个数组,一个用来存放归并结果,这么些数组中的内容是可有可无的;
另贰个则保留了归并前的数组,用于实际的集合进度。
归并甘休后,前3个数组变成归并后的有序结果(也正是下3遍归并时的「归并前数组」),后八个数组中的内容则不再实用。
咱俩能够见见那四个数组的剧中人物在下一次归并时刚刚能够调换。

要留意的是,归并次数三番五次贰个奇数(右侧归并+左边归并+总归并),由此在第2遍调用
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个功利是足以无需移动整个因素。对于成分大而键小的数组来说节约是高大的,因为正如只需访问成分一小部分,而排序进程当先二分之壹因素都不会被访问到。对于大致任意大小的要素,引用在壹般景色下调换开支和比较开销大约1模1样(代价是须求非凡层空间间存款和储蓄引用)。

2.2.12

各类排序方法

Java 的 Comparator 接口允许在2个类中贯彻五种排序方法。它唯有3个
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)能够先将三个块看作二个因素,将块的率先个要素作为块的主键,用选择排序将块排序;
(ii)遍历数组,将第贰块和第一块归并,完毕后将第一块和第一块归并,等等。

行使比较器实现优先队列
  • 为 马克斯PQ 添加一个实例变量 comparator
    以及3个构造函数,该构造函数接受三个比较器作为参数并用它将
    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,1七
多个数排序的决策树如下,结点代表相比对应地方上的数。
美高梅开户网址 54
对于 35,10,17 来说,路径坚守右、左、左,最后取得的结果正是 二 3
一(十,一七,35)。
我们能够发现决策树上的每1个叶子节点都表示一种排列顺序,对于 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 / 二) + 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。

平均来说,基于切分的挑3拣4算法运营时刻是线性级别的。

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

以下是可供参考的博客:
各个排序算法时间复杂度
面试中的排序算法总括
⑧大排序算法
必须知道的八大种排序算法【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个成分。
创办3个由这 N 个类别组成的行列,然后不断用练习 二.二.第11四中学的方法将队列的头多少个要素归并,
并将结果重新加入到行列结尾,直到队列的队列只剩余一个成分截止。

解答

程序思路标题已经交给,根据题意完成即可。
Merge 方法能够直接行使前一题的兑现。

代码
using System;

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

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

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

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

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

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

            return sortedQueue;
        }
    }
}

 

2.2.16

题目

理所当然的统一排序。
编排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

题目

链表排序。
福寿双全对链表的当然排序
(那是将链表排序的最棒方法,因为它不需求非凡的长空且运营时刻是线性对数级别的)。

解答

排序情势和 贰.二.16 拾壹分近乎,不再赘述,那里介绍一下归并方法。
美高梅开户网址 57
如 gif
图所示,先把要合并的四个链表拆出来,随后明显表头地点,然后举办统1即可。
归并终止后归来 first。

结果分析如下图所示:
美高梅开户网址 58
随着有序部分的增多,对于同样大小的数组自然归并排序的耗费时间会浓缩。
对此有序部分雷同的事态,随着数组大小的倍增,耗费时间呈现了O(nlogn)的势头。

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

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

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

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

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

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

                if (mid.next == null)
                    break;

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

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

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

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

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

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

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

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

            first = current;

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

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

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

            return first;
        }

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

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

 

2.2.18

题目

打乱链表。
福寿无疆贰个分治算法,使用线性对数级其余年华和对数级别的附加空间随意打乱一条链表。

解答

能够在用归并排序的格局做。
将归并时取两边较小的成分改为随机取1侧的值,即可完成打乱的成效。
算法的辨析和平凡归并排序1致,知足标题供给。

代码

分治法打乱链表的完毕。

using System;

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

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

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

                if (mid.next == null)
                    break;

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


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

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

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

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

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

            first = current;

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

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

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

            return result;
        }

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

            return hi;
        }
    }
}

 

2.2.19

题目

倒置。
编纂3个线性对数级其他算法总计给定数组中“倒置”数量
(即插入排序所需的置换次数,请见 2.一 节)。
这些数量和 Kendall tau 距离有关,请见 二.5 节。

解答

官方实现:

实际上借使在归并排序的时候总括 Less(aux[j], aux[i])
满足的次数即可,这一个次数正是大家要的值。

代码
using System;
using Merge;

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

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

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

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

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

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

 

2.2.20

题目

直接排序。
编写制定3个不改变数组的集合排序,
它回到2个 int[] 数组 perm,其中 perm[i] 的值是原数组中第 i
小的要素的地方。

解答

官方达成:

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

代码
using System;
using Merge;

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

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

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

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

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

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

 

2.2.21

题目

一式3份。
加以八个列表,每一个列表中蕴藏 N 个名字,
编纂二个线性对数级其他算法来判断三分列表中是或不是包括公共的名字,
假定有,重临第一个被找到的那种名字。

解答

对3份列表进行归并排序(O(nlogn)),随后遍历2次在那之中的一份表,
用二分查找检查在其余多个表中是或不是留存壹样的真名(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向归并排序。
设若每一次大家是把数组分成八个部分而不是几个部分并将它们分别排序。
接下来进行叁向归并。
那种算法的运维时刻的加强数据级是稍稍。

解答

美高梅开户网址 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

题目

改进。
用试验评估正文中所提到的合并排序的三项革新(请见练习 2.二.1壹)的作用,
并比较正文中贯彻的联合排序和演习 2.二.10 所达成的联结排序之间的习性。
基于经验给出应该在几时为子数组切换来插入排序。

解答

美高梅开户网址 60
阈值合适时,差不多会有百分之10的特性升高。
阈值在 10 以下都是比较适合的。

代码
using System;
using Merge;

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

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

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

 

2.2.24

题目

改正的稳步测试。
在实验中用巨型随机数组评估演练 二.2.八 所做的修改的效用。
依照经验用 N(被排序的原始数组的尺寸)的函数描述条件语句(a[mid] <=
a[mid + 1])创立(无论数组是不是有序)的次数。

解答

美高梅开户网址 61
约为 lgN 次

代码
using System;
using Merge;

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

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

 

2.2.25

题目

多向归并排序。
完结一个 k 向(相对双向而言)归并排序程序。
解析你的算法,揣摸最好的 k 值并通过试验注脚猜度。

解答

事实上 k 的取值非亲非故首要,实验也证实了这一点。
美高梅开户网址 62
算法差不多能够分成以下多少个步骤
率先将数组划为 k 份,用贰个数组 mids 记录那 k 个子数组的分割地方
紧接着递归的调用 Sort 方法,将这 k 个子数组排序
随之将那 k 个子数组归并,
每一回归并时遍历取 k 个子数组中值最小的二个,然后对应子数组的提醒器 + 1
地方这一步是 O(k) 的,能够用堆或许败者树优化为对数级别

代码
using System;
using System.Diagnostics;

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

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

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

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

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

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

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

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

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

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

 

2.2.26

题目

创立数组。使用 SortCompare 粗略比较在你的总计机上在 merge() 杏月在
sort() 中创建 aux[] 的属性差距。

解答

不一致依然比较明显的,由于 Merge 会调用数次,而用于运转递归的 Sort
方法只会调用壹遍。

美高梅开户网址 63

代码
using System;
using Merge;

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

        }
    }
}

 

2.2.27

题目

子数经理度。
用归并将大型随机数组排序,
依据经验用 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^叁、10^六 和 10^9,类型为 Long
的自由主键数组,根据经验给出自然的联结排序(请见练习二.二.1陆)所需求的遍数。
晋升:不需求达成那个排序(甚至不需求转移全部完整的 6叁人主键)也能达成那道练习。

解答

统统有序时只供给一次归并(直接出口),
逆序时要求 n – 一 次归并(退化为插入排序),
平均必要 n/二 次归并。
因此个别需求 500,四千00,伍仟00000 次归并。

发表评论

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

网站地图xml地图