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

By admin in 4858.com on 2019年3月29日

写在前边

全方位项目都托管在了 Github
上:

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

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

善用 Ctrl + F 查找难点。

1 初级排序算法

排序算法关心的重假使重新排列数组成分,个中种种成分都有3个主键。排序算法是将兼具因素主键按某种格局排列(平时是依据轻重缓急恐怕字母顺序)。排序后索引较大的主键大于等于索引较小的主键。

参考资料

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

 

Q:什么是归并排序?
A:它是建立在统一操作上的一种有效的排序算法;是使用分治法的1个老大独立的行使;是一种祥和的

习题&题解

排序算法类的沙盘

public class Example{
    public static void sort(Comparable a[]){}
    private static boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){
        for(int i = 0;  i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static boolean isSort(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        //从标准输入读入字符串,排序后输出
        Integer[] a = new Integer[]{1,34,55,66,7};
        sort(a);
        assert isSort(a);
        show(a);
    }
}
  • 排序费用模型:斟酌排序算法时,要求总计正如和置换的次数。对于不交换到分的算法,总括走访数组的次数
  • 额外内部存款和储蓄器使用:排序算法的额外内部存款和储蓄器费用和平运动行时刻同一首要。排序算法可分两类:除了函数调用所需的栈和固定数目标实例变量之外无需附加内存的原地排序算法,以及须要额外内部存储器空间来存款和储蓄另一份数组副本的别样排序算法。
  • 数据类型:上述排序算法模板适用于任何实现了Comparable接口的数据类型。例如,Java中封装的Integer和Double,以及String和别的很多高档数据类型(如File和URAV4L)都达成了Comparable接口,因而得以平昔调用那些品种的数组作为参数调用大家协调达成的排序方法。

诸如——用快排对N个随机的Double数据举办排序:

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

在创制自身的数据类型时,只要落成Comparable接口并达成该接口中的compareTo()方法,来定义指标项目对象的理所当然次序,如:

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

对此 v < w、v = w 和 v > w
二种意况,Java习惯是在v.compareTo(w)被调用时分别重临二个负整数、零和二个正整数(-壹 、0和1)。一般的话,若
v 和 w 不能够相比只怕两者之一是 null,v.compareTo(w) 将会抛出多个十三分。

归并排序的概念

归并排序的完结自身是那样来讲述的:先对个别多少个成分通过两两合并的不二法门进行排序,形成3个长度稍大学一年级部分的静止类别。然后在此基础上,对四个长度稍大学一年级些的雷打不动种类再开始展览两两联合,形成三个长度更大的稳步连串,有序类别的的尺寸不断增加,直到覆盖全体数组的轻重停止,归并排序就马到成功了。

 

骨干思维

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

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

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

2.2.1

1.1 选择排序

选拔排序:首先找到数组中型小型小的的成分,其次,将它和数组的首先个因素沟通地点(要是第③个要素最小就和融洽调换)。再度,在结余成分中找到最小的成分,将它与数组的第四个因素沟通地点。如此往复,直到将总体数组排序。那种措施叫做慎选排序,因为它在不停采纳剩余成分中的最小者

less()、exch()和isSort()的贯彻见排序算法类的模板

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

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

  • 长度为 N 的数组,选拔排序需求大约 (N^2) / 2 次相比和 N 次交流

0 到 N-1 的任意 i 都会进展三次交流和 N-1-i 次相比,因而总共有 N
次交流以及(N-1)+(N-2)+…+2+1 = N(N-1) / 2 ~ N^2 / 2次比较

  • 分选排序有多个鲜明特点:
  1. 运作时刻和输入非亲非故。为了找出最小成分而扫描1次数组并不能够为下2次扫描提供怎么样新闻。那种场地在一些意况下是欠缺,因为一个已经稳步的数组或是主键全部等于的数组和三个要素随机排列的数组所用的排序时间相同长,而其余算法更善于利用输入的先导状态。
  2. 多少移动最少。每一次交流都会改变三个数组成分的值,因而选用排序用了N次调换——调换次数和数组大小是线性关系,而别的任何算法都不具有这几个特点(半数以上增加数量级都以线性对数或平方级别)。

归并排序的三种实现情势:递归和巡回

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

 

那二种归并算法尽管完成形式不一致,但依然有共同之处的:

 

1.
无论是基于递归依然循环的统一排序,
它们调用的主导措施都以一致的:实现一趟合并的算法,即多少个已经稳步的数组体系合并成1个更大的静止数组系列 
(前提是多个原连串都以有序的!)

2.
从排序轨迹上看,统一类别的尺寸皆以从小(2个成分)到大(整个数组)拉长

 

 

原地归并的悬空方法

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 插入排序

插入排序:整理扑克时相似都以一张华晨张来,将每张牌插入到任何已经平稳的牌中的适当地点。在计算机实现中,为了要给插入成分腾出空间,须求将别的具备因素在插入在此以前都向右移动1个人。那种算法叫做插入排序

  • 与选用排序一样,当前目录左侧全体因素都以平稳的,但它们最后地方还不鲜明,为了给更小元素腾出空间,它们也许会被移动,但当索引到达数组右端时,数组排序就完了了。
  • 与采用排序不相同的是,插入排序所需时日取决于输入申月素的开始顺序。如对近似平稳的数组排序要比自由数组快很多。

对此自由排列的长短为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。若数组中倒置的数目紧跟于数组大小的某部倍数,则这一个数组是一部分有序。插入排序对如此的数组很管用,事实上,当倒置数量相当的小时,插入排序恐怕比别的任何算法都快。

插入排序的沟通操作和数组中倒置数量同样,需求比较的次数超越等于倒置的数据,小于等于倒置的数量增加数组的大小再减一。要大幅提升插入排序速度并简单,只需在内循环上校较大要素都向右移而不总是交流多少个成分(那样访问数组次数就能减半),即上述第1种完结。

单趟归并算法

 

自顶向下的统一排序(化零为整,递归消除)

是因为上述的原地归并只能将四个不变的数组归并成3个静止的数组,所以得依据原地归并的悬空去贯彻一种递归归并。

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

Q:为啥它能将科学的排序?
A:就算它能将多个子数组排序,那么它就能够通过归并五个子数组来将一切数组排序。

解答

4858.com 1

 

1.3 希尔排序

希尔排序:是一种基于插入排序的排序算法。对于普遍乱序数组插入排序相当的慢,因为它只会换到相邻的因素,若最小元素在数组最终,则对其索要活动N-2次。希尔排序立异了插入排序,交流不相邻的成分以对数组的片段进展排序,并最后用插入排序将部分有序的数组排序。

  • h有序数组:数组中自由间隔为 h 的要素都稳步。即2个 h有序数组
    就是 h
    个相互独立的稳步数组编织在共同构成的一个数组。若h一点都不小,则可将成分移到很远地点,为贯彻更小的h有序创建便利。

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

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

算法实例解释可参看:
空话经典算法体系之三
希尔排序的兑现
图解排序算法(二)之希尔排序

希尔排序更高速原因是它度量了子数组的层面和有序性。排序之初,各样子数组都相当短,排序之后子数组都以一对有序的,那二种状态都合乎插入排序。子数组部分有序的品位取决于递增类别的挑三拣四。

单趟排序的达成分析

 

上边作者先介绍二种区别归并算法调用的公共措施,
即完结单趟归并的算法。(八个曾经平稳的数组体系合并成一个更大的雷打不动数组系列)

 

在初始排序前创办有三个和原数组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]…依次类推),并取得较小成分的下2个因素,
和另一个行列中较大的要素比较
。因为前提是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

4858.com 2

 

 

 

4858.com 3

组成地点的长河3, 
相比 i 和 j 当前所指的aux中的元素的深浅,
取得在那之中相比较大的不胜成分(例如上海教室中的i),将其放入数组a中,
此时(在图中借使意况下): i加1,左游标右移。  同时k也加1,
k游标也向右移动

 

图B

4858.com 4

 

 

4858.com 5

整合方面包车型客车历程4,
在 i 和 j 都向右移动的长河中,
在图中假如情形下,因为j当前所指的要素(图中位置)大于左半边即a[low…mid]的持有因素,导致
i 不断加码(右移)且通过了界线(mid),
所以这时候就不必要相比了,只要把j当前所指地方到high的要素都搬到原数组中,填满原数组中多余的任务,
单趟归并就做到了, 在这一段进度中 j 再而三加1,右游标一连右移。 
同时k也接连加1, k游标也接连右移, 直到 j == high且k == high截至

 

依据上边的发挥,
总括出单趟归并算法中最关键的5个标准化判断景况:

  1. 左半边用尽(取右半边的要素)
  2. 右半边用尽(取左半边的因素)
  3. 右半边成分小于左半边当前元素(取右半边的因素)
  4. 归并排序及其优化,归并排序算法的编码和优化。右半边成分大于等于左半边当前因素(取左半边的因素)

 

 

运作轨道

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

2.2.2

1.4 归并排序

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

单趟排序算法的代码

 

有了上边的表达,写那一个算法就简单了呢

 

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

 

【注意】在排序之初创建了2个尺寸和原数组a相同的声援数组aux,那有个别代码上文未提交

 

代码完毕

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

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

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

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

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

原地归并的肤浅方法——merge()

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

上述方法将具备因素复制到多个扶植数组aux[]中,再把归并结果放回原数组a[]中。方法在归并时(第①个for循环)举行了两个判断:左半边用尽(取右半边成分)、右半边用尽(取左半边成分)、左半边的近期成分小于右半边的近年来成分(取左半边成分)以及右半边的当前因素小于左半边的当下成分(取右半边成分)

单趟排序的长河图解

 

为了更详细的描述单趟排序的经过,上边在上头的图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 右移

4858.com 6

 4858.com 7

 

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

4858.com 8

 4858.com 9

 

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

4858.com 10

 4858.com 11

 

就像是上述,
不解释

4858.com 12

4858.com 13

 

 

好像上述,
不解释

4858.com 14

 4858.com 15

 

接近上述,
不解释

4858.com 16

 4858.com 17

 

类似上述,
不表达

4858.com 18

 

4858.com 19

 

注意, 这那里 j
扩大导致 j> high,  以往的气象是“右半边用尽”,
所以将aux左半边剩余的成分9放入a剩下的局地a[7]中,
单趟排序达成

4858.com 20

 

4858.com 21

 

【注意】
上边那么些事例中的种类只是数组的一某个,
并不一定是整整数组

 

 

自家在上边介绍过,二种区别归并算法:
基于递归的统一和基于循环的集合, 
都是以单趟归并的算法为底蕴的。

 

上边先来讲一下依据递归的合并排序(自顶向下的合并排序)

 

质量分析

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

对此长度为 N 的任意数组,自顶向下的合并排序必要 1/2NlgN – NlgN
次比较

对于长度为 N 的任意数组,自顶向下的晤面排序最多需求做客数组 6NlgN
(2N 次用来复制、2N
次用来将排好序的要素移动回来、其它最多比较 2N 次)。

Q:首要弱点是怎么着
A:辅助数组所利用的附加空间和 N 的高低成正比。

解答

4858.com 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

归并革新:
  • 对小范围数组使用插入排序。使用插入排序处理小范围的子数组,一般能够将归并排序运转时刻减弱1/10~15%。
  • 测试数组是或不是业已逐步。添加3个论断标准,若 a[mid] <= a[mid + 1]
    则认为数组已经稳步并跳过 merge()
    方法。这些改变不影响排序的递归调用,但随便有序的子数组算法的运营时刻就变为线性了。
  • 不将成分复制到帮衬数组。能够节省成分复制到援助数组所用时间(但空间十一分),此时需调用两种排序方法,一种从输入数组排序到援救数组,一种从支持数组排序到输入数组,技巧是在递归调用的各类层次调换输入数组和扶植数组的剧中人物。

递归归并的思念

4858.com 23

 

4858.com 24

 

 

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

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

 

分别代表对超越47%边连串递归、对右半边种类递归、单趟合并操作。

 

凡事代码:

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

 

 

测试代码:

 

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

 

 

输出结果

0
1
1
2
3
5
6
7
9

 

 

运营轨迹
题目

用自底向上的碰面排序解答练习 2.2.2

自底向上的联结排序

先归并微型数组,然后再成对归并获得的子数组,直到将一切数组归并到一起,这比正规递归方法所需代码量少。首先是两两归并(各种成分是大大小小为1的数组),然后四四归并(将七个高低为2的数组归并成3个有5个因素的数组),然后是八八归并…

    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小)。

4858.com 25

自底向上的会合排序的联合结果

长度为 N 的数组,自底向上的统一排序需 4/8NlogN 至 NlogN
次正如,最多访问数组 6NlogN 次。

  • 当数老板度为2的幂时,自顶向下和自底向上归并排序所用相比和走访次数相同,只是顺序不一致。
  • 自底向上归并排序适合用链表公司数量。此办法只需重新组织链表连接就能将链表原地排序(不需创设任何新的链表节点)。

用自顶向下或自底向上形式完成任何分治算法都很自然。归并排序表达,当能用一种“化整为零”方法化解时方可尝试另一种“按部就班”的法子。

递归栈深度和调用顺序

 

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

从上到下,是逐一merge的程序调用顺序,1起始调用,
15尾声调用

从右到左,
递归栈由深到浅
,例如 1,2,4,5的递归深度是一样的,
而3比它们浅贰个层次

4858.com 26

 

 

4858.com 27

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

 

对上海教室可依照代码来领悟

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

 

 

第2,在第③层递归的时候,先进入的是首先行的sort方法里(A处),然后随即又进入了第2层递归的率先行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)

 

 

代码落成

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

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

4858.com 28

 

排序算法的复杂度

钻探复杂度的率先步是起家一个测算模型。对排序来说,基于相比较的算法对数组操作方法是由主键相比较决定。

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

递归归并的轨道图像

 

(上边显示的联结实行了一部分优化,对小数组使用插入排序)

4858.com 29

 

4858.com 30

 

 

 

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

 

 

4858.com 31

 

4858.com 32

 

 

天性分析

对于长度为 N 的任意数组,自底向上的相会排序要求 1/2NlgN – NlgN
次比较
,最多做客数组 6NlgN 次。(每一边走访数组 6N 次,比较次数
N/2 – N)

当数CEO度为 2
的幂
时,自顶向下和自底向上的合并排序所用的比较次数数组访问次数恰好相同,只是顺序不一致。

自底向上的统一相比吻合用链表组织的数据。

2.2.4

Q&A

  1. 归并排序比希尔排序快呢?
    在其实应用中,它们运营时刻距离在常数级别。
  2. 何以不把数组 aux[] 声明为 merge() 方法的一些变量?
    为防止每一回归并时,就算归并相当小的数组都创立多个新数组,不然创造新数组将成为归并排序运转时刻首要部分。更好的不二法门是将
    aux[] 变为 sort() 方法的部分变量,并视作参数字传送给 merge()
    方法。
  3. 当数组中设有双重元素时归并排序品质怎么着?
    若有所因素相同,则归并排序运营时刻是线性的。若有七个不等重复值,运营时刻是线性对数的(和颇具因素都不重复知足相同循环条件)。

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

 

总结

从不其余依照相比的算法能够保障使用有限 lg(N!) – NlgN 次相比较将长度为
N 的数组排序。

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

题目

是还是不是当且仅当三个输入的子数组都逐步时原地归并的虚幻方法才能赢得正确的结果?
表达你的下结论,也许给出三个反例。

1.5 急速排序

飞快排序特点包罗原地排序(只需1个非常小的扶助栈),且将长度为 N
的数组排序所需时日和 NlogN 成正比,内循环比超越二分一排序算法都要短小。

火速排序:是一种分治排序算法。将2个数组分成多个子数组,将两某些单独地排序。快排和归并排序是填补的,归并排序将数组分成八个子数组分别排序,并将稳步的子数组归并以将总体数组排序;快排的排序情势是当三个子数组都纹丝不动时整个数组也理所当然有序了。前者的递归调用产生在拍卖整个数组在此以前;后者递归调用发生在处理任何数组之后。在归并排序中,3个数组被等分为两半;在快排中,切分位置取决于数组的内容。

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

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

用分裂的法门处理小框框难题能革新大部分递归算法的习性,因为递归会使小范围难点中方法调用太过频仍,所以革新对它们的拍卖方法就能改正整个算法。
因为插入排序十一分不难
因而一般的话在小数组上比归并排序更快
那种优化能使归并排序的运维时刻减少百分之十到15%;

 

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

  if(low>=high) { return; }

 

改成

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

 

就足以了,那样的话,那条语句就有所了多个职能:

 

1.
在适用时候甘休递归

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

 

实际代码:

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

 

 

优化方案

①、一直将扶持数组作为参数字传送入,而不直接使用静态数组。
②、对小规模子数组使用插入排序,一般能够将归并排序的时刻减弱 一成 ~
15%;
③、判定测试数组是还是不是曾经平稳,如果 arr[mid] <=
arr[mid+1],我们就认为数组已经是有序的并跳过merge()
方法,能够是私自有序的子数组算法的运作时刻变为线性的。
四 、merge()
方法中不将成分复制到补助数组,节约数组复制的时日。调用二种排序方法,一种:将数据从输入数组排序到帮扶数组;另一种:将数据从帮助数组排序到输入数组。
第二:在种种层次调换输入数组和扶植数组的剧中人物。

解答

是的,必要求多个子数组都稳步时归并才能收获不错结果。
倘诺说数组不平稳的话,那么最后不得不获取七个数组的插花。
集合后的数组中,属于原有数组的因素的相对顺序不会被转移。
诸如子数组 1 3 1 和 2 8 5 原地归并。
结果是 1 2 3 1 8 5,个中 1 3 1 和 2 8 5 的周旋顺序不变。

 

快排革新

  • 切换来插入排序。对于小数组,快排比插入排序慢;因为递归,快排的sort()格局在小数组中也会调用本人。因而在排序小数组时可切换来插入排序——将sort()中的
    if (hi <= lo) return; 改为
    if (hi <= lo + M){Insertion.sort(a, lo, hi); return;},M
    最棒值和系统有关,5~15里头平日较好。
  • 三取样切分。使用子数组的一小部分因素的中位数来切分数组,那样切分更好,代价是需总括中位数。
  • 熵最优的排序。实际运用平日出现含有大批量再一次成分的数组,3个因素全体重新的子数组就不供给持续排序了,但后面包车型地铁算法还会持续切分成更小的数组。不难的缓解方法是将数组切分为三部分(详见Dijkstra三向切分),分别对应小于、等于和过量切分成分的数组成分,那种比当下二分更扑朔迷离,相关难点有荷兰国旗问题。

4858.com 33

三向切分示意图

  1. a[i] 小于 v,将 a[lt] 和 a[4858.com,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);
        }
    }
}

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

优化点二:  测试待排序系列中左右半边是或不是已平稳

 

经过测试待排序连串中左右半边是或不是业已平稳,
在静止的图景下制止合并方法的调用。

 

譬如说对单趟合并,大家对a[low…high]中的a[low…mid]和a[mid…high]拓展统一

因为a[low…mid]和a[mid…high]自然就是有序的,存在a[low]<a[low+1]…<a[mid]和a[mid+1]<a[mid+2]…<
a[high]这三种关系,
假定判断出a[mid]<=a[mid+1]的话,
不就足以确认保证从而a[low…high]笔者正是不供给排序的平稳类别了吧?

 

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.5

