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

作者:www.7727.com

写在头里

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

追寻更为便利的本子见:https://alg4.ikesnowy.com

这生机勃勃节内容大概会用到的库文件有 Merge,同样在 Github 上得以找到。

善用 Ctrl + F 查找难题。

参照他事他说加以考察资料

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

 

1 低端排序算法

排序算法关切的首假设重新排列数组成分,个中各种成分皆有八个主键。排序算法是将享有因素主键按某种方式排列(常常是比照大小大概字母逐豆蔻梢头)。排序后索引十分的大的主键大于等于索引异常的小的主键。

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和UPRADOL)都达成了Comparable接口,由此得以一贯调用这么些项目标数组作为参数调用大家和好完成的排序方法。

举例——用快排对N个随机的Double数据开展排序:

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

在开创和煦的数据类型时,只要完毕Comparable接口并得以完结该接口中的compareTo(卡塔尔(英语:State of Qatar)方法,来定义指标项目对象的当然次序,如:

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

对于 v < w、v = w 和 v > w 二种情况,Java习于旧贯是在v.compareTo(w卡塔尔(قطر‎被调用时分别再次来到五个负整数、零和三个正整数(-1、0和1)。平常的话,若 v 和 w 无法相比只怕两者之一是 null,v.compareTo(w卡塔尔国 将会抛出多少个非常。

着力思维

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

优点?它能确认保障将轻巧长度为 N 的数组排序所需时日和 NlogN 成正比;

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

2.2.1

合併排序的三种达成情势:递归和巡回

归总列排在一条线序有二种完结格局: 基于递归的相会排序和根据循环的会面排序。(也叫自顶向下的合併排序自底向上的集结排序

 

这三种合併算法即便落成情势各异,但要么有同盟之处的:

 

1. 无论是基于递归依然循环的探问排序, 它们调用的骨干措施都以一模二样的:完结风流浪漫趟归并的算法,即四个曾经平稳的数组系列归并成二个更加大的稳步数组连串  (前提是七个原系列都是板上钉钉的!)

2. 从排序轨迹上看,统大器晚成体系的长短都是从小(一个因素)到大(整个数组)增加

 

 

1.1 选拔排序

选择排序:首先找到数组中小小的的成分,其次,将它和数组的首先个因素调交换一下地方置(假若第二个要素最小就和投机调换)。再度,在结余成分中找到最小的元素,将它与数组的第一个因素调换个地方置。如此往复,直到将全体数组排序。这种办法叫做选料排序,因为它在接踵而至 蜂拥而至采纳剩余成分中的最小者

less(卡塔尔(قطر‎、exch(卡塔尔(英语:State of Qatar)和isSort(卡塔尔的兑现见排序算法类的沙盘模拟经营

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

选料排序内循环只是在比较当前因素与近来已知最小成分(以致将日前索引加1和检查是或不是代码越界),交流成分的代码写到了内循环之外,每趟沟通都能排定一个因素,因而交流总次数是N。所以算法总的时间成效决议于相比较次数。

  • 长度为 N 的数组,接收排序供给大概 (N^2卡塔尔国 / 2 次比较和 N 次交流

0 到 N-1 的恣意 i 都会开展一遍调换和 N-1-i 次比较,因而总共有 N 次调换甚至(N-1卡塔尔(قطر‎+(N-2卡塔尔(英语:State of Qatar)+...+2+1 = N(N-1卡塔尔(قطر‎ / 2 ~ N^2 / 2次比较

  • 筛选排序有多少个鲜明特点:
  1. 运作时刻和输入非亲非故。为了找寻最小成分而扫描三回数组并无法为下一回扫描提供什么信息。这种情状在好几情状下是老毛病,因为一个早就平稳的数组或是主键全体极其的数组和三个要素随机排列的数组所用的排序时间同一长,而其他算法更加长于利用输入的最初状态。
  2. 数量移动起码。每一遍交流都会变动多个数组成分的值,由此接收排序用了N次交流——调换次数和数组大小是线性关系,而任何任何算法都不抱有那么些特点(超越四分之二增高数量级都以线性对数或平方等级)。

原地合併的画饼充饥方法

Q:为啥须求原地归总?
A:因为用归总将二个大数组排序时,要求张开频仍归总,并且每便合併会都创立二个新数组来存款和储蓄排序结果会带给难题。

Q:原地归总促成了怎样?
A:能够先将前半部分排序,再将后半有些排序,然后数组中活动成分而无需使用额外的半空中(将八个静止的数组归拢为叁个长久以来的数组)

Q:怎么着达成归拢?
A:创制多个切合大小的数组,然后将四个输入数组中的成分贰个个多年方法那几个数组中。

代码达成
根据排序算法类的模板兑现归总列排在一条线序(提示:点蓝字查看详细的情况)

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

安分守纪本书初阶所示轨迹的格式给出原地归总排序的悬空 merge()方法是哪些将数组 A E Q S U Y E I N O S T 排序的。

单趟合并算法

 

1.2 插入排序

插入排序:收拾扑克时平日都是一陈威张来,将每张牌插入到此外已经稳步的牌中的适当地方。在微电脑完结中,为了要给插入成分腾出空间,供给将别的具有因素在插入在此以前都向右移动壹位。这种算法叫做插入排序

  • 与选取排序肖似,当前目录侧面全部因素都以稳步的,但它们最终地方还不明显,为了给越来越小成分腾出空间,它们或者会被移位,但当索引达到数组右端时,数组排序就完毕了。
  • 与选拔排序分歧的是,插入排序所需时日决计于输入二月素的上马顺序。如对相同平稳的数组排序要比自由数组快超多。

对于随便排列的长度为N且主键不另行的数组,平均情状下插入排序须求 ~ N^2 / 4$ 次相比以致~N^2 / 4 次调换。最坏情形下要求 ~ N^2 / 2 次相比和 ~N^2 / 2 次交流,最佳状态下需求 N-1 次比较和 0 次调换。

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

酌量平日情形下局地有序的数组。倒置指的是数组中八个顺序颠倒的因素。比方EXAMPLE中有11对倒置:E-A,X-A,X-M,X-P,X-L,X-E,M-L,M-E,P-L,P-E和L-E。若数组中倒置的数额低于数组大小的某部倍数,则这几个数组是一些有序。插入排序对如此的数组很得力,事实上,当倒置数量很时辰,插入排序可能比其他任何算法都快。

插入排序的沟通操作和数组中倒置数量相近,要求相比的次数超过等于倒置的数额,小于等于倒置的数额增加数组的尺寸再减意气风发。要小幅提升插入排序速度并简单,只需在内循环少校异常的大因素都向右移而不接二连三调换三个要素(那样访谈数组次数就会减半),即上述第2种完结。

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

是因为上述的原地归拢只能将三个静止的数组归总成三个不改变的数组,所以得依照原地归拢的抽象去完成生龙活虎种递归合併。

要对子数组 arr[lo...hi] 举行排序,先将它分成 arr[lo...mid] 和 arr[mid+1...hi] 两局地,分别通过递归调用将它们单独排序,最终将不改变的子数组归拢为最终的排序结果。

Q:为啥它能将科学的排序?
A:假诺它能将五个子数组排序,那么它就足以因而合併八个子数组来将全部数组排序。

解答

图片 1

 

单趟排序的落到实处深入分析

 

上面笔者先介绍三种不一致合并算法调用的公家艺术, 即完结单趟合併的算法。(七个曾经逐步的数组系列合併成一个更加大的平稳数组连串)

 

在上马排序前创办有三个和原数组a长度相符的空的扶持数组aux

 

单趟归拢的历程如下:

 

1.  第后生可畏将原数组中的待排序种类拷贝进帮助数组的相近地点中,将要a[low...high]拷贝进aux[low...high]中

2.  支持数组aux的天职有两项:相比成分大小, 并在aux中每一种拿到有序的成分归入原数组a中 (通过1使aux和a在low-high的职位是完全相符的!那是得以达成的底子)

3.  因为aux[low...high]由两段有序的队列:aux[low...mid]和aux[mid...high]结合, 这里称之为aux1和aux2,大家要做的正是从aux1和aux2的头顶成分开始,对比双方成分的高低。将异常的小的成分归入原数组a中(若a[0]已被占则放在a[1]...依次类推),并获取非常的小元素的下三个因素, 和另二个队列中非常大的要素相比较。因为前提是aux1和aux2都以铁板钉钉的,所以经过这种格局我们能赢得更加长的不改变体系

4.  只要aux的两段体系中,此中风流倜傥段中的全部因素都已经"比较"完了, 获得另一段类别中剩下的因素,全体放入原数组a的剩下地方。

 

进程3和4的得以完毕形式

  • 安装多少个游标 i 和 j 用于“成分相比” (在aux中张开):变量,i 和 j,分别表示左游标和右游标,最先时分别指向aux[low]和aux[mid]
  • 设置游标k用于分明在a中放置元素的任务(在a中进行),k在伊始时候指向a[low]
  • 全部上来讲i, j, k的取向都是向右移动的

 

进度3和4的图示解说

 

图A

图片 2

 

 

 

图片 3

结缘地点的进程3,  相比较 i 和 j 当前所指的aux中的成分的尺寸, 获得个中十分大的不得了成分(比如上航海用体育场地中的i),将其放入数组a中, 那时(在图中借使情形下): i加1,左游标右移。  同时k也加1, k游标也向右移动

 

图B

图片 4

 

 

图片 5

结合位置的进度4, 在 i 和 j 都向右移动的进度中, 在图中借使景况下,因为j当前所指的因素(图中地方)大于左半边即a[low...mid]的拥有因素,引致i 不断增加(右移)且通过了边界(mid), 所以当时就无需相比了,只要把j当前所指地方到high的因素都搬到原数组中,填满原数组中剩下的岗位, 单趟归总就做到了, 在这里大器晚成段进度中 j 一而再加1,右游标一而再右移。  同期k也接连加1, k游标也接连右移, 直到 j == high且k == high停止

 

基于上面包车型地铁抒发, 总括出单趟归总算法中最注重的4个标准推断景况:

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

 

 

1.3 Hill排序

Hill排序:是意气风发种基于插入排序的排序算法。对于相近乱序数组插入排序一点也不快,因为它只会换换相邻的要素,若最小成分在数组最后,则对其急需活动N-1次。Hill排序改善了插入排序,交流不相邻的要素以对数组的一些进展排序,并最终用插入排序将部分有序的数组排序。

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

算法实例解释可参看:
空话优越算法连串之三 Hill排序的落实
图解排序算法(二卡塔尔(قطر‎之Hill排序

Hill排序更飞速原因是它衡量了子数组的局面和有序性。排序之初,各类子数组都超短,排序之后子数组都以局地有序的,那二种状态都合乎插入排序。子数组部分有序的品位在于依次增加类别的选料。

运行轨迹

自顶向下的相会排序运转轨迹

2.2.2

单趟排序算法的代码

 

有了地方的讲解,写那么些算法就简单了吧

 

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

 

【注意】在排序之初制造了二个长度和原数组a相近的增加帮衬数组aux,那黄金时代部分代码上文未提交

 

1.4 合併排序

合并列排在一条线序:将二个数组排序,能够先(递归地)将它分成两半各自动排档序,然后将结果合併起来。合併列排在一条线序将长度为N的数组排序所需时间和 NlogN 成正比;所需额外层空间间和 N 成正比。

代码落成

根据排序算法类的沙盘模拟经营兑现选用排序(提示:点蓝字查看详细情况)

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

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

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

遵纪守法算法 2.4 所示轨迹的格式给来自顶向下的联合排序是什么样将数组 E A S Y Q U E S T I O N 排序的。

单趟排序的长河图解

 

为了更详实的描述单趟排序的经过,下边在地点的图A和图B的底工上提交每一步的图解:

 

咱俩要排序的队列是 2 4 5 9 1 3 6 7, 联合的前提是2 4 5 9 和 1 3 6 7都以有序的

 

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

图片 6

 图片 7

 

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

图片 8

 图片 9

 

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

图片 10

 图片 11

 

恍如上述, 不表明

图片 12

图片 13

 

 

周边上述, 不表明

图片 14

 图片 15

 

好像上述, 不说明

图片 16

 图片 17

 

看似上述, 不解释

图片 18

 

图片 19

 

在乎, 这这里 j 扩张导致 j> high,  以往的景色是“右半边用尽”, 所以将aux左半边剩余的成分9归入a剩下的片段a[7]中, 单趟排序实现

图片 20

 

图片 21

 

【注意】 上边这么些事例中的系列只是数组的风流浪漫局地, 并不一定是整套数组

 

 

本人在上头介绍过,三种不相同合併算法: 基于递归的归并和依照循环的归并,  都以以单趟合并的算法为根底的。

 

下边先来说一下依照递归的联结排序(自顶向下的联结排序)

 

原地归总的指雁为羹方法——merge(卡塔尔(英语:State of Qatar)

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

上述措施将装有因素复制到一个帮衬数组aux[]中,再把合併结果放回原数组a[]中。方法在归总时(第一个for循环)实行了4个判定:左半边用尽(取右半边成分)、右半边用尽(取左半边成分)、左半边的当下因素小于右半边的脚下因素(取左半边成分)乃至右半边的一时一刻成分小于左半边的最近因素(取右半边成分)

特性深入分析

至上状态:T(n卡塔尔(英语:State of Qatar) = O(n卡塔尔
最差情状:T(n卡塔尔(英语:State of Qatar) = O(nlogn卡塔尔(قطر‎
平均情形:T(n卡塔尔(英语:State of Qatar) = O(nlogn卡塔尔(قطر‎

对此长度为 N 的大肆数组,自顶向下的集结排序须要 1/2NlgN - NlgN 次比较

对此长度为 N 的任意数组,自顶向下的合併列排在一条线序最多须求做客数组 6NlgN 次(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 的数组,自顶向下的合併列排在一条线序须要 百分之五十NlogN 至 NlogN 次正如
  2. 对此长度为 N 的数组,自顶向下的联合排序最多须要拜望数组 6NlogN 次

归拢列排在一条线序所需时间和 NlogN 成正比,首要弱点是协助数组所使用的额外层空间间和 N 的高低成正比。

自底向上的统一排序(循途守辙的缓和)

得以落成统意气风发的另后生可畏种方法:先归拢那叁个微型数组,然后再成对归拢拿走子数组。首先两两归总,然后四四归拢,然后八八合併,平素下去。

2.2.3

递归归拢的思辨

图片 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

 

 

合併修正:
  • 对小框框数组使用插入排序。使用插入排序管理小圈圈的子数组,通常能够将归拢列排在一条线序运维时刻裁减十分一~15%。
  • 测验数组是还是不是业已稳步。加多八个论断规范,若 a[mid] <= a[mid + 1] 则以为数组已经稳步并跳过 merge(卡塔尔(英语:State of Qatar)方法。那一个改造不影响排序的递归调用,但随意有序的子数组算法的运营时刻就变为线性了。
  • 不将成分复制到扶持数组。能够节省成分复制到帮忙数组所用时间(但空间十三分),这时需调用三种排序方法,风流倜傥种从输入数组排序到扶植数组,后生可畏种从援救数组排序到输入数组,本事是在递归调用的各类等级次序交换输入数组和救助数组的剧中人物。
运作轨道
题目

用自底向上的联合排序解答练习 2.2.2

递归栈深度和调用顺序

 

递归诱致的结果是,形成了生龙活虎多级有档期的顺序、有程序调用顺序的merge,  如下图左侧的写入编号的merge列表

从上到下,是逐意气风发merge的前后相继调用顺序,1最初调用, 15末段调用

从右到左, 递归栈由深到浅,比方 1,2,4,5的递归深度是相近的, 而3比它们浅叁个档期的顺序

图片 25

 

 

图片 26

(这里是根据字母排序, A最小, Z最大)

 

对上海教室可依据代码来驾驭

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

 

 

先是,在首先层递归的时候,先走入的是首先行的sort方法里(A处),然后跟着又进来了第二层递归的第风流倜傥行sort方法(A处), 如此继续,由(a, low,mid卡塔尔国的参数列表可以预知其递归的倾向是直接向左移动的,直到最后黄金时代层递归,所以最先执行merge的对象是a[0]和a[1](上航海用教室编号1),再然后施行的是终极黄金年代层递归的第二行代码(B处),当时merge的对象是a[2]和a[3](上海体育场面编号2)。 再然后, 重回上风华正茂层递归,对已经稳步的a[0]、a[1]和a[2]、a[3]开展merge。(上图编号3)如此继续,递归的吃水不断变浅, 直到对总体数组的左右两半扩充merge。 (上海教室编号3)

 

 

自底向上的统一排序

先合併微型数组,然后再成对归总获得的子数组,直到将全部数组归总到一同,那比正规递归方法所需代码量少。首先是两两归拢(各个成分是高低为1的数组),然后四四合併(将四个轻重缓急为2的数组合併成二个有4个成分的数组),然后是八八归总...

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

自底向上归总列排在一条线序会再三遍历整个数组,依据子数组大小进行两两合并,子数组大小sz初始值为1,每一次加倍。最后二个子数组大小只有在数组大小是sz的偶好多倍时才也就是sz(不然会比sz小)。

图片 27

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

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

  • 当数董事长度为2的幂时,自顶向下和自底向上归总排序所用相比较和做客次数相符,只是顺序分歧。
  • 自底向上合併列排在一条线序相符用链表团组织数据。此办法只需另行组织链表连接就会将链表原地排序(不需成立任何新的链表节点)。

用自顶向下或自底向上情势落实任何分治算法都很当然。合併排序表明,当能用风姿浪漫种“合两为一”方法搞准时得以施行另后生可畏种“遵纪守法”的形式。

代码完结

根据排序算法类的模板得以完成选取排序(提醒:点蓝字查看详细情况)

    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

 

递归归拢的轨迹图像

 

(下面显示的群集进行了豆蔻年华部分优化,对小数组使用插入排序)

图片 29

 

图片 30

 

 

 

传闻上文所讲的递归栈和调用顺序, 上边包车型地铁轨道图像就简单精通了: 从最侧面的因素先导统后生可畏,何况侧面的数组系列在率先轮归总后,相邻侧面的数组按相符的轨迹举办联合, 直到联合出和左边手相似长度的行列后,才和左边手合併(递归栈上升朝气蓬勃层)

 

 

图片 31

 

图片 32

 

 

排序算法的复杂度

讨论复杂度的率先步是树立一个思谋模型。对排序来讲,基于相比的算法对数组操作方法是由主键比较决定。

未有其他依靠比较的算法能确认保证使用简单 log(N!) ~ NlogN 次比较将长度为 N 的数组排序
归总列排在一条线序是豆蔻梢头种渐进最优的基于相比排序的算法。归总排序在最坏意况下的可比次数和任性基于相比的排序算法所需的最少相比次数都以 ~NogN。

属性深入分析

对此长度为 N 的任性数组,自底向上的联合排序必要 1/2NlgN - NlgN 次比较,最多采访数组 6NlgN 次。(每风姿浪漫边拜会数组 6N 次,比较次数 N/2 - N)

当数主管度为 2 的幂时,自顶向下和自底向上的会集排序所用的相比次数数组访问次数偏巧相近,只是顺序不一样。

自底向上的联合比较符合用链表协会的数据。

2.2.4

依附递归归拢列排在一条线序的优化措施

 

Q&A

  1. 归总排序比Hill排序快吗?
    在其实使用中,它们运营时刻间隔在常数等第。
  2. 何以不把数组 aux[] 声明为 merge() 方法的局地变量?
    为避免每便合併时,就算归并相当的小的数组都创立三个新数组,不然创制新数组将改成合并列排在一条线序运营时刻首要部分。更加好的情势是将 aux[] 变为 sort() 方法的生龙活虎部分变量,并视作参数字传送给 merge() 方法。
  3. 当数组中存在重新成分时合併列排在一条线序质量怎样?
    若持有因素形似,则合并列排在一条线序运维时刻是线性的。若有四个分裂重复值,运转时刻是线性对数的(和全体因素都不另行满意相符循环条件)。

总结

从未别的依据相比较的算法能够保险使用有限 lg(N!卡塔尔 - NlgN 次比较将长度为 N 的数组排序。

归总列排在一条线序是意气风发种渐进最优的基于相比排序的算法。

题目

是还是不是当且仅当三个输入的子数组都闻风不动时原地归拢的悬空方法技巧获得不错的结果?
证实你的定论,可能给出一个反例。

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

用分化的章程管理小框框难点能改革大许多递归算法的性质,因为递归会使小范围难点中方法调用太过多次,所以改良对它们的拍卖方法就能够改善整个算法。 因为插入排序特别轻便, 由此经常的话在小数组上比合并列排在一条线序更加快。 这种优化能使合併列排在一条线序的运作时刻收缩百分之十到15%;

 

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

  if(low>=high) { return; }

 

改成

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

 

就足以了,那样的话,那条语句就具备了四个效果与利益:

 

1. 在适那时候候截止递归

2. 当数COO度小于M的时候(high-low <= M), 不开展归总排序,而进展插排

 

切实代码:

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

 

 

1.5 急迅排序

神速排序特点包涵原地排序(只需一个非常的小的扶持栈),且将长度为 N 的数组排序所需时间和 NlogN 成正比,内循同比大繁多排序算法都要短小。

快捷排序:是风姿罗曼蒂克种分治排序算法。将四个数组分成多少个子数组,将两局地单独地排序。快排和联合排序是抵补的,归拢列排在一条线序将数组分成四个子数组分别排序,并将不改变的子数组归总以将全体数组排序;快排的排序方式是当五个子数组都稳步时整个数组也当然有序了。前边一个的递归调用发生在拍卖整个数组早前;前者递归调用产生在处理任何数组之后。在合併列排在一条线序中,一个数组被等分为两半;在快排中,切分地点决定于数组的原委。

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

火速排序最多需 N^2 / 2 次相比,但任何时候打乱数组能防守这种情景。每一次切分后两子数组之意气风发总是空的情状下相比次数为:N+(N-1卡塔尔(قطر‎+...+1 = N(N+1卡塔尔(قطر‎ / 2,此时时刻是平方品级的,空间是线性的。

优化方案

①、直接将帮助数组作为参数字传送入,而不直接运用静态数组。
②、对小规模子数组使用插入排序,常常可以将合併列排在一条线序的时间缩小 十一分之黄金年代 ~ 15%;
③、认清测试数组是不是早就平稳,如果 arr[mid] <= arr[mid+1],大家就认为数组已是持锲而不舍的并跳过merge(卡塔尔国方法,能够是不管三七八十朝气蓬勃有序的子数组算法的周转时刻变为线性的。
④、merge(卡塔尔(英语:State of Qatar)方法中不将元素复制到扶植数组,节省数组复制的日子。调用二种排序方法,后生可畏种:将数据从输入数组排序到帮扶数组;另意气风发种:将数据从帮助数组排序到输入数组。
重在:在各样档期的顺序调换输入数组和接济数组的剧中人物。

解答

是的,一定要三个子数组都维持原状时归拢技能收获不错结果。
假诺说数组不平稳的话,那么最终一定要获取八个数组的鱼目混珠。
集结后的数组中,归于原有数组的要素的对峙顺序不会被改变。
比方说子数组 1 3 1 和 2 8 5 原地合并。
结果是 1 2 3 1 8 5,当中 1 3 1 和 2 8 5 的相对顺序不改变。

 

优化点二:  测验待排序体系中左右半边是还是不是已平稳

 

透过测试待排序系列中左右半边是不是早就平稳, 在稳步的景观下幸免合併方法的调用。

 

诸如对单趟合併,大家对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);  // 单趟合并
  }

 

 

快排改过

  • 切换成插入排序。对于小数组,快排比插入排序慢;因为递归,快排的sort()焦点在小数组中也会调用自身。由此在排序小数组时可切换来插入排序——将sort()中的 if (hi <= lo) return; 改为 if (hi <= lo + M){Insertion.sort(a, lo, hi); return;},M 最好值和系统相关,5~15时期日常较好。
  • 三取样切分。使用子数组的一小部分要素的中位数来切分数组,那样切分更加好,代价是需总括中位数。
  • 熵最优的排序。实际选择常常现身含有多量双重成分的数组,叁个要素全体再一次的子数组就不供给后续排序了,但在此以前的算法还恐怕会继续切分成更加小的数组。轻易的消除办法是将数组切分为三局地(详见Dijkstra三向切分),分别对应小于、等于和超过切分成分的数组成分,这种比近期二分更复杂,相关难题有Netherlands国旗问题。

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

对此唯有若干莫衷一是主键的恣意数组,归总列排在一条线序时间复杂度是线性对数,而三向切分快排是线性的。对于随便遍及的输入,最优的依赖相比的算法平均所需比较次数和三向切分快排平均所需比较次数相互处于常数因子范围内。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.5

优化点三:去除原数组系列到扶持数组的正片

在上面介绍的依照递归的统一排序的代码中, 大家在历次调用merge方法时候,我们都把a对应的连串拷贝到补助数组aux中来,即

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

 

实则,我们能够透过风华正茂种**看起来比较逆天的办法把那一个拷贝进程给去除掉。。。。。**

 

为了达到那点,大家要在递归调用的各样等级次序沟通输入数组和出口数组的剧中人物,进而持续地把输入数组排序到赞助数组,再将数据从辅助数组排序到输入数组。

 

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

 

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

 

在那地大家做了四个操作:

  • 在排序前拷贝三个和原数组成分完全相像的帮扶数组(不再是开创一个空数组了!)
  • 在递归调用的种种等级次序沟通输入数组和出口数组的剧中人物

 

 

注意, 外界的sort方法和中间sort方法选用的a和aux参数正巧是倒转的

图片 34

 图片 35

 

与此相类似做的话, 我们就足以去除原数组连串到扶助数组的正片了!

 

但是您恐怕会问: 骚年, 我们要排序的可是原数组a啊! 你不怕一非常大心最后浑然排序的是赞助数组aux并非原数组a吗?

 

Don't worry !! 这种景象不会生出, 看图:

 

图片 36

 图片 37

 

由图示易知, 因为表面sort和merge的参数顺序是如出生龙活虎辙的, 所以,无论递归进程中援助数组和原数组的剧中人物怎样替换,对最终三回调用的merge来说(将一切数组左右半边合为平稳的操作),   最终被排为有序的都以原数组,并不是帮扶数组!

 

 

整整代码:

 

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

 

 

测量检验代码和输出结果同上文。

 

《算法导论》上的快排

优化测验代码

快快复制数组的法子】,提示:点击巴黎绿字体查看方法详细情形。

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

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

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

    }

}
题目

当输入数组的高低 N=39 时,给来自顶向下和自底向上的会师排序中各次归拢子数组的朗朗上口及顺序。

依照循环的统一排序(自底向上)

 

听闻循环的拜望排序又叫做自底向上的合併列排在一条线序

 

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

图片 38

quicksort普通版本

优化测量试验结果

瞩目:优化结果就算好些个,不过当其数组周围平稳的时候,速度有了冲天的进级。

相对等级数据量

只顾:编写翻译器私下认可不适用 assert 检查评定(不过junit测量检验中适用),所以要利用时要足够参数虚构机运行参数-ea 具体增加进程,请参见eclipse 和 IDEA 设置设想机运转参数

解答

历次合併子数组的分寸和种种如下:

自顶向下

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

 

循环归并的中坚观念

图片 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++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素
      }
    }
  }
}

 

 

快排随机化版本

引进随机性,能够使算法对于持有的输入都能博取较好的期望品质。在快排中接纳专断取样的随机化技巧——从子数组 A[p...r] 中随便接受叁个因素作为主元。为此,能够将 A[r] 与从 A[p...r] 中随机选出的一个因素沟通来确定保证主元 x = A[r] 是等可能率地从子数组的 r-p+1 个成分中获取的。因为主元是随机选的,期待在平均处境下对输入数组的剪切是比较平均的。

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

2.2.6

循环归总的轨迹图像

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

 

图片 41

 

 

图片 42

 图片 43

 图片 44

 

 

快排时间复杂度

  • 最坏情状:
    当划分产生的多个子难题各自包罗了 n-1 个和 0 个成分时,划分时间复杂度为 O(n卡塔尔(英语:State of Qatar),因为对贰个轻重为 0 的数组实行递归调用会直接回到,因而 T(0卡塔尔国 = O(1卡塔尔,于是算法运转时刻的递归式为:T(n卡塔尔国 = T(n-1卡塔尔国 + T(0卡塔尔(قطر‎ + O(n卡塔尔(英语:State of Qatar) = T(n-1卡塔尔(英语:State of Qatar)+O(n卡塔尔(英语:State of Qatar) = O(n^2卡塔尔(قطر‎。其他,在输入数组完全有序时,快排时间复杂度仍为O(n^2卡塔尔,而插入排序则为 O(n卡塔尔(英语:State of Qatar)。

  • 最佳状态:
    partition 得到的多少个子难点规模都不超过 n / 2,子难题规模分别为 n / 2 和 n / 2 - 1,当时算法运营时刻递归式为:T(n卡塔尔国 = 2T(n / 2卡塔尔(英语:State of Qatar) + O(n卡塔尔(قطر‎ = O(nlogn卡塔尔(英语:State of Qatar)。

  • 平衡的细分:
    快排平均运转时刻更就像于最佳状态,而非最坏处境。如按 9:1 分开,递归树如下:

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

quicksort递归树

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

编写制定八个主次来测算自顶向下和自底向上的合併列排在一条线序访谈数组的规范次数。
使用那几个程序将 N=1 至 512 的结果绘成曲线图,并将其和上限 6NlgN 绝比较。

随机化版本
解答

图片 45

橄榄黑是上限,蓝点是自顶向下,红点是自底向上。
鉴于二种排序访谈数组的次数是同大器晚成的,因而蓝点和红点重合。

1.6 优先队列

先行队列援助删去最大体素和插入成分。基于二叉堆的事情发生前队列,是用数组保存成分并遵照一定原则排序,以贯彻急忙地(对数等第)删除最大体素和插入元素。优先队列实际运用蕴涵模拟系统、任务调解和数值计算等。

通过插入一列成分然后一个个剔除个中的一丝一毫成分,就足以用事情未发生前队列达成排序算法。堆排序发源于依赖堆的早期队列的兑现。

代码

付出绘图部分的代码:

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

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

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

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

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

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

                dataSize *= 2;
            }

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

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

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

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

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

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

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

            graphics.Dispose();
        }
    }
}

 

API

刚开始阶段队列是生龙活虎种抽象数据类型,表示了蓬蓬勃勃组值和这个值的操作。优先队列最首要操作是去除最大因素和插入成分,

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

2.2.7

前期队列的调用示例

叁个事情发生前队列的用例

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

证实归拢列排在一条线序的可比次数是单调依次增加的(即对于 N>0,C(N+1卡塔尔国>C(N卡塔尔(قطر‎)。

初级完结

图片 46

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

解答

依靠书本给出的命题 G 和命题 H(汉语版 P173/176,德文版 P275/279),
正如次数的下限 C(N卡塔尔国 = 二分之生龙活虎 * NlgN
N 和 lgN 都以干瘪依次增加且高于零的(N>1卡塔尔国,因而 C(N卡塔尔国 也是干Baba依次增加的

 

堆的定义

在二叉堆数组中,每一种成分都要保管大于等于另三个特定岗位的元素。相应地,那么些地点成分又起码超越等于数组中另三个要素。
堆有序:风流倜傥棵二叉树的每一个结点都高于等于它的三个子结点,根结点是堆有序的二叉树中的最大结点。

2.2.8

二叉堆表示法

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

二叉堆是风度翩翩组能用堆有序的完全二叉树排序的成分,并在数组中按层级存款和储蓄(不用数组第2个岗位)

在四个堆(后文都指二叉堆),地点 k 的节点的父节点在 $lfloorfrac{k}{2}rfloor$,八个子节点分别为 2k 和 2k+1。

图片 47

堆的表示

风度翩翩棵大小为 N 的完全二叉树的中度为 $lfloor logNrfloor$

题目

生龙活虎旦将算法 2.4 修正为:
只要 a[mid] <= a[mid+1] 就不调用 merge(卡塔尔(قطر‎ 方法,
请证实用归总列排在一条线序处理多个早就平稳的数组所需的可比次数是线性级其他。

堆的算法

堆完成的比较和调换方法:

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

改正后的算法对曾经平稳的意况做了优化
数组对半切分并列排在一条线序后,
如果 a[mid] < a[mid + 1](左半某个的结尾二个要素小于右半部分的第八个成分)
那正是说大家能够直接统黄金年代数组,无需再做多余的操作

今昔的输入是叁个已经排序的数组
算法独一的相比产生在认清 a[mid] < a[mid + 1] 这一个规格时
后生可畏旦数组有 N 个要素
正如次数满意 T(N卡塔尔国 = 2 * T(N / 2) + 1, T(1) = 0
倒车为非递归方式即为:T(N卡塔尔(英语:State of Qatar) = cN / 2 + N - 1
里面 c 为随便正整数

 

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

若堆的有状态因有个别节点变得比它的父节点更加大而被打破,则需经过置换它和它的父节点来修复堆。调换后,该节点比它的四个子节点都大。重复该进度,直到碰着越来越大的父节点。

图片 48

上浮

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

2.2.9

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

若堆的有序状态因有些节点比它的八个子节点或内部之风流倜傥更加小而被打破,则可通过将它和它的四个子节点比较大者沟通来过来堆。重复该进度,直到它的子节点都比它更加小或达到了堆的平底。

图片 49

下沉

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

插入成分:将新元素加到数组末尾,扩张堆的大小并让该新成分上浮到万分岗位。

图片 50

插入成分

剔除最大因素:从数组顶上部分删去最大的因素并将数组的终极三个要素放到顶上部分,减小堆的轻重缓急并让那几个成分下沉到合适岗位。

图片 51

删除最大因素

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

命题:对于二个包蕴 N 个要素的依靠堆的预先队列,布署成分操作只需不超越 lgN+1 次比较,剔除最大因素操作内需不超越 2lgN 次相比较。

证实:三种操作都亟待在根节点和堆底之间活动成分,而路线长度不超越lgN。对于路线上的每一个节点,剔除最大因素内需三遍比较(除了堆底成分),叁回用来找寻十分的大的子节点,一回用来规定该子节点是或不是须求上浮。

题目

在库函数中选取 aux[] 那样的静态数组时不性格很顽强在险阻艰难或巨大压力面前不屈帖的,
因为恐怕会有多少个程序同不经常间利用那一个类。
贯彻三个不用静态数组的 Merge 类,
但也绝不将 aux[] 变为 merge(卡塔尔 的风姿罗曼蒂克部分变量(请见本书的答应部分)。
唤醒:能够将扶植数组作为参数字传送递给递归的 sort(卡塔尔 方法。

多叉堆

一心三叉堆:对于数组中1至 N 的 N 个因素,地点 k 的节点大于等于位于3k-1、3k 和 3k+1 的节点,小于等于坐落于 (k+1卡塔尔国 / 3的节点。须要在树高 log_d(N卡塔尔(قطر‎ 和在种种节点的 d 个子节点找到最大者的代价之间找到折中,那决计于实现细节以至分裂操作的预料相对频繁程度。

解答

合法给出的归拢列排在一条线序完结中在 Sort 方法里开首化了 aux 数组。
源码见:

C#得以达成和合法的兑现充足附近,

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

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

然后创设贰个私有的递归 Sort 方法抓好际的排序操作。

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

丰裕叁个从未参数的结构函数,在 insert() 中增加将数首席营业官度加倍的代码,在 delMax() 中增加将数首席营业官度减半的代码。

代码
using System;

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

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

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

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

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

 

堆排序

能够把自由优先队列形成生机勃勃种排序方法,将装有因素插入叁个找出最小成分的先行队列,然后再重复调用删除最小成分的操作按顺序删除。用冬天数组完结优先队列这么做一定于进行三回插入排序,用堆达成获得堆排序。堆排序分多个品级:

  • 堆的构造:将原始数组重新协会布署进四个堆中。
  • 下沉排序:从堆中按依次减少顺序抽出全体因素并获得排序结果。

2.2.10

堆的结构

连接向优先队列插入成分可行,但更迅捷的格局是从右到左用 sink() 函数结构子堆。数组每一种岗位都早已经是叁个子堆的根节点了,sink() 对于那么些子堆也适用。若贰个节点的三个子节点都早已经是堆了,则在该节点上调用 sink() 可将它们成为四个堆。开头时只需扫描数组中二分一因素,因为能够跳过大小为1的子堆。最后在岗位1上调用 sink() 方法,扫描截止。在排序第一等第,堆的布局方法和大家无声无息想象的例外,因为大家指标是结构多少个堆有序的数组并使最大因素坐落于数组的上马(次大的要素在西隔)而非构造函数结束的尾声。

用下沉操作由 N 个元素布局堆只需少于 2N 次相比较以至个别 N 次沟通

题目

敏捷归总。
兑现八个 merge(卡塔尔(英语:State of Qatar) 方法,按降序将 a[] 的后半片段复制到 aux[],
下一场将其合併回 a[] 中。那样就能够去掉内循环中检验某半边是还是不是用尽的代码。
注意:那样的排序产生的结果是不平稳的(请见 2.5.1.8 节)。

下沉排序

将堆中最大意素删除,然后归入堆减弱后数组中空出的职位,该进度和甄选排序近似(按降序而非升序抽取全部因素),但因为堆提供了生龙活虎种未有排序部分找到最大体素的管事方法,所需相比次数少得多。

图片 52

堆的架交涉下沉排序

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

将N个成分排序,堆排序只需少于 2NlgN+2N 次相比(以至一半次数的沟通),2N 项来自于堆的布局,2NlgN 来源于每一趟下沉操作最大大概须求 2lgN 次相比较。

解答

官方近似给出了 java 落成,如下:

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

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

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

C# 达成见代码部分。

改过:先下沉后上浮

大部在下沉排序时期重新插入堆的成分会被一贯步入堆底。Floyd 壹玖陆壹年开采能够透过免去反省成分是或不是到达精确地方来节省时间。在下白木香港中华总商会是直接进级非常大的子节点直至到达堆底,然后再使成分上浮到科学地方,那样能够将相比次数收缩二分一——周围了合并列排在一条线序所需比较次数(随机数组)。该方法需额外层空间中,因而实际应用中唯有当比较操作代价比较高时才用(比方:将字符串或其余键值较长类型的因素排序时)。

堆排序在排序复杂性研讨中有关键地方,因为它是独一无二能同一时候最优地利用空间和岁月的办法——最坏情状下能作保使用 ~2NlgN 次比较和定位的附加空间。当空间丰富不安时(如嵌入式系统或低本钱移动器材)很盛行,因为它只用几行就能够落到实处较好的品质(以至机器码也是)。但今世体系非常少用,因为它敬谢不敏运用缓存。数组成分相当少和邻座的别的成分相比较,因而缓存未命中的次数要远高于大多数比较都在隔壁成分间展开的算法,如快排、合并列排在一条线序、以至是希尔排序。

在大数据量下,要管理 TopK 和 Multiway 难点,不可能排序(或无法全装进内部存款和储蓄器),如 10 亿因素中选最大 十三个,则只用三个能积攒拾个要素的队列就能够。

代码
using System;
using Merge;

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

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

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

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

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

 

1.7 排序算法和开始时期队列的使用

2.2.11

将种种数码排序

前边完成的排序对象是由完成了Comparable接口的对象组成的数组,那样能够使用 Java 的回调机制将轻巧落成了 Comparable接口的数据类型排序。达成Comparable接口只需定义一个compareTo()函数并在内部定义该数据类型的分寸关系。Java 中的 String、Integer、Double、File 和 URL都达成了Comparable接口。

题目

改进。
兑现 2.2.2 节所述的对合并列排在一条线序的三项纠正:
增长速度小数组的排序速度,
检查评定数组是还是不是业已稳步以致由此在递归中交流参数来幸免复制。

指南针排序

前边使用的艺术被叫作指南针排序,因为只管理成分的援用而不移步多少本身。在C/C++中,须要显著建议操作的是数量依然指向数据的指针,在 Java 中,指针的操作是隐式的。除了原有数字类型外,操作的连年数据的引用(指针)而非数据作者。

解答

法定达成见:

在 MergeSortX 类里加多贰个 CUTOFF 字段,排序时黄金时代旦数COO度小于它则一向调用插入排序进行排序。

在调用归拢措施前判别第多少个有序数组的末尾二个要素是或不是超越第一个有序数组的第一个成分,
万风姿洒脱过量的话就没有必要调用归总了,直接首尾相接就可以。

每趟归总都亟需七个数组,四个用来寄放合并结果,这一个数组中的内容是开玩笑的;
另三个则保留了合併前的数组,用于实际的合併进度。
归拢结束后,前贰个数组产生归总后的平稳结果(也正是下二回归总时的「归总前数组」),后三个数组中的内容则不再有效。
大家得以看出那多个数组的剧中人物在下二回合併时适逢其会能够沟通。

要小心的是,合并次数延续四个奇数(左边归总+侧边归拢+总合併),因而在首先次调用 Sort 方法时应当把 aux 和 a 交换传入。

不可变的键

若排序后用例仍然是能够更正键值,那么数组就不再有序了。Java 中可用不可变数据类型作为键来防止该难题,如String、Integer、Double和 File 都以不可变的。

代码
using System;

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

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

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

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

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

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

 

优惠的交流

应用援用另四个益处是能够不要移动整个因素。对于元素大而键小的数组来讲节约是宏大的,因为正如只需访谈成分一小部分,而排序进程大多数要素都不会被访问到。对于大致大肆大小的成分,援引在相仿景况下交流花费和比较费用大致同风姿洒脱(代价是内需额外层空间间存款和储蓄引用)。

2.2.12

各类排序方法

Java 的 Comparator 接口允许在贰个类中实现多样排序方法。它独有一个 compare() 方法来比很多个目的,用 Comparator 接口取代Comparable接口能够将数据类型定义和八个该数据类型的可比的定义区分开。举例 Insertion.sort(a, String.CASE_INSENSITIVE_ORDER),对 Transaction 对象数组定期间排序 Insertion.sort(a, new Transaction.WhenOrder()),按金额排序 Insertion.sort(a, new Transaction.HowMuchOrder()) 等。sort() 方法每一回都会回调 Transaction 类中的用例钦点的 compare() 方法,为防止每便排序都创立新的 Comparator 对象,使用 public final 来定义那一个相比较器(就疑似使用 String.CASE_INSENSITIVE_ORDER 一样)

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

次线性的附加空间。用大小 M 的数组分为 N/M 块(轻易起见,设 M 是 N 的约数)。
福衢寿车八个联结措施,使之所需的额外层空间间压缩到 max(M, N/M卡塔尔(قطر‎:
(i)能够先将一个块看作一个要素,将块的第三个因素作为块的主键,用采用排序将块排序;
(ii)遍历数组,将首先块和第二块合併,实现后将第二块和第三块归拢,等等。

行使比较器达成优先队列
  • 为 MaxPQ 加多一个实例变量 comparator 以致一个布局函数,该布局函数接收一个相比较器作为参数并用它将 comparator 伊始化。
  • 在 less(卡塔尔(قطر‎ 中检查 comparator 属性是不是为 null(假如不是就用它相比)

使用了 Comparator 的插入排序:

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

汉语版的翻译相比较难通晓
其实正是另一种归拢列排在一条线序的兑现方式
先把数组分成若干个分寸为 M 的块
对于每一个块,用选用排序进行排序
接着遍历数组,将依次块归拢起来

稳定性

若贰个排序算法能保存数组中重复成分的对峙地方则可被称之为稳定的。风度翩翩部分算法是平静的——插入排序和统一排序,但接受排序、Hill排序、飞速排序和堆排序不稳定。

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

举个例子对多少个数举办排序,那四个数是:35,10,17
五个数排序的决策树如下,结点代表比较对应地点上的数。
图片 54
对于 35,10,17 来讲,路线据守右、左、左,最终收获的结果正是 2 3 1(10,17,35)。
大家得以窥见决策树上的每一个卡牌节点都意味着大器晚成种排列顺序,对于 N 个数,叶子节点就有 N! 个
听别人讲二叉树的习性,中度为 h 的二叉树最多有 2^h 个叶子节点
这正是说,对于 N 个数,决策树的中度 h 的最小值能够经过下边那些姿势得出去
2^h >= n!
h >= log(n!)
故而能够获得决策树中度 h 的最小值是 log(n!)

接下去大家来计量平均路线长度
作者们令函数 H(k卡塔尔(英语:State of Qatar) 代表有 k 个叶子节点的平衡决策树的具有途径长度之和
上例中 H(6) = 2 + 2 + 3 + 3 + 3 + 3 = 16
是因为平衡决策树的性质,H(k卡塔尔 = 2H(k / 2卡塔尔(英语:State of Qatar) + k
(加上 k 的由来:左右子树的莫斯中国科学技术大学学比任何树的惊人小 1,由此每条路子的长短都必须要加 1,总共多加了 k 次)
因此 H(k) = klogk
现在令 k = n!
H(n!) = n!log(n!)
鉴于每一趟排序时我们只经过某一条路径(上例中大家只透过了右、左、左那条门路)
况兼每一种路子的现身可能率相等
就此平均相比次数应当为 H(n!) / n! = log(n!) = nlog(n)
表达达成

 

排名

逆序对数难点

2.2.14

中位数与种种总括

二个和排序有关但又无需完全的显要应用便是寻找风流倜傥组成分的中位数,有后生可畏种非常选用:找到意气风发组数中第 k 小的成分。通过前边的 TopM 难点用事情未发生前队列能够清除,或许排序后获得第 k 个因素也得以解决,但都以线性对数时间。实际上,当 k 超小或相当大时方可在线性时间找到:

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

不断切分知道子数组只包蕴第 k 个成分,当时 a[k] 含有微小的(k+1)个成分,a[0] 到 a[k-1] 都小于等于 a[k],而 a[k+1] 及其后的因素都高于等于 a[k]。若是每一次都刚巧将数组二分,则相比总次数是(N+N/2+N/4+...)直到找到第 k 个因素,依照等比数列求和公式该和显然低于 2N。

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

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

以下是可供参照他事他说加以考察的博客:
各个排序算法时间复杂度
面试中的排序算法计算
八大排序算法
必须要知道的八大种排序算法【java完成】
坐在马桶上看算法:快捷排序

题目

合併一直以来的队列。
编写二个静态方法,将八个静止的类别作为参数,再次回到二个联合后的牢不可破队列。

解答

相比四个不改变队列的首先个因素,取非常的小的叁个出队并放入额外建设布局的类别中。
双重上述手续直到多个种类都为空。

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

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

    return sortedQueue;
}

 

2.2.15

题目

自底向上的静止队列归总排序。
用上面包车型客车办法编写一个自底向上的联结排序:
给定 N 个成分,创造 N 个类别,每一个队列包涵个中多个因素。
始建二个由那 N 个连串组成的队列,然后不断用演习 2.2.14中的方法将队列的头八个元素归总,
并将结果重新参预到行列结尾,直到队列的行列只剩余二个要素结束。

解答

次第思路标题已经付诸,遵照题意完毕就可以。
Merge 方法能够平素选取前生机勃勃题的贯彻。

代码
using System;

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

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

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

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

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

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

            return sortedQueue;
        }
    }
}

 

2.2.16

题目

当然的联合排序。
编排二个自底向上的统一排序,当须要将七个子数组排序时能够使用数组中曾经平稳的有个别。
首先找到贰个静止的子数组(移动指针直到当前因素比上二个成分小甘休),
然后再寻觅另一个并将它们合并。
依照数组大小和数组中递增子数组的最大尺寸深入分析算法的运作时刻。

解答

自然归总列排在一条线序的贰个演示如下图所示:

图片 55
骨干进程和自底向上的联结排序相通,只是每一遍归总的块大小不必然相仿。

日子解析

图片 56

乘胜有序块的变大,排序耗费时间会收缩,但加强的多寡级会变高(归拢的平分块大小变大了)。

代码
using System;
using System.Diagnostics;

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

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

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

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

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

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

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

 

2.2.17

题目

链表排序。
贯彻对链表的本来排序
(那是将链表排序的最佳点子,因为它无需十二分的上空且运维时刻是线性对数级其他)。

解答

排序情势和 2.2.16 拾贰分看似,不再赘言,这里介绍一下合并方法。
图片 57
如 gif 图所示,先把要合併的五个链表拆出来,随后分明表头地点,然后开展统生龙活虎就能够。
归总截止后赶回 first。

结果解析如下图所示:
图片 58
趁着有序部分的增添,对于相仿大小的数组自然合併列排在一条线序的耗费时间会降低。
对于有序部分周围的情事,随着数组大小的倍增,耗费时间显示了O(nlogn卡塔尔(قطر‎的来头。

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

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

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

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

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

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

                if (mid.next == null)
                    break;

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

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

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

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

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

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

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

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

            first = current;

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

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

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

            return first;
        }

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

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

 

2.2.18

题目

打乱链表。
兑现一个分治算法,使用线性对数等级的岁月和对数级其余额外空间随便打乱一条链表。

解答

能够在用归总排序的办法做。
将归拢时取两侧极小的成分改为随机取意气风发侧的值,就能够完结打乱的职能。
算法的深入解析和平淡无奇归拢列排在一条线序生机勃勃致,知足题目须要。

代码

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

using System;

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

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

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

                if (mid.next == null)
                    break;

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


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

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

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

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

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

            first = current;

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

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

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

            return result;
        }

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

            return hi;
        }
    }
}

 

2.2.19

题目

倒置。
编辑二个线性对数等级的算法总括给定数组中“倒置”数量
(即插入排序所需的置换次数,请见 2.1 节)。
那一个数量和 Kendall tau 间距有关,请见 2.5 节。

解答

法定完成:

实则借使在归总列排在一条线序的时候总计 Less(aux[j], aux[i])满意的次数就可以,那么些次数就是我们要的值。

代码
using System;
using Merge;

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

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

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

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

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

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

 

2.2.20

题目

间接排序。
编辑三个不退换数组的联结排序,
它回到一个 int[] 数组 perm,其中 perm[i] 的值是原数组中第 i 小的要素的岗位。

解答

合法完毕:

把 Sort 方法中传唱的 a 数组换到多少个 index 数组,将 Merge 方法中的决断改为 Less(a[aux[j]], a[aux[i]]) 即可。

代码
using System;
using Merge;

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

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

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

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

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

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

 

2.2.21

题目

风姿浪漫式三份。
加以三个列表,每一个列表中带有 N 个名字,
编排叁个线性对数级其余算法来推断四分列表中是否含有公共的名字,
假定有,重临第七个被找到的这种名字。

解答

对三份列表进行合併列排在一条线序(O(nlogn卡塔尔国),随后遍历二次此中的生龙活虎份表,
用二分查找检查在其他三个表中是或不是存在近似的真名(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

题目

三向合并列排在一条线序。
若是每一趟大家是把数组分成多个部分而不是五个部分并将它们各自动排档序。
然后开展三向归拢。
这种算法的运作时刻的进步数据级是有个别。

解答

图片 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.2.11)的功用,
并相比较正文中得以达成的统一排序和练习 2.2.10 所完成的会集排序之间的属性。
依附经验给出应该在哪天为子数组切换来插入排序。

解答

图片 60
阈值合合时,大概会有十三分之意气风发的品质提高。
阈值在 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耗时1t耗时2t阈值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耗时1t耗时2t比率");
            for (int i = 0; i < 6; i++)
            {
                double mergeSortTime = 0;
                double mergeSortUnstableTime = 0;
                for (int j = 0; j < trialTime; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(n);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    mergeSortTime += SortCompare.Time(mergeSort, a);
                    mergeSortUnstableTime += SortCompare.Time(mergeSortUnstable, b);
                }
                mergeSortTime /= trialTime;
                mergeSortUnstableTime /= trialTime;
                Console.WriteLine(n + "t" + mergeSortTime + "t" + mergeSortUnstableTime + "t" + mergeSortTime / mergeSortUnstableTime);
                n *= 2;
            }
        }
    }
}

 

2.2.24

题目

精雕细琢的有序测量检验。
在尝试中用大型随机数组评估演练 2.2.8 所做的改革的效应。
依据经历用 N(被排序的原始数组的轻重缓急)的函数描述条件语句(a[mid] <= a[mid + 1])创设(无论数组是还是不是有序)的次数。

解答

图片 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卡塔尔(英语:State of Qatar) 的,能够用堆可能败者树优化为对数品级

代码
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("ntrestttimes");
            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 + "mst自底向上:" + time2 / trialTimes + "ms");
                n *= 10;
            }
        }
    }
}

 

2.2.29

题目

理所必然的晤面排序。对于 N=10^3、10^6 和 10^9,类型为 Long 的轻松主键数组,依照经历给出自然的合併列排在一条线序(请见练习2.2.16)所要求的遍数。
晋升:没有必要达成那几个排序(以至不须要转移全体完整的 61位主键)也能燃眉之急那道演练。

解答

统统有序时只须求一回合併(直接出口),
逆序时索要 n - 1 次合併(退化为插入排序),
平均要求 n/2 次合併。
因而个别必要 500,500000,500000000 次合并。

本文由金沙手机娱乐网址发布,转载请注明来源

关键词: