写在前面

一切项目都托管在了 Github
上:

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

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

善用 Ctrl + F 查找难点。

一 起码排序算法

排序算法关切的重如若重新排列数组成分,个中各类成分都有三个主键。排序算法是将具有因素主键按某种方式排列(平时是依照轻重缓急也许字母顺序)。排序后索引较大的主键大于等于索引较小的主键。

参考资料

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

 

Q:什么是归并排序?
A:它是起家在集合操作上的一种有效的排序算法;是行使分治法的八个十分杰出的使用;是1种祥和的

习题&题解

排序算法类的沙盘

public class Example{
    public static void sort(Comparable a[]){}
    private static boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){
        for(int i = 0;  i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static boolean isSort(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        //从标准输入读入字符串,排序后输出
        Integer[] a = new Integer[]{1,34,55,66,7};
        sort(a);
        assert isSort(a);
        show(a);
    }
}
  • 排序费用模型:商量排序算法时,需求计算正如和置换的次数。对于不交流成分的算法,总计访问数组的次数
  • 额外内部存款和储蓄器使用:排序算法的附加内部存款和储蓄器开支和平运动行时刻同1首要。排序算法可分两类:除了函数调用所需的栈和固定数目标实例变量之外无需额外内部存款和储蓄器的原地排序算法,以及供给外加内部存款和储蓄器空间来储存另1份数组副本的其它排序算法。
  • 数据类型:上述排序算法模板适用于此外完成了Comparable接口的数据类型。例如,Java中封装的Integer和Double,以及String和任何不少尖端数据类型(如File和U本田UR-VL)都达成了Comparable接口,因而能够平素调用这个品种的数组作为参数调用大家友好完毕的排序方法。

比如说——用快排对N个随机的Double数据开始展览排序:

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

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

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

对此 v < w、v = w 和 v > w
三种情形,Java习惯是在v.compareTo(w)被调用时分别重返3个负整数、零和3个正整数(-一、0和一)。一般的话,若
v 和 w 无法相比或然双方之一是 null,v.compareTo(w) 将会抛出1个不胜。

归并排序的定义

归并排序的落成本身是那样来讲述的:先对个别多少个成分通过两两联合的点子举办排序,形成二个尺寸稍大学一年级部分的静止连串。然后在此基础上,对八个长度稍大学一年级些的有序体系再开始展览两两统1,形成1个尺寸更加大的稳步类别,有序类别的的长短不断增加,直到覆盖任何数组的高低甘休,归并排序就马到功成了。

 

着力思考

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

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

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

2.2.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和检查是或不是代码越界),交流成分的代码写到了内循环之外,每一趟交流都能排定贰个成分,由此调换总次数是N。所以算法总的时间效用取决于相比次数。

  • 长度为 N 的数组,采纳排序须要大致 (N^贰) / 二 次相比较和 N 次交流

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

  • 分选排序有多少个鲜明特点:
  1. 运行时刻和输入无关。为了找出最小成分而扫描一次数组并无法为下一回扫描提供什么音信。那种气象在好几情况下是欠缺,因为二个已经稳步的数组或是主键全体对等的数组和1个成分随机排列的数组所用的排序时间相同长,而别的算法更擅长运用输入的开头状态。
  2. 数据移动最少。每回调换都会转移几个数组成分的值,由此挑选排序用了N次调换——交流次数和数组大小是线性关系,而别的任何算法都不有所那几个特点(超越八分之四增强数据级都以线性对数或平方级别)。

归并排序的二种达成格局:递归和循环

归并排序有二种完结格局:
基于递归的统一排序和依照循环的集合排序
。(也叫自顶向下的联合排序自底向上的合并排序

 

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

 

1.
无论是基于递归照旧循环的统一排序,
它们调用的主干措施都是1致的:达成壹趟合并的算法,即多少个已经逐步的数组连串合并成1个更加大的雷打不动数组类别 
(前提是多个原种类都以照猫画虎的!)

2.
从排序轨迹上看,集合类别的长度都以从小(一个因素)到大(整个数组)增加

 

 

原地归并的空洞方法

Q:为何需求原地归并?
A:因为用归并将一个大数组排序时,须求展开再3归并,而且每一回归并会都创设二个新数组来存款和储蓄排序结果会带来难点。

Q:原地归并促成了怎么样?
A:能够先将前半片段排序,再将后半部分排序,然后数组中移动成分而不必要接纳额外的长空(将三个不变的数组归并为贰个平稳的数组)

Q:如何落到实处归并?
A:创建三个正好大小的数组,然后将多少个输入数组中的成分2个个经年累月方法那几个数组中。

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

    /**
     * 将子数组 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个人。那种算法叫做插入排序

  • 与采取排序1样,当前目录左边全体因素都以严守原地的,但它们最终地点还不明确,为了给更加小成分腾出空间,它们只怕会被移位,但当索引到达数组右端时,数组排序就到位了。
  • 与选择排序差异的是,插入排序所需时日取决于输入凉月素的起来顺序。如对类似平稳的数组排序要比自由数组快很多。

对此自由排列的尺寸为N且主键不另行的数组,平均情形下插入排序必要 ~ N^2
/ 4$ 次相比较以及~N^二 / 4 次交换。最坏情形下要求 ~ N^2 / 二 次相比和 ~N^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;
        }
    }
}

设想壹般景观下部分有序的数组。倒置金沙注册送58 ,指的是数组中五个顺序颠倒的成分。比如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个一成不变的数组,所以得依照原地归并的悬空去落到实处1种递归归并。

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

Q:为啥它能将科学的排序?
A:假若它能将三个子数组排序,那么它就能够透过归并八个子数组来将总体数组排序。

解答

金沙注册送58 1

 

一.叁 希尔排序

希尔排序:是壹种基于插入排序的排序算法。对于大规模乱序数组插入排序相当的慢,因为它只会换换相邻的要素,若最小成分在数组最终,则对其急需活动N-1回。希尔排序创新了插入排序,调换不相邻的成分以对数组的一些进展排序,并最后用插入排序将有个别有序的数组排序。

  • h有序数组:数组中随心所欲间隔为 h 的因素都稳步。即三个 h有序数组
    正是 h
    个相互独立的雷打不动数组编织在一块构成的一个数组。若h十分大,则可将元素移到很远地点,为达成越来越小的h有序创建福利。

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

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

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

Hill排序越来越高速原因是它衡量了子数组的范围和有序性。排序之初,各样子数组都很短,排序之后子数组都以1些有序的,那二种情状都符合插入排序。子数组部分有序的档次取决于递增连串的抉择。

单趟排序的达成分析

 

上边作者先介绍二种分歧归并算法调用的共用艺术,
即完毕单趟归并的算法。(五个已经稳步的数组种类合并成八个更加大的静止数组体系)

 

在早先排序前创办有三个和原数组a长度相同的空的提携数组aux

 

单趟归并的进度如下:

 

一. 
率先将原数组中的待排序种类拷贝进帮助数组的等同地点中,即将a[low…high]拷贝进aux[low…high]中

2.  扶持数组aux的义务有两项:比较元素大小,
并在aux中每一个拿到有序的成分放入原数组a中

(通过一使aux和a在low-high的岗位是完全相同的!那是兑现的功底)

3. 
因为aux[low…high]由两段有序的队列:aux[low…mid]和aux[mid…high]结合,
这里称之为aux壹和aux二,我们要做的正是从aux一和aux二的头顶元素起始,相比双方成分的轻重。将较小的因素放入原数组a中(若a[0]已被占则放在a[1]…依次类推),并取得较小成分的下四个成分,
和另2个行列中较大的要素相比
。因为前提是aux一和aux2都以有序的,所以经过那种艺术我们能博取越来越长的静止类别

4.  若果aux的两段类别中,个中一段中的全部因素都已”相比”完了,
取得另1段系列中多余的要素,全体放入原数组a的剩下地点。

 

经过三和四的达成格局

  • 安装八个游标 i 和 j
    用于“成分相比”
    (在aux中展开):变量,i 和
    j,分别代表左游标和右游标,始发时分别指向aux[low]和aux[mid]
  • 设置游标k用于明确在a中放置成分的职分(在a中进行),k在开首时候指向a[low]
  • 完全上来说i,
    j, k的可行性都以向右移动的

 

经过3和4的图示演说

 

图A

金沙注册送58 2

 

 

 

金沙注册送58 3

组成地方的进程三, 
相比较 i 和 j 当前所指的aux中的成分的大大小小,
取得个中相比较大的百般成分(例如上海体育地方中的i),将其放入数组a中,
此时(在图中假设景况下): i加一,左游标右移。  同时k也加一,
k游标也向右移动

 

图B

金沙注册送58 4

 

 

金沙注册送58 5

组合地点的进度4,
在 i 和 j 都向右移动的经过中,
在图中倘诺意况下,因为j当前所指的要素(图中地方)大于左半边即a[low…mid]的兼具因素,导致
i 不断加码(右移)且通过了界线(mid),
所以这时候就不须求相比较了,只要把j当前所指地点到high的因素都搬到原数组中,填满原数组中剩下的职位,
单趟归并就完了了, 在那1段进程中 j 延续加一,右游标三番五次右移。 
同时k也总是加一, k游标也总是右移, 直到 j == high且k == high截至

 

依照上边的表达,
计算出单趟归并算法中最要害的四个规格判断意况:

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

 

【注意】在排序之初成立了贰个长度和原数组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);     // 归并结果
    }
题目

遵守算法 贰.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++];
        }
    }
}

上述情势将富有因素复制到1个扶植数组aux[]中,再把归并结果放回原数组a[]中。方法在归并时(第一个for循环)实行了五个判断:左半边用尽(取右半边成分)、右半边用尽(取左半边成分)、左半边的当下成分小于右半边的脚下因素(取左半边成分)以及右半边的如今因素小于左半边的最近成分(取右半边成分)

单趟排序的长河图解

 

为了更详实的讲述单趟排序的长河,上边在上头的图A和图B的功底上交给每一步的图解:

 

作者们要排序的体系是
二 肆 5 玖 一 三 陆 柒, 合并的前提是二 四 5
九 和 一 叁 陆 柒都是一步一趋的

 

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

金沙注册送58 6

 金沙注册送58 7

 

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

金沙注册送58 8

 金沙注册送58 9

 

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

金沙注册送58 10

 金沙注册送58 11

 

恍如上述,
不表明

金沙注册送58 12

金沙注册送58 13

 

 

看似上述,
不表明

金沙注册送58 14

 金沙注册送58 15

 

恍如上述,
不解释

金沙注册送58 16

 金沙注册送58 17

 

类似上述,
不表达

金沙注册送58 18

 

金沙注册送58 19

 

留神, 那那里 j
扩张导致 j> high,  以后的事态是“右半边用尽”,
所以将aux左半边剩余的因素玖放入a剩下的片段a[7]中,
单趟排序完毕

金沙注册送58 20

 

金沙注册送58 21

 

【注意】
下面那一个例子中的连串只是数组的一片段,
并不一定是成套数组

 

 

自个儿在上头介绍过,三种不一样归并算法:
基于递归的统一和依照循环的集合, 
都以以单趟归并的算法为底蕴的。

 

上边先来讲一下依照递归的集合排序(自顶向下的会面排序)

 

质量分析

至上状态:T(n) = O(n)
最差景况:T(n) = O(nlogn)
平均处境:T(n) = O(nlogn)

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

对于长度为 N 的任意数组,自顶向下的会合排序最多供给做客数组 陆NlgN
(2N 次用来复制、二N
次用来将排好序的成分移动重回、其余最多比较 2N 次)。

Q:首要症结是什么样
A:辅助数组所选拔的额外层空间间和 N 的大小成正比。

解答

金沙注册送58 22

 

自顶向下的合并排序

public class Merge extends Example {
    //归并所需辅助数组
    private static Comparable[] aux;
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        //将a[]复制到aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        //注意:比较元素都用aux[]
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        //左半边排序
        sort(a, lo, mid);
        //右半边排序
        sort(a, mid + 1, hi);
        //归并结果
        merge(a, lo, mid, hi);
    }
    public static void main(String[] args) {
        //从标准输入读入字符串,排序后输出
        Integer[] a = new Integer[]{49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
        sort(a);
        assert isSort(a) : "Error Information...";
        show(a);
    }
}
  1. 对此长度为 N 的数组,自顶向下的联合排序须要 二分一NlogN 至 NlogN 次正如
  2. 对于长度为 N 的数组,自顶向下的联合排序最多需求拜访数组 陆NlogN 次

归并排序所需时日和 NlogN 成正比,首要症结是帮忙数组所运用的附加空间和
N 的深浅成正比。

依照递归的会师排序(自顶向下)

 

依照递归的统壹排序又称为自顶向下的联合排序

 

自底向上的统壹排序(安分守纪的解决)

贯彻合并的另一种办法:先归并那多少个微型数组,然后再成对归并得到子数组。首先两两归并,然后44归并,然后捌八归并,一贯下去。

2.2.3

归并立异:
  • 对小圈圈数组使用插入排序。使用插入排序处理小范围的子数组,一般能够将归并排序运转时刻裁减1/10~15%。
  • 测试数组是不是曾经稳步。添加一个判定标准,若 a[mid] <= a[mid + 1]
    则认为数组已经平稳并跳过 merge()
    方法。那一个改变不影响排序的递归调用,但随便有序的子数组算法的运营时刻就变为线性了。
  • 不将成分复制到协助数组。能够省去成分复制到协理数组所用时间(但空间格外),此时需调用二种排序方法,一种从输入数组排序到扶助数组,一种从扶助数组排序到输入数组,技巧是在递归调用的每种层次交流输入数组和救助数组的剧中人物。

递归归并的想念

金沙注册送58 23

 

金沙注册送58 24

 

 

最珍视的是sort(int
a [], int low,int high)方法里面的3行代码:

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

 

各自表示对多数边种类递归、对右半边体系递归、单趟合并操作。

 

全总代码:

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

 

 

测试代码:

 

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

 

 

输出结果

0
1
1
2
3
5
6
7
9

 

 

运行轨道
题目

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

自底向上的联合排序

先归并微型数组,然后再成对归并取得的子数组,直到将全部数组归并到一起,那比标准递归方法所需代码量少。首先是两两归并(每一种元素是高低为一的数组),然后肆四归并(将三个高低为2的数组归并成二个有四个因素的数组),然后是八八归并…

    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,每一次加倍。最终3个子数组大小唯有在数组大小是sz的偶数倍时才也等于sz(否则会比sz小)。

金沙注册送58 25

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

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

  • 当数COO度为2的幂时,自顶向下和自底向上归并排序所用比较和访问次数相同,只是顺序不相同。
  • 自底向上归并排序适合用链表公司数量。此格局只需再一次协会链表连接就能将链表原地排序(不需创造任何新的链表节点)。

用自顶向下或自底向上格局贯彻任何分治算法都很当然。归并排序表达,当能用1种“化整为零”方法消除时方可试试另一种“安份守己”的章程。

递归栈深度和调用顺序

 

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

从上到下,是各类merge的程序调用顺序,壹初叶调用,
一伍末段调用

从右到左,
递归栈由深到浅
,例如 1,二,四,伍的递归深度是一模壹样的,
而3比它们浅1个层次

金沙注册送58 26

 

 

金沙注册送58 27

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

 

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

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

 

 

先是,在第一层递归的时候,先进入的是首先行的sort方法里(A处),然后紧接着又进入了第1层递归的首先行sort方法(A处),
如此继续,由(a,
low,mid)的参数列表可见其递归的动向是直接向左移动的,直到最后一层递归,所以首先执行merge的对象是a[0]和a[1](上海教室编号一),再然后举办的是最后一层递归的第贰行代码(B处),那时候merge的指标是a[2]和a[3](上海教室编号二)。
再接下来,
重回上一层递归,对已经稳步的a[0]、a[1]和a[2]、a[3]展开merge。(上海教室编号叁)如此继续,递归的纵深不断变浅,
直到对整个数组的左右两半进展merge。 (上航海用教室编号3)

 

 

代码完毕

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

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

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

金沙注册送58 28

 

排序算法的复杂度

探究复杂度的第2步是树立几个计量模型。对排序来说,基于相比的算法对数组操作办法是由主键比较决定。

并未别的依照比较的算法能担保使用不难 log(N!) ~ NlogN 次相比较将长度为 N
的数组排序
归并排序是一种渐进最优的根据相比较排序的算法。归并排序在最坏意况下的比较次数和私自基于相比较的排序算法所需的足足相比次数都以
~NogN。

递归归并的轨迹图像

 

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

金沙注册送58 29

 

金沙注册送58 30

 

 

 

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

 

 

金沙注册送58 31

 

金沙注册送58 32

 

 

属性分析

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

当数经理度为 2
的幂
时,自顶向下和自底向上的联合排序所用的相比次数数组访问次数刚刚相同,只是顺序分歧。

自底向上的合并比较吻合用链表组织的数据。

2.2.4

Q&A

  1. 归并排序比希尔排序快呢?
    在实际利用中,它们运转时刻差距在常数级别。
  2. 缘何不把数组 aux[] 声明为 merge() 方法的1部分变量?
    为制止每一趟归并时,就算归并不大的数组都创立1个新数组,不然创设新数组将成为归并排序运转时刻首要部分。更好的不二法门是将
    aux[] 变为 sort() 方法的有的变量,并视作参数字传送给 merge()
    方法。
  3. 当数组中设有双重元素时归并排序品质如何?
    若有所因素相同,则归并排序运营时刻是线性的。若有多少个差异重复值,运转时刻是线性对数的(和全部因素都不另行知足相同循环条件)。

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

 

总结

尚无任何据说相比的算法能够确定保证使用容易 lg(N!) – NlgN 次相比较将长度为
N 的数组排序。

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

题目

是或不是当且仅当多少个输入的子数组都稳步时原地归并的空洞方法才能赢得正确的结果?
表达您的下结论,可能给出贰个反例。

1.5 火速排序

迅猛排序特点包蕴原地排序(只需二个十分小的辅助栈),且将长度为 N
的数组排序所需时日和 NlogN 成正比,内循环比超越二分一排序算法都要短小。

迅猛排序:是一种分治排序算法。将2个数组分成五个子数组,将两部分单独地排序。快排和归并排序是补偿的,归并排序将数组分成七个子数组分别排序,并将逐步的子数组归并以将全数数组排序;快排的排序形式是当多少个子数组都纹丝不动时整个数组也自然有序了。前者的递归调用爆发在处理任何数组此前;后者递归调用发生在拍卖任何数组之后。在归并排序中,叁个数组被等分为两半;在快排中,切分地点取决于数组的内容。

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

高速排序最多需 N^2 / 3回对比,但随着打乱数组能预防那种状态。每一次切分后两子数组之一总是空的图景下比较次数为:N+(N-1)+…+1= N(N+一) / 2,此时日子是平方级别的,空间是线性的。

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

用不一致的办法处理小框框难题能改良大部分递归算法的属性,因为递归会使小圈圈难点中方法调用太过频仍,所以革新对它们的处理形式就能改善整个算法。
因为插入排序卓殊简单
因而1般的话在小数组上比归并排序更加快
那种优化能使归并排序的周转时刻减少百分之10到一5%;

 

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

  if(low>=high) { return; }

 

改成

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

 

就能够了,那样的话,那条语句就持有了八个效用:

 

壹.
在适合时候甘休递归

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

 

 

优化方案

①、直接将支持数组作为参数字传送入,而不直接运用静态数组。
②、对小规模子数组使用插入排序,壹般能够将归并排序的日子缩小 1/10 ~
15%;
③、认清测试数组是还是不是早已平稳,如果 arr[mid] <=
arr[mid+1],咱们就觉得数组已经是寸步不移的并跳过merge()
方法,能够是随意有序的子数组算法的运维时刻变为线性的。
肆、merge()
方法中不将成分复制到协理数组,节省数组复制的小运。调用二种排序方法,一种:将数据从输入数组排序到赞助数组;另一种:将数据从帮忙数组排序到输入数组。
根本:在每一个层次沟通输入数组和提携数组的剧中人物。

解答

不错,须求求八个子数组都维持原状时归并才能博取不错结果。
就算说数组不平稳的话,那么最后只得获得七个数组的名不副实。
合并后的数组中,属于原有数组的因素的对峙顺序不会被改成。
诸如子数组 一 3 1 和 二 捌 5 原地归并。
结果是 一 贰 三 1 8 伍,当中 一 叁 壹 和 贰 8 五 的相对顺序不变。

 

快排革新

  • 切换来插入排序。对于小数组,快排比插入排序慢;因为递归,快排的sort()办法在小数组中也会调用自身。由此在排序小数组时可切换来插入排序——将sort()中的
    if (hi <= lo) return; 改为
    if (hi <= lo + M){Insertion.sort(a, lo, hi); return;},M
    最棒值和种类有关,五~一伍之间平时较好。
  • 3取样切分。使用子数组的一小部分要素的中位数来切分数组,那样切分更加好,代价是需计算中位数。
  • 熵最优的排序。实际选取常常出现含有大批量重新元素的数组,三个要素全体重复的子数组就不须要持续排序了,但之前的算法还会持续切分成越来越小的数组。不难的缓解方法是将数组切分为三有的(详见Dijkstra叁向切分),分别对应小于、等于和超乎切分成分的数组成分,那种比目前二分更扑朔迷离,相关难题有荷兰王国国旗问题。

金沙注册送58 33

三向切分示意图

  1. a[i] 小于 v,将 a[lt] 和 a[i] 交换,将 lt 和 i 加一
  2. a[i] 大于 v,将 a[gt] 和 a[i] 交换,将 gt减一
  3. a[i] 等于 v,将 i 加一

那些操作都会确定保障数组元素不变且减弱 gt-i
的值(这样循环才会终止)。上边是三向切分的切实落到实处:

public class Quick3way{
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo){
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp < 0){
                exch(a, lt++, i++);
            }else if (cmp > 0){
                exch(a, i , gt--);
            }else {
                i++;
            }
            sort(a, lo, lt - 1);
            sort(a, gt + 1, hi);
        }
    }
}

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

优化点二:  测试待排序类别中左右半边是不是已铁板钉钉

 

经过测试待排序体系中左右半边是或不是业已稳步,
在稳步的场地下防止合并方法的调用。

 

譬如对单趟合并,我们对a[low…high]中的a[low…mid]和a[mid…high]展开联合

因为a[low…mid]和a[mid…high]本来正是有序的,存在a[low]<a[low+1]…<a[mid]和a[mid+1]<a[mid+2]…<
a[high]那二种关系,
假如判断出a[mid]<=a[mid+1]的话,
不就足以确定保证从而a[low…high]自作者即是不必要排序的稳步连串了吗?

 

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.5

《算法导论》上的快排

优化点叁:去除原数组种类到助手数组的正片

在地点介绍的依照递归的会合排序的代码中,
大家在每一趟调用merge方法时候,大家都把a对应的行列拷贝到帮忙数组aux中来,即

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

 

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

 

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

 

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

 

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

 

在此地大家做了八个操作:

  • 在排序前拷贝3个和原数组成分完全一样的鼎力相助数组(不再是创立二个空数组了!)
  • 在递归调用的每一个层次交流输入数组和输出数组的剧中人物

 

 

留意,
外部的sort方法和里面sort方法接收的a和aux参数刚好是倒转的

金沙注册送58 34

 金沙注册送58 35

 

诸如此类做的话,
我们就足以去除原数组类别到帮手数组的正片了!

 

但是你可能会问:
骚年, 大家要排序的只是原数组a啊! 你尽管一一点都不小心最终浑然排序的是扶持数组aux而不是原数组a吗?

 

Don’t worry !! 那种状态不会发出
看图:

 

金沙注册送58 36

 金沙注册送58 37

 

由图示易知,
因为表面sort和merge的参数顺序是平等的, 所以,无论递归进度中扶助数组和原数组的剧中人物怎么替换,对最终三遍调用的merge而言(将全方位数组左右半边合为平稳的操作),  
最后被排为有序的都以原数组,而不是支援数组!

 

 

成套代码:

 

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

 

 

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

 

优化测试代码

飞速复制数组的章程】,提示:点击水晶色字体查看方法详情。

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

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

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

    }

}
题目

当输入数组的尺寸 N=3九时,给来自顶向下和自底向上的合并排序中各次归并子数组的轻重及种种。

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

金沙注册送58 38

quicksort普通版本

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

 

据悉循环的联合排序又叫做自底向上的合并排序

 

优化测试结果

在意:优化结果就算大多,不过当其数组接近平稳的时候,速度有了冲天的升官。

相对级别数据量

留神:编写翻译器默许不适用 assert
质量评定(但是junit测试中适用),所以要动用时要丰硕参数虚拟机运转参数-ea
具体添加进度,请参考eclipse 和 IDEA
设置虚拟机运维参数

解答

历次归并子数组的高低和各类如下:

自顶向下

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

自底向上

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

 

快排随机化版本

引入随机性,能够使算法对于拥有的输入都能获取较好的盼望质量。在快排中动用随意取样的随机化技术——从子数组
A[p...r] 中随机选择一个成分作为主元。为此,能够将 A[r] 与从
A[p...r] 中随意选出的一个成分交流来保管主元 x = A[r]
是等可能率地从子数组的 r-p+3个要素中取得的。因为主元是随机选的,期望在平均情形下对输入数组的分开是相比均匀的。

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

循环归并的基本思维

金沙注册送58 39

 金沙注册送58 40

 

 

据他们说循环的代码较为不难,那里就不多废话了

 

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

 

 

2.2.6

快排时间复杂度

  • 最坏境况:
    当划分发生的八个子难点各自包涵了 n-一 个和 0
    个要素时,划分时间复杂度为 O(n),因为对一个轻重缓急为 0
    的数组进行递归调用会直接重回,由此 T(0) =
    O(一),于是算法运营时刻的递归式为:T(n) = T(n-1) + T(0) + O(n) =
    T(n-1)+O(n) = O(n^二)。其余,在输入数组完全有序时,快排时间复杂度仍为
    O(n^贰),而插入排序则为 O(n)。

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

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

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

quicksort递归树

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

循环归并的轨迹图像

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

 

金沙注册送58 41

 

 

金沙注册送58 42

 金沙注册送58 43

 金沙注册送58 44

 

 

题目

编写制定三个主次来计量自顶向下和自底向上的联结排序访问数组的确切次数。
运用这几个顺序将 N=一 至 51二 的结果绘成曲线图,并将其和上限 陆NlgN 相相比。

随机化版本
解答

金沙注册送58 45

藏青是上限,蓝点是自顶向下,红点是自底向上。
是因为二种排序访问数组的次数是1模壹样的,因而蓝点和红点重合。

一.6 优先队列

优先队列帮忙剔除最大因素和插入成分。基于二叉堆的预先队列,是用数组保存成分并遵守一定原则排序,以完成长足地(对数级别)删除最大要素和插入成分。优先队列实际运用包涵模拟系统、任务调度和数值计算等。

由此插入1列成分然后一个个剔除当中的微小成分,就能够用事先队列完结排序算法。堆排序起点于根据堆的预先队列的兑现。

代码

提交绘图部分的代码:

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

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

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

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

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

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

                dataSize *= 2;
            }

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

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

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

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

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

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

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

            graphics.Dispose();
        }
    }
}

 

API

事先队列是一种抽象数据类型,表示了一组值和这几个值的操作。优先队列最根本操作是剔除最大因素和插入元素,

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

2.2.7

事先队列的调用示例

几个先期队列的用例

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

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

起码达成

金沙注册送58 46

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

解答

根据书本给出的命题 G 和命题 H(汉语版 P173/17陆,英文版 P275/27九),
比较次数的下限 C(N) = 二分之一 * NlgN
N 和 lgN 都以干瘪递增且高于零的(N>壹),由此 C(N) 也是单调递增的

 

堆的定义

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

2.2.8

2叉堆表示法

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

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

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

金沙注册送58 47

堆的意味

1棵大小为 N 的一点一滴二叉树的万丈为 $\lfloor logN\rfloor$

题目

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

堆的算法

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

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

修改后的算法对曾经稳步的事态做了优化
数组对半切分并排序后,
如果 a[mid] < a[mid +
1](左半部分的末梢1个因素小于右半部分的率先个要素)
这正是说大家得以一贯统壹数组,不需求再做多余的操作

今昔的输入是贰个一度排序的数组
算法唯1的可比产生在认清 a[mid] < a[mid + 1] 那些原则时
借使数组有 N 个因素
比较次数满意 T(N) = 2 * T(N / 2) + 1, T(1) = 0
转折为非递归方式即为:T(N) = cN / 二 + N – 一
里头 c 为随机正整数

 

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

若堆的有情状因有些节点变得比它的父节点越来越大而被打破,则需通过交换它和它的父节点来修复堆。沟通后,该节点比它的多个子节点都大。重复该进度,直到蒙受越来越大的父节点。

金沙注册送58 48

上浮

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

2.2.9

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

若堆的有序状态因某些节点比它的八个子节点或内部之1更加小而被打破,则可经过将它和它的四个子节点较大者调换到苏醒堆。重复该进程,直到它的子节点都比它更加小或到达了堆的平底。

金沙注册送58 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;
    }
}

计划成分:将新成分加到数组末尾,增添堆的轻重并让该新成分上浮到适当岗位。

金沙注册送58 50

插入成分

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

金沙注册送58 51

去除最大因素

  • 听别人讲堆的预先队列

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

命题:对于三个带有 N
个要素的依照堆的优先队列,布置成分操作只需不当先 lgN+1遍相比,去除最大因素操作内需不超过 贰lgN 次比较。

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

题目

在库函数中运用 aux[] 那样的静态数组时不妥帖的,
因为恐怕会有多少个程序同时接纳这些类。
兑现多少个绝不静态数组的 Merge 类,
但也决不将 aux[] 变为 merge() 的有的变量(请见本书的回应部分)。
提示:可以将支持数组作为参数字传送递给递归的 sort() 方法。

多叉堆

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

解答

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

C#落到实处和合法的贯彻丰盛左近,

首先定义只接受贰个参数的公开 Sort 方法,在那么些主意里面开始化 aux
数组。

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

然后建立一个私有的递归 Sort 方法坚实际的排序操作。

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

添加1个并未有参数的构造函数,在 insert() 中添加将数首席营业官度加倍的代码,在
delMax() 中添加将数COO度减半的代码。

代码
using System;

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

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

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

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

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

 

堆排序

能够把自由优先队列变成一种排序方法,将具备因素插入二个寻觅最小成分的先行队列,然后再另行调用剔除最小成分的操作按梯次删除。用严节数组落成优先队列这么做一定于举办三次插入排序,用堆实现获得堆排序。堆排序分三个阶段:

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

2.2.10

堆的布局

连日向优先队列插入成分可行,但更迅捷的不二等秘书诀是从右到左用 sink()
函数构造子堆。数组每一种地方都早便是3个子堆的根节点了,sink()
对于这一个子堆也适用。若二个节点的多个子节点都早正是堆了,则在该节点上调用
sink()
可将它们变成一个堆。初步时只需扫描数组中拾分之伍要素,因为能够跳过大小为1的子堆。最后在岗位1上调用
sink()
方法,扫描甘休。在排序第二阶段,堆的构造方法和我们不知不觉想象的例外,因为大家目的是组织2个堆有序的数组并使最大因素位于数组的开端(次大的成分在紧邻)而非构造函数停止的最终。

用下沉操作由 N 个要素构造堆只需少于 2N 次相比较以及个别 N 次沟通

题目

赶快归并。
兑现八个 merge() 方法,按降序将 a[] 的后半片段复制到 aux[],
然后将其归并回 a[]
中。那样就足以去掉内循环中检验某半边是还是不是用尽的代码。
注意:那样的排序发生的结果是不安静的(请见 贰.5.一.八 节)。

下沉排序

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

金沙注册送58 52

堆的结构和下沉排序

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

将N个成分排序,堆排序只需少于 二NlgN+二N
次相比(以及5/10次数的置换),贰N 项来自于堆的协会,二NlgN
源于于每一遍下沉操作最大可能需求 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 一9六一年发现能够通过免去反省成分是不是到达正确地点来节省时间。在下沉中接贰连三直接进步较大的子节点直至到达堆底,然后再使成分上浮到正确地点,那样可以将相比次数缩小2/四——接近了归并排序所需比较次数(随机数组)。该格局需额外层空间中,因而实际使用中唯有当相比较操作代价相比高时才用(例如:将字符串或任何键值较长类型的因素排序时)。

堆排序在排序复杂性切磋中有首要地点,因为它是唯一能同时最优地利用空间和岁月的方法——最坏意况下能担保使用
~二NlgN
次比较和一贯的额外层空间间。当空间卓殊紧张时(如嵌入式系统或低本钱移动设备)很红,因为它只用几行就能促成较好的特性(甚至机器码也是)。但现代种类很少用,因为它没辙使用缓存。数组成分很少和周围的别的成分比较,因而缓存未命中的次数要远超出当先51%相比较都在紧邻成分间开始展览的算法,如快排、归并排序、甚至是希尔排序。

在大数据量下,要处理 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++;
                }
            }
        }
    }
}

 

一.柒 排序算法和先期队列的使用

2.2.11

将各类数码排序

后边达成的排序对象是由达成了Comparable接口的目的组成的数组,那样可以使用
Java 的回调机制将随意实现了
Comparable接口的数据类型排序。达成Comparable接口只需定义3个compareTo()函数并在里头定义该数据类型的分寸关系。Java
中的 String、Integer、Double、File 和 URL都完毕了Comparable接口。

题目

改进。
贯彻 二.二.二 节所述的对归并排序的叁项改正:
加速小数组的排序速度,
检验数组是还是不是早已平稳以及通过在递归中交流参数来防止复制。

指南针排序

前边使用的方法被喻为指南针排序,因为只处理元素的引用而不移步数据作者。在C/C++中,须求明显建议操作的是数码大概指向数据的指针,在
Java
中,指针的操作是隐式的。除了原有数字类型外,操作的连天数据的引用(指针)而非数据本身。

解答

官方实现见:

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

在调用归并措施前判断第叁个有序数组的末尾二个成分是或不是超过第3个有序数组的首先个因素,
万一超越的话就不须求调用归并了,直接首尾相接即可。

历次归并都需求四个数组,一个用以存放归并结果,那么些数组中的内容是微不足道的;
另1个则保留了归并前的数组,用于实际的联合进程。
归并甘休后,前三个数组变成归并后的有序结果(也正是下1次归并时的「归并前数组」),后三个数组中的内容则不再灵光。
大家得以见见那七个数组的角色在下二遍归并时刚好能够调换。

要小心的是,归并次数延续二个奇数(左侧归并+左边归并+总归并),由此在率先次调用
Sort 方法时应有把 aux 和 a 调换传入。

不可变的键

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

代码
using System;

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

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

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

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

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

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

 

优惠的置换

应用引用另二个利益是可以不要移动整个因素。对于成分大而键小的数组来说节约是巨大的,因为比较只需访问成分一小部分,而排序进程半数以上要素都不会被访问到。对于差不离任意大小的因素,引用在相似情况下沟通开销和比较花费大致如出1辙(代价是内需额外层空间间存款和储蓄引用)。

2.2.12

四种排序方法

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

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

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

应用相比较器达成优先队列
  • 为 马克斯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;
        }
    }
}
解答

普通话版的翻译比较难掌握
实际正是另1种归并排序的完成格局
先把数组分成若干个大大小小为 M 的块
对此每一个块,用采用排序进行排序
紧接着遍历数组,将逐条块归并起来

稳定性

若一个排序算法能保留数组中再度成分的周旋地方则可被叫做稳定的。1部分算法是平稳的——插入排序和归并排序,但挑选排序、希尔排序、急迅排序和堆排序不稳定。

代码
using System;
using Merge;

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

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

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

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

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

 

该用哪一种排序

金沙注册送58 53

各类排序算法的属性特点

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

2.2.13

题材规约

在动用化解难题 B 的点子来消除难点 A 时,都在将 A 规约为 B。

题目

平均情况的下限。请表达自由基于比较的排序算法的料想比较次数至少为
~NlogN(如若输入成分的具有排列的产出概率是均等的)。
唤醒:相比次数至少是比较树的表面路径的长度(根结点到叶子结点的路子长度之和),当树平衡时该值最小。

找出重新成分

在1个 Comparable
对象的数组中是还是不是留存双重成分?有微微重复元素?哪个值出现最频仍?

透过两两相比能够在平方级别化解,但因此排序可在线性对数时间内消除。

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

1旦对多个数举行排序,这些数是:35,10,一柒
多个数排序的决策树如下,结点代表比较对应地方上的数。
金沙注册送58 54
对此 35,10,一7 来说,路径服从右、左、左,最终获得的结果正是 贰 3
1(10,一柒,35)。
咱俩得以发现决策树上的每三个纸牌节点都表示壹种排列顺序,对于 N
个数,叶子节点就有 N! 个
根据二叉树的习性,高度为 h 的2叉树最多有 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 / 二) + k
(加上 k 的来由:左右子树的可观比壹切树的冲天小
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/二+N/肆+…)直到找到第
k 个因素,依照等比数列求和公式该和明朗低于 二N。

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

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

以下是可供参考的博客:
各个排序算法时间复杂度
面试中的排序算法总计
8大排序算法
非得知道的8大种排序算法【java落成】
坐在马桶上看算法:火速排序

题目

归并壹如既往的体系。
编纂1个静态方法,将五个静止的行列作为参数,再次来到一个联合后的平稳队列。

解答

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

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

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

    return sortedQueue;
}

 

2.2.15

题目

自底向上的不变队列归并排序。
用上面包车型客车格局编写多少个自底向上的联合排序:
给定 N 个要素,创设 N 个系列,每种队列包罗当中一个因素。
始建3个由那 N 个种类组成的连串,然后不断用演习 2.二.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

题目

自然的统壹排序。
编纂1个自底向上的联结排序,当须要将多个子数组排序时能够运用数组中早就平稳的①些。
先是找到1个不变的子数组(移动指针直到当前成分比上2个要素小结束),
然后再找出另3个并将它们归并。
依照数组大小和数组中递增子数组的最大尺寸分析算法的运作时刻。

解答

本来归并排序的3个示范如下图所示:

金沙注册送58 55
骨干进度和自底向上的合并排序类似,只是每一趟归并的块大小不肯定相同。

岁月分析

金沙注册送58 56

随着有序块的变大,排序耗费时间会减少,但拉长的数据级会变高(归并的平均块大小变大了)。

代码
using System;
using System.Diagnostics;

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

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

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

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

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

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

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

 

2.2.17

题目

链表排序。
完成对链表的当然排序
(那是将链表排序的最棒措施,因为它不供给额外的空中且运维时刻是线性对数级别的)。

解答

排序格局和 2.二.16 拾分好像,不再赘言,那里介绍一下归并方法。
金沙注册送58 57
如 gif
图所示,先把要合并的三个链表拆出来,随后鲜明表头地方,然后实行统一即可。
归并终止后归来 first。

结果分析如下图所示:
金沙注册送58 58
乘势有序部分的增多,对于同样大小的数组自然归并排序的耗费时间会浓缩。
对于有序部分雷同的场合,随着数组大小的倍增,耗费时间显示了O(nlogn)的趋势。

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

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

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

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

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

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

                if (mid.next == null)
                    break;

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

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

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

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

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

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

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

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

            first = current;

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

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

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

            return first;
        }

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

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

 

2.2.18

题目

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

解答

能够在用归并排序的主意做。
将归并时取两边较小的成分改为随机取一侧的值,即可达成打乱的效应。
算法的辨析和1般性归并排序一致,满足标题供给。

代码

分治法打乱链表的兑现。

using System;

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

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

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

                if (mid.next == null)
                    break;

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


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

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

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

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

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

            first = current;

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

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

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

            return result;
        }

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

            return hi;
        }
    }
}

 

2.2.19

题目

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

解答

法定完毕:

骨子里假设在归并排序的时候总计 Less(aux[j], aux[i])
满意的次数即可,那几个次数便是大家要的值。

代码
using System;
using Merge;

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

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

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

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

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

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

 

2.2.20

题目

间接排序。
编写制定贰个不转移数组的合并排序,
它回到贰个 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 个名字,
编写3个线性对数级别的算法来判定三分列表中是或不是带有公共的名字,
假如有,重返第3个被找到的那种名字。

解答

对3份列表进行归并排序(O(nlogn)),随后遍历3遍当中的一份表,
用二分查找检查在任何五个表中是不是留存一样的全名(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

题目

三向归并排序。
如果每回大家是把数组分成八个部分而不是八个部分并将它们各自动排档序。
下一场开展三向归并。
那种算法的运维时刻的滋长数量级是稍稍。

解答

金沙注册送58 59
增加数据级为O(nlogn)。

代码
using System;
using System.Diagnostics;

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

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

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

        /// <summary>
        /// 返回两个元素中较小的那个。
        /// </summary>
        /// <typeparam name="T">比较的元素类型。</typeparam>
        /// <param name="a">用于比较的元素。</param>
        /// <param name="b">用于比较的元素。</param>
        /// <returns>较小的元素。</returns>
        private T Min<T>(T a, T b) where T : IComparable<T>
        {
            if (Less(a, b))
                return a;
            return b;
        }

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

            int i = lo, j = lmid + 1, k = rmid + 1;
            for (int l = lo; l <= hi; l++)
            {
                int flag = 0;
                if (i > lmid)
                    flag += 1;
                if (j > rmid)
                    flag += 10;
                if (k > hi)
                    flag += 100;
                switch (flag)
                {
                    case 0:         // 三个数组都还没有取完
                        T min = Min(aux[i], Min(aux[j], aux[k]));
                        if (min.Equals(aux[i]))
                            a[l] = aux[i++];
                        else if (min.Equals(aux[j]))
                            a[l] = aux[j++];
                        else
                            a[l] = aux[k++];
                        break;
                    case 1:         // 只有第一个数组取完了
                        if (Less(aux[j], aux[k]))
                            a[l] = aux[j++];
                        else
                            a[l] = aux[k++];

                        break;
                    case 10:        // 只有第二个数组取完了
                        if (Less(aux[i], aux[k]))
                            a[l] = aux[i++];
                        else
                            a[l] = aux[k++];
                        break;
                    case 100:       // 只有第三个数组取完了
                        if (Less(aux[i], aux[j]))
                            a[l] = aux[i++];
                        else
                            a[l] = aux[j++];
                        break;
                    case 11:        // 第一、二个数组取完了
                        a[l] = aux[k++];
                        break;
                    case 101:       // 第一、三个数组取完了
                        a[l] = aux[j++];
                        break;
                    case 110:       // 第二、三个数组取完了
                        a[l] = aux[i++];
                        break;
                }
            }
        }
    }
}

 

2.2.23

题目

改进。
用试验评估正文中所提到的合并排序的三项改革(请见演练 二.二.1一)的机能,
并比较正文中贯彻的联合排序和演习 贰.二.十 所完毕的联结排序之间的属性。
基于经验给出应该在曾几何时为子数组切换来插入排序。

解答

金沙注册送58 60
阈值合适时,大概会有一成的质量提高。
阈值在 十 以下都是相比较安妥的。

代码
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.捌 所做的改动的功用。
依照经验用 N(被排序的原始数组的轻重缓急)的函数描述条件语句(a[mid] <=
a[mid + 1])创立(无论数组是或不是有序)的次数。

解答

金沙注册送58 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 的取值无关主要,实验也验证了那或多或少。
金沙注册送58 62
算法大概可以分成以下多少个步骤
第三将数组划为 k 份,用二个数组 mids 记录那 k 个子数组的剪切地方
随即递归的调用 Sort 方法,将那 k 个子数组排序
跟着将那 k 个子数组归并,
每便归并时遍历取 k 个子数组中值最小的八个,然后对应子数组的提醒器 + 一
上面这一步是 O(k) 的,能够用堆或然败者树优化为对数级别

代码
using System;
using System.Diagnostics;

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

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

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

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

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

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

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

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

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

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

 

2.2.26

题目

创制数组。使用 SortCompare 粗略比较在您的总结机上在 merge() 阳春在
sort() 中开创 aux[] 的属性差异。

解答

差别还是相比较掌握的,由于 Merge 会调用多次,而用于运行递归的 Sort
方法只会调用贰次。

金沙注册送58 63

代码
using System;
using Merge;

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

        }
    }
}

 

2.2.27

题目

子数主任度。
用归并将重型随机数组排序,
依照经验用 N
(某次归并时三个子数组的长度之和)的函数猜测当二个子数组用尽时另三个子数组的平分长度。

解答

大概上会是四个对数函数,用 Excel 做了简约的拟合。
金沙注册送58 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 相比自顶向下和自底向上的集合排序的习性。

解答

自底向上会快一些,省去了递归进度中等高校函授数重复调用的时辰。
金沙注册送58 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^三、十^陆 和 拾^玖,类型为 Long
的轻易主键数组,遵照经验给出自然的会见排序(请见练习贰.二.16)所须要的遍数。
唤醒:不须求达成那个排序(甚至不须要变更全数完整的 613个人主键)也能一气浑成那道练习。

解答

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

相关文章

网站地图xml地图