《算法导论》上的快排

优化点三:去除原数组连串到助手数组的正片

在地点介绍的依照递归的会晤排序的代码中,
我们在每一趟调用merge方法时候,大家都把a对应的种类拷贝到支持数组aux中来,即

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

 

事实上,我们得以通过一种**看起来相比较逆天的方法把这几个拷贝进度给去除掉。。。。。**

 

为了达成那或多或少,我们要在递归调用的各样层次调换输入数组和出口数组的剧中人物,从而不断地把输入数组排序到救助数组,再将数据从帮忙数组排序到输入数组。

 

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

 

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

 

在那里大家做了多少个操作:

  • 在排序前拷贝三个和原数组成分完全平等的扶植数组(不再是创立一个空数组了!)
  • 在递归调用的每一种层次沟通输入数组和输出数组的角色

 

 

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

4858.com 34

 4858.com 35

 

如此做的话,
大家就足以去除原数组种类到救助数组的正片了!

 

但是您恐怕会问:
骚年, 大家要排序的然而原数组a啊! 你固然一十分大心最终浑然排序的是赞助数组aux而不是原数组a吗?

 

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

 

4858.com 36

 4858.com 37

 

由图示易知,
因为外部sort和merge的参数顺序是同等的, 所以,无论递归进程中扶助数组和原数组的角色怎么样替换,对终极2遍调用的merge而言(将全方位数组左右半边合为平稳的操作),  
末了被排为有序的都是原数组,而不是扶持数组!

 

 

全套代码:

 

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

 

 

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

 

优化测试代码

高速复制数组的法子】,提醒:点击青白字体查看方法详情。

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

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

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

    }

}
题目

当输入数组的大大小小 N=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;
    }
}

4858.com 38

quicksort普通版本

基于循环的合并排序(自底向上)

 

依照循环的集合排序又称为自底向上的联合排序

 

优化测试结果

专注:优化结果即使大多,可是当其数组接近平稳的时候,速度有了莫大的升官。

相对级别数据量

只顾:编写翻译器暗中认可不适用 assert
检查和测试(可是junit测试中适用),所以要使用时要加上参数虚拟机运行参数-ea
具体添加进度,请参考eclipse 和 IDEA
设置虚拟机运营参数

解答

每一回归并子数组的轻重缓急和顺序如下:

自顶向下

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

自底向上

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

 

快排随机化版本

引入随机性,能够使算法对于全体的输入都能博取较好的盼望品质。在快排中动用随机取样的随机化技术——从子数组
A[p...r] 中自由选择二个成分作为主元。为此,能够将 A[r] 与从
A[p...r] 中随机选出的二个成分调换成保管主元 x = A[r]
是等可能率地从子数组的 r-p+一个要素中获取的。因为主元是随机选的,期望在平均情状下对输入数组的撤销合并是比较均匀的。

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

循环归并的骨干考虑

4858.com 39

 4858.com 40

 

 

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

 

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

 

 

2.2.6

快排时间复杂度

  • 最坏情形:
    当划分发生的多个子难点分别包涵了 n-1 个和 0
    个因素时,划分时间复杂度为 O(n),因为对3个尺寸为 0
    的数组举行递归调用会直接重回,由此 T(0) =
    O(1),于是算法运营时刻的递归式为:T(n) = T(n-1) + T(0) + O(n) =
    T(n-1)+O(n) = O(n^2)。其它,在输入数组完全有序时,快排时间复杂度仍为
    O(n^2),而插入排序则为 O(n)。

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

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

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

quicksort递归树

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

循环归并的轨迹图像

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

 

4858.com 41

 

 

4858.com 42

 4858.com 43

 4858.com 44

 

 

题目

编辑3个顺序来测算自顶向下和自底向上的集合排序访问数组的标准次数。
行使这些程序将 N=1 至 512 的结果绘成曲线图,并将其和上限 6NlgN 绝比较。

随机化版本
解答

4858.com 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

先行队列的调用示例

1个优先队列的用例

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))。

起码实现

4858.com 46

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

解答

据他们说书本给出的命题 G 和命题 H(汉语版 P173/176,英文版 P275/279),
正如次数的下限 C(N) = 1/2 * NlgN
N 和 lgN 都是乏味递增且超过零的(N>1),由此 C(N) 也是干Baba递增的

 

堆的概念

在二叉堆数组中,每个成分都要有限帮衬大于等于另七个特定岗位的要素。相应地,这几个岗位成分又至少超过等于数组中另四个元素。
堆有序:一棵二叉树的每种结点都高于等于它的八个子结点,根结点是堆有序的二叉树中的最大结点。

2.2.8

二叉堆表示法

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

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

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

4858.com 47

堆的代表

一棵大小为 N 的通通二叉树的冲天为 $\lfloor logN\rfloor$

题目

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

堆的算法

