【算法】归并排序算法的编码和优化

参考资料

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

归并排序的概念

归并排序的实现我是这样来描述的:先对少数几个元素通过两两合并的方式进行排序,形成一个长度稍大一些的有序序列。然后在此基础上,对两个长度稍大一些的有序序列再进行两两合并,形成一个长度更大的有序序列,有序序列的的长度不断增长,直到覆盖整个数组的大小为止,归并排序就完成了。

归并排序的两种实现方式:递归和循环

归并排序有两种实现方式: 基于递归的归并排序和基于循环的归并排序。(也叫自顶向下的归并排序自底向上的归并排序

这两种归并算法虽然实现方式不同,但还是有共同之处的:

1. 无论是基于递归还是循环的归并排序, 它们调用的核心方法都是相同的:完成一趟合并的算法,即两个已经有序的数组序列合并成一个更大的有序数组序列  (前提是两个原序列都是有序的!)

2. 从排序轨迹上看,合并序列的长度都是从小(一个元素)到大(整个数组)增长

单趟归并算法

单趟排序的实现分析

下面我先介绍两种不同归并算法调用的公共方法, 即完成单趟归并的算法。(两个已经有序的数组序列合并成一个更大的有序数组序列)

在开始排序前创建有一个和原数组a长度相同的空的辅助数组aux

单趟归并的过程如下:

1.  首先将原数组中的待排序序列拷贝进辅助数组的相同位置中,即将a[low...high]拷贝进aux[low...high]中

2.  辅助数组aux的任务有两项:比较元素大小, 并在aux中逐个取得有序的元素放入原数组a中 (通过1使aux和a在low-high的位置是完全相同的!这是实现的基础)

3.  因为aux[low...high]由两段有序的序列:aux[low...mid]和aux[mid...high]组成, 这里称之为aux1和aux2,我们要做的就是从aux1和aux2的头部元素开始,比较双方元素的大小。将较小的元素放入原数组a中(若a[0]已被占则放在a[1]...依次类推),并取得较小元素的下一个元素, 和另一个序列中较大的元素比较。因为前提是aux1和aux2都是有序的,所以通过这种方法我们能得到更长的有序序列

4.  如果aux的两段序列中,其中一段中的所有元素都已"比较"完了, 取得另一段序列中剩下的元素,全部放入原数组a的剩余位置。

过程3和4的实现方法

  • 设置两个游标 i 和 j 用于“元素比较” (在aux中进行):变量,i 和 j,分别代表左游标和右游标,开始时分别指向aux[low]和aux[mid]
  • 设置游标k用于确定在a中放置元素的位置(在a中进行),k在开始时候指向a[low]
  • 总体上来说i, j, k的趋势都是向右移动的

过程3和4的图示解说

图A

结合上面的过程3,  比较 i 和 j 当前所指的aux中的元素的大小, 取得其中比较大的那个元素(例如上图中的i),将其放入数组a中, 此时(在图中假设情况下): i加1,左游标右移。  同时k也加1, k游标也向右移动

图B

结合上面的过程4, 在 i 和 j 都向右移动的过程中, 在图中假设情况下,因为j当前所指的元素(图中位置)大于左半边即a[low...mid]的所有元素,导致 i 不断增加(右移)且越过了边界(mid), 所以这时候就不需要比较了,只要把j当前所指位置到high的元素都搬到原数组中,填满原数组中剩下的位置, 单趟归并就完成了, 在这一段过程中 j 连续加1,右游标连续右移。  同时k也连续加1, k游标也连续右移, 直到 j == high且k == high为止

基于上面的表述, 总结出单趟归并算法中最关键的4个条件判断情形:

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

单趟排序算法的代码

有了上面的解释,写这个算法就不难了吧

/**
   * @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,这部分代码上文未给出

单趟排序的过程图解

为了更详细的描述单趟排序的过程,下面在上面的图A和图B的基础上给出每一步的图解:

我们要排序的序列是 2 4 5 9 1 3 6 7, 合并的前提是2 4 5 9 和 1 3 6 7都是有序的

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

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

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

类似以上, 不解释

类似以上, 不解释

类似以上, 不解释

类似以上, 不解释

注意, 这这里 j 增加导致 j> high,  现在的情形是“右半边用尽”, 所以将aux左半边剩余的元素9放入a剩下的部分a[7]中, 单趟排序完成

【注意】 上面这个例子中的序列只是数组的一部分, 并不一定是整个数组

我在上面介绍过,两种不同归并算法: 基于递归的归并和基于循环的归并,  都是以单趟归并的算法为基础的。

下面先来讲一下基于递归的归并排序(自顶向下的归并排序)

基于递归的归并排序(自顶向下)

基于递归的归并排序又叫做自顶向下的归并排序

递归归并的思想

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

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

分别表示对左半边序列递归、对右半边序列递归、单趟合并操作。

全部代码:

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

测试代码:

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

输出结果

0
1
1
2
3
5
6
7
9

递归栈深度和调用顺序

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

从上到下,是各个merge的先后调用顺序,1最先调用, 15最后调用

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

(这里是按照字母排序, A最小, Z最大)

对上图可根据代码来理解

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

首先,在第一层递归的时候,先进入的是第一行的sort方法里(A处),然后紧接着又进入了第二层递归的第一行sort方法(A处), 如此继续,由(a, low,mid)的参数列表可知其递归的趋势是一直向左移动的,直到最后一层递归,所以最先执行merge的对象是a[0]和a[1](上图编号1),再然后执行的是最后一层递归的第二行代码(B处),这时候merge的对象是a[2]和a[3](上图编号2)。 再然后, 返回上一层递归,对已经有序的a[0]、a[1]和a[2]、a[3]进行merge。(上图编号3)如此继续,递归的深度不断变浅, 直到对整个数组的左右两半进行merge。 (上图编号3)

递归归并的轨迹图像

(下面展示的归并进行了一些优化,对小数组使用插入排序)

根据上文所讲的递归栈和调用顺序, 下面的轨迹图像就不难理解了: 从最左边的元素开始合并,而且左边的数组序列在第一轮合并后,相邻右边的数组按同样的轨迹进行合并, 直到合并出和左边相同长度的序列后,才和左边合并(递归栈上升一层)

基于递归归并排序的优化方法

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

用不同的方法处理小规模问题能改进大多数递归算法的性能,因为递归会使小规模问题中方法调用太过频繁,所以改进对它们的处理方法就能改进整个算法。 因为插入排序非常简单, 因此一般来说在小数组上比归并排序更快。 这种优化能使归并排序的运行时间缩短10%到15%;

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

  if(low>=high) { return; }

改成

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

就可以了,这样的话,这条语句就具有了两个功能:

1. 在适当时候终止递归

2. 当数组长度小于M的时候(high-low <= M), 不进行归并排序,而进行插排

具体代码:

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

优化点二:  测试待排序序列中左右半边是否已有序

通过测试待排序序列中左右半边是否已经有序, 在有序的情况下避免合并方法的调用。

例如对单趟合并,我们对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);  // 单趟合并
  }

优化点三:去除原数组序列到辅助数组的拷贝

在上面介绍的基于递归的归并排序的代码中, 我们在每次调用merge方法时候,我们都把a对应的序列拷贝到辅助数组aux中来,即

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

实际上,我们可以通过一种看起来比较逆天的方式把这个拷贝过程给去除掉。。。。。

为了达到这一点,我们要在递归调用的每个层次交换输入数组和输出数组的角色,从而不断地把输入数组排序到辅助数组,再将数据从辅助数组排序到输入数组。

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

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

在这里我们做了两个操作:

  • 在排序前拷贝一个和原数组元素完全一样的辅助数组(不再是创建一个空数组了!)
  • 在递归调用的每个层次交换输入数组和输出数组的角色

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

这样做的话, 我们就可以去除原数组序列到辅助数组的拷贝了!

但是你可能会问: 骚年, 我们要排序的可是原数组a啊! 你不怕一不小心最后完全排序的是辅助数组aux而不是原数组a吗?

Don't worry !! 这种情况不会发生, 看图:

由图示易知, 因为外部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++]; // 右半边当前元素大于等于左半边当前元素,取左半边元素
      }
    }
  }
}

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

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

基于循环的归并排序又叫做自底向上的归并排序

循环归并的基本思想

基于循环的代码较为简单,这里就不多赘述了

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

循环归并的轨迹图像

(下图中的sz同上面的变量size)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏刘望舒

算法(三)初等排序后篇[选择和希尔排序]

1.选择排序 根据上一篇文章讲到的插入排序和冒泡排序,我们把选择排序的数组也分为已排序部分和未排序部分。 图解选择排序 在用图来讲解选择排序之前,我们要先了...

1708
来自专栏魂祭心

原 二叉树 非递归 层序、前序、中序、后序

3054
来自专栏C/C++基础

数组中的逆序对

题目: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

621
来自专栏zaking's

用js来实现那些数据结构13(树01-二叉搜索树的实现)

  前一篇文章我们学会了第一个非顺序数据结构hashMap,那么这一篇我们来学学树,包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现,不...

36310
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

1909
来自专栏codingforever

经典算法巡礼(三) -- 排序之插入排序

插入排序,与之前的冒泡排序和选择排序一样,其名称就说明了她的原理。所谓插入排序,就是对于数组中未排序的元素,依次遍历寻找合适的位置并插入到已排序的子数组中。当数...

224
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】图篇

1806
来自专栏老马说编程

(47) 堆和PriorityQueue的应用 / 计算机程序的思维逻辑

45节介绍了堆的概念和算法,上节介绍了Java中堆的实现类PriorityQueue,PriorityQueue除了用作优先级队列,还可以用来解决一些别的问题,...

17410
来自专栏刘望舒

算法(二)初等排序前篇[插入和冒泡排序]

前言 排序是算法的基础,排序有很多种方法,有些方法实现起来很简单,但是效率较差,我们可以将这些排序的方法称之为初等排序。这篇文章我们就来学习初等排序中的插入排序...

1619
来自专栏java 成神之路

Trie Tree 实现中文分词器

33411

扫码关注云+社区