堆完成的比较和沟通方法:

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

修改后的算法对已经稳步的情况做了优化
数组对半切分并排序后,
如果 a[mid] < a[mid +
1](左半片段的最后2个元素小于右半部分的首先个因素)
那么大家得以平昔统一数组,不供给再做多余的操作

后日的输入是3个已经排序的数组
算法唯一的比较产生在认清 a[mid] < a[mid + 1] 那一个标准时
借使数组有 N 个因素
比较次数满意 T(N) = 2 * T(N / 2) + 1, T(1) = 0
倒车为非递归情势即为:T(N) = cN / 2 + N – 1
里头 c 为私行正整数

 

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

若堆的有事态因有些节点变得比它的父节点更大而被打破,则需通过调换它和它的父节点来修复堆。沟通后,该节点比它的七个子节点都大。重复该进度,直到遇见更大的父节点。

4858.com 48

上浮

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

2.2.9

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

若堆的平稳状态因某些节点比它的两个子节点或内部之一更小而被打破,则可因而将它和它的几个子节点较大者交换成平复堆。重复该进度,直到它的子节点都比它更小或到达了堆的最底层。

4858.com 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;
    }
}

插入成分:将新成分加到数组末尾,扩张堆的深浅并让该新成分上浮到合适岗位。

4858.com 50

布署成分

除去最大因素:从数组顶端删去最大的要素并将数组的结尾贰个要素放到顶端,减小堆的轻重并让那些成分下沉到适当岗位。

4858.com 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+一次相比较,剔除最大因素操作急需不超过 2lgN 次相比较。

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

题目

在库函数中使用 aux[] 那样的静态数组时不妥贴的,
因为大概会有五个程序同时利用那么些类。
金玉满堂三个不要静态数组的 Merge 类,
但也无须将 aux[] 变为 merge() 的片段变量(请见本书的答复部分)。
升迁:能够将扶助数组作为参数字传送递给递归的 sort() 方法。

多叉堆

一心三叉堆:对于数组中1至 N 的 N 个因素,地方 k 的节点大于等于位于
3k-一 、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);
}

下一场建立2个私有的递归 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遍插入排序,用堆达成获得堆排序。堆排序分五个阶段:

  • 堆的布局:将原始数组重新协会计划进2个堆中。
  • 下沉排序:从堆中按递减顺序取出全部因素并收获排序结果。

2.2.10

堆的构造

总是向优先队列插入成分可行,但更敏捷的办法是从右到左用 sink()
函数构造子堆。数组各个岗位都早正是1个子堆的根节点了,sink()
对于这个子堆也适用。若贰个节点的四个子节点都早正是堆了,则在该节点上调用
sink()
可将它们变成三个堆。开始时只需扫描数组中5/10元素,因为能够跳过大小为1的子堆。最后在地方1上调用
sink()
方法,扫描结束。在排序第三阶段,堆的构造方法和我们不知不觉想象的不如,因为我们指标是结构3个堆有序的数组并使最大因素位于数组的始发(次大的成分在隔壁)而非构造函数结束的结尾。

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

题目

快快归并。
落实2个 merge() 方法,按降序将 a[] 的后半部分复制到 aux[],
下一场将其归并回 a[]
中。那样就能够去掉内循环中检查和测试某半边是还是不是用尽的代码。
留神:那样的排序发生的结果是不稳定的(请见 2.5.1.8 节)。

下沉排序

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

4858.com 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
次相比(以及百分之四18遍数的置换),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 1963年发现能够通过免去反省成分是还是不是到达正确地点来节省时间。在下沉中三番五次间接晋级较大的子节点直至到达堆底,然后再使成分上浮到科学地点,那样能够将比较次数收缩3/6——接近了归并排序所需比较次数(随机数组)。该措施需额外层空间中,由此实际应用中唯有当比较操作代价比较高时才用(例如:将字符串或任何键值较长类型的因素排序时)。

堆排序在排序复杂性研讨中有根本地位,因为它是唯一能同时最优地利用空间和岁月的艺术——最坏情形下能保障使用
~2NlgN
次相比和定位的附加空间。当空间充裕忐忑时(如嵌入式系统或低本钱移动设备)很盛行,因为它只用几行就能兑现较好的性质(甚至机器码也是)。但现代系统很少用,因为它手足无措利用缓存。数组成分很少和附近的别样元素比较,由此缓存未命中的次数要远不止大多数相比较都在隔壁成分间展开的算法,如快排、归并排序、甚至是希尔排序。

在大数据量下,要拍卖 TopK 和 Multiway
难点,不能排序(或不可能全装进内部存储器),如 10 亿因素中选最大 十一个,则只用1个能积存十三个要素的队列即可。

代码
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
字段,排序时一旦数总裁度小于它则一贯调用插入排序进行排序。

在调用归并措施前判断第二个有序数组的末段3个成分是不是高于第一个有序数组的首先个因素,
只要抢先的话就不需要调用归并了,直接首尾相接即可。

每一趟归并都急需八个数组,3个用来存放归并结果,这几个数组中的内容是开玩笑的;
另叁个则保留了归并前的数组,用于实际的合并进程。
归并终止后,前二个数组变成归并后的稳步结果(也便是下1回归并时的「归并前数组」),后叁个数组中的内容则不再实用。
我们得以观看那三个数组的剧中人物在下一回归并时刚好可以交流。

要留意的是,归并次数连续3个奇数(左侧归并+左边归并+总归并),因而在首先次调用
Sort 方法时应当把 aux 和 a 交流传入。

不可变的键

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

代码
using System;

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

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

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

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

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

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

 

降价的调换

选拔引用另3个便宜是足以不必移动整个因素。对于成分大而键小的数组来说节约是宏伟的,因为正如只需访问成分一小部分,而排序进程大多数要素都不会被访问到。对于大概任意大小的成分,引用在相似情况下交换开销和相比花费大约同样(代价是供给额外层空间间存款和储蓄引用)。

2.2.12

种种排序方法

Java 的 Comparator 接口允许在多个类中落到实处八种排序方法。它只有1个
compare() 方法来比较三个指标,用 Comparator
接口代替Comparable接口能够将数据类型定义和八个该数据类型的可比的定义区分开。例如
Insertion.sort(a, String.CASE_INSENSITIVE_ORDER),对 Transaction
对象数组按时间排序
Insertion.sort(a, new Transaction.WhenOrder()),按金额排序
Insertion.sort(a, new Transaction.HowMuchOrder()) 等。sort()
方法每一遍都会回调 Transaction 类中的用例内定的 compare()
方法,为幸免每趟排序都创建新的 Comparator 对象,使用 public final
来定义那么些相比较器(就如使用 String.CASE_INSENSITIVE_ORDER 一样)

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

次线性的额外层空间间。用大小 M 的数组分为 N/M 块(简单起见,设 M 是 N
的约数)。
贯彻二个集合措施,使之所需的附加空间压缩到 max(M, N/M):
(i)能够先将1个块看作一个因素,将块的首先个因素作为块的主键,用选择排序将块排序;
(ii)遍历数组,将率先块和第叁块归并,达成后将第叁块和第一块归并,等等。

采用比较器完结优先队列
  • 为 马克斯PQ 添加三个实例变量 comparator
    以及一个构造函数,该构造函数接受二个比较器作为参数并用它将
    comparator 起头化。
  • 在 less() 中检查 comparator 属性是还是不是为 null(假使不是就用它相比较)

应用了 Comparator 的插入排序:

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

汉语版的翻译相比较难精晓
实质上就是另一种归并排序的贯彻格局
先把数组分成若干个大大小小为 M 的块
对此每个块,用选取排序进行排序
进而遍历数组,将逐条块归并起来

稳定性

若一个排序算法能保存数组中再一次成分的周旋地方则可被叫作稳定的。一部分算法是安静的——插入排序和合并排序,但选拔排序、希尔排序、火速排序和堆排序不稳定。

代码
using System;
using Merge;

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

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

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

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

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

 

该用哪个种类排序

4858.com 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
多个数排序的决策树如下,结点代表对比对应地方上的数。
4858.com 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) 代表有 k 个叶子节点的平衡决策树的享有途径长度之和
上例中 H(6) = 2 + 2 + 3 + 3 + 3 + 3 = 16
出于平衡决策树的质量,H(k) = 2H(k / 2) + k
(加上 k 的原故:左右子树的万丈比任何树的万丈小
1,因而每条途径的长度都必须加 1,总共多加了 k 次)
因此 H(k) = klogk
现在令 k = n!
H(n!) = n!log(n!)
是因为每便排序时大家只经过某一条途径(上例中大家只透过了右、左、左那条路线)
并且各种途径的面世可能率相等
故此平均相比次数应当为 H(n!) / n! = log(n!) = nlog(n)
声明完成

 

排名

逆序对数难点

2.2.14

中位数与各种总结

二个和排序有关但又不须求完全的要紧应用正是找出一组成分的中位数,有一种尤其选择:找到一组数中第
k 小的成分。通过前边的 TopM 难点用事先队列能够化解,大概排序后取得第 k
个要素也得以解决,但都以线性对数时间。实际上,当 k
十分小或相当的大时方可在线性时间找到:

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

不止切分知道子数组只包蕴第 k 个要素,此时 a[k]
含有纤维的(k+1)个因素,a[0] 到 a[k-1] 都小于等于 a[k],而
a[k+1] 及其后的要素都超出等于
a[k]。假使每回都碰巧将数组二分,则比较总次数是(N+N/2+N/4+…)直到找到第
k 个因素,遵照等比数列求和公式该和鲜明低于 2N。

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

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

以下是可供参考的博客:
各个排序算法时间复杂度
面试中的排序算法总计
八大排序算法
总得明白的八大种排序算法【java实现】
坐在马桶上看算法:急迅排序

题目

归并一如既往的队列。
编辑2个静态方法,将多个静止的队列作为参数,再次来到贰个集合后的雷打不动队列。

解答

相比五个静止队列的首个成分,取较小的3个出队并放入额外建立的行列中。
重新上述手续直到八个类别都为空。

代码
/// <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 个类别,每一个队列包括个中八个因素。
创制1个由那 N 个类别组成的行列,然后不断用练习 2.2.14中的方法将队列的头四个成分归并,
并将结果重新参预到行列结尾,直到队列的种类只剩余1个因素停止。

解答

先后思路标题已经交由,依照题意完结即可。
Merge 方法能够直接采取前一题的贯彻。

代码
using System;

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

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

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

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

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

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

            return sortedQueue;
        }
    }
}

 

2.2.16

题目

当然的联合排序。
编写3个自底向上的统一排序,当须要将七个子数组排序时能够使用数组中早就平稳的一部分。
先是找到一个不变的子数组(移动指针直到近日因素比上2个要素小停止),
下一场再找出另叁个并将它们归并。
基于数组大小和数组中递增子数组的最大尺寸分析算法的周转时刻。

解答

自然归并排序的二个示范如下图所示:

4858.com 55
主干历程和自底向上的统一排序类似,只是每一次归并的块大小不肯定相同。

时光分析

4858.com 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 十三分近乎,不再赘言,这里介绍一下归并方法。
4858.com 57
如 gif
图所示,先把要合并的七个链表拆出来,随后鲜明表头地方,然后开始展览统一即可。
归并终止后回去 first。

结果分析如下图所示:
4858.com 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

题目

直接排序。
编排三个不更改数组的会见排序,
它回到3个 int[] 数组 perm,其中 perm[i] 的值是原数组中第 i
小的要素的职位。

解答

合法完毕:

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

代码
using System;
using Merge;

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

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

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

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

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

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

 

2.2.21

题目

一式三份。
加以七个列表,每一个列表中隐含 N 个名字,
编纂一个线性对数级其余算法来判定三分列表中是不是包括公共的名字,
假使有,重回第二个被找到的这种名字。

解答

对三份列表进行归并排序(O(nlogn)),随后遍历三遍个中的一份表,
用二分查找检查在其他四个表中是还是不是存在同样的姓名(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

题目

三向归并排序。
假诺每便大家是把数组分成多少个部分而不是八个部分并将它们分别排序。
接下来实行三向归并。
那种算法的运作时刻的拉长数据级是稍稍。

解答

4858.com 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 所实现的联结排序之间的品质。
依照经验给出应该在几时为子数组切换来插入排序。

解答

4858.com 60
阈值合适时,大概会有1/10的性质提高。
阈值在 10 以下都以相比确切的。

代码
using System;
using Merge;

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

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

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

 

2.2.24

题目

立异的稳步测试。
在尝试中用大型随机数组评估演练 2.2.8 所做的改动的功力。
基于经验用 N(被排序的原始数组的轻重)的函数描述条件语句(a[mid] <=
a[mid + 1])创设(无论数组是还是不是有序)的次数。

解答

4858.com 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 的取值无关重要,实验也表达了那或多或少。
4858.com 62
算法大概能够分为以下多少个步骤
率先将数组划为 k 份,用七个数组 mids 记录那 k 个子数组的划分地方
随之递归的调用 Sort 方法,将那 k 个子数组排序
随后将那 k 个子数组归并,
老是归并时遍历取 k 个子数组中值最小的贰个,然后对应子数组的提醒器 + 1
上边这一步是 O(k) 的,能够用堆只怕败者树优化为对数级别

代码
using System;
using System.Diagnostics;

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

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

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

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

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

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

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

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

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

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

 

2.2.26

题目

创制数组。使用 SortCompare 粗略相比较在你的微型总计机上在 merge() 仲春在
sort() 中成立 aux[] 的性质差别。

解答

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

4858.com 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
(某次归并时三个子数组的尺寸之和)的函数推测当二个子数组用尽时另3个子数组的平均长度。

解答

粗粗上会是3个对数函数,用 Excel 做了回顾的拟合。
4858.com 64

代码
using System;
using Merge;

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

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

 

2.2.28

题目

自顶向下和自底向上。
对于 N=10^3、10^4、10^5 和 10^6,
动用 SortCompare 相比自顶向下和自底向上的联结排序的天性。

解答

自底向上会快一些,省去了递归进度中等高校函授数重复调用的时间。
4858.com 65

代码
using System;
using Merge;

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

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

 

2.2.29

题目

本来的合并排序。对于 N=10^③ 、10^6 和 10^9,类型为 Long
的轻易主键数组,遵照经验给出自然的集合排序(请见练习2.2.16)所急需的遍数。
唤醒:不供给达成那几个排序(甚至不必要变更全数完整的 60人主键)也能不负众望这道演习。

解答

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

发表评论

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

网站地图xml地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有