归并排序

时间:2021-1-8 作者:admin

写在前面

随着现在面试越来越变态,动不动就是手写几道算法题,而且很多都是常见排序算法的变形,因此掌握好常见的排序算法是学好其他算法的基础。但是已经记不清这是第几次学习排序算法了,每次都是当时学完,看似懂了,然后过一段时间如果不去看又忘记了。因此本文的重点是用浅显易懂的方法讲述算法,我的实现尽可能地从更多的实例触发,一步一步地去引出算法,然后进行实现。(算法的实现过程跟其他大佬可能有所区别,更多地是按照自己的理解的思路去实现)。同时目的是记录下来以备以后复习。这一节,我们学习归并排序。

归并排序的概念

思考

假设有两个有序的数组我们需要对其进行排序,合并成一个有序的数组。如下所示:

let arr1 = [1,3,4,6];
let arr2 = [2,5,7,8];
// 需要得到 [1,2,3,4,5,6,7,8]

对于两个有序的数组,我们想要对其进行合并,那么肯定需要利用它的有序性,因此我们肯定需要分别从数组的两端同时开始,用通俗的话来说,就是将两个手指头放到两个数组的开头(都是最小),手指头指向的数,谁小就将其放到新的数组中。然后这个手指头往后移动一位,直到移动到这个数组最后。这里需要考虑的是两个边界条件:

  1. 如果左边数组先结束了,那么剩下的右边数组值肯定都比左边数组大,因此直接将剩下的数组的值添加到新数组中即可。
  2. 同理,如果右边数组先结束了,那么就把左边数组中的值直接添加到新数组中。

最终的实现如下:

const merge = (a, b) => {
  let c = [];
  let i = 0;
  let k = 0;
  while (i < a.length || k < b.length) {
    if (i >= a.length) {
      c.push(b[k]);
      k += 1;
    } else if (k >= b.length) {
      c.push(a[i]);
      i += 1;
    } else {
      if (a[i] <= b[k]) {
        c.push(a[i]);
        i += 1;
      } else {
        c.push(b[k]);
        k += 1;
      }
    }
  }
  return c;
};

我们使用上面的merge函数测试一下一些有序数组:

console.log(merge([1,3,4,6],[2,5,7,8]))   // [1,2,3,4,5,6,7,8]
console.log(merge([5, 6, 7], [1, 2, 3,4]));  // [1,2,3,4,5,6,7]
console.log(merge([1, 3], [2,4,6,7]));  // [1,2,3,4,6,7]

好了,到目前为止,我们能够实现将两个有序数组进行排序了,但是如果一个序列是无序的,但是我们又想将其转化成两个有序数组进行排列。比如:

let arr = [1,3,4,6,2,5,7,8]

这个数组整体是无序的,但是如果将其拆分成[1,3,4,6]和[2,5,7,8],它就是两个有序数组,这样的话就可以使用我们上面的方法进行排序了。实现思路如下:

let sort = (arr) => {
  let k = arr.length;
  let left = arr.slice(0,parseInt(k/2));
  let right = arr.slice(parseInt(k/2));
  return merge (left,right);
}

我们可以发现,上面的排序函数的实现过程是,先拆分成两个数组,然后使得这两个数组有序(由于我们已经看出了他们是有序的,因此先不关注为什么他是有序的),最后合并这两个有序数组。这样的话就实现了整个数组的排序。这就是归并排序的思想:

归并排序的思想

归并排序的主要思想是分治法。主要过程是:

1、将n个元素从中间切开,分成两部分。(左右两边可能相差一个数)
2、将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1或者2。
3、从最底层开始逐步合并两个排好序的数列。

通过上面的分析,我们已经知道我们想要合并的必须是两个有序的数组,但是我们无法确保拆分后的数组是有序的,因此需要对拆分后的数组进行排序。但是如何去排序了?难道又去使用其他的排序方法,那肯定得不偿失了,其关键就是继续拆分,试想一下,我们很难对4个数的数组进行排序,很难直接对3个数的数组进行排序,但是对2个数的数组排序就比较简单了,对一个数进行排序就更加简单了。因此,我们只需要不断地拆分,直到数组长度为1或者2就很容易实现一个有序的数组。这么说可能有点抽象,我们继续看一个简单的例子:
假设有这样一个正整数数组,需要给它们进行排序。

let arr = [6,5,3,1,8,7,2,4];
const sort = (arr) => {
    // 若干代码
    return arr;
}

分析思路如下:
当数组长度为1时,即arr=[6]:那么只需要返回原数组即可。

const sort = (arr) => {
    return arr;
}

当数组长度为2时,即arr=[6,5]:那么只需要比较这两个数即可

const sort = ([a,b]) =>{
    return a > b ? [b,a] : [a,b];
}

当数组长度为3时,即arr=[6,5,3]:3个数就无法直接得出结论了,但是我们已经计算出[6,5]的顺序了,得到一个有序数组[5,6],同时数组[3]也能够直接得出有序数组即它本身[3],因此我们只需要再合并两个有序数组[5,6]和[3]即可得到排序后的数组。
当数组长度为4时,即[6,5,3,1]:四个数组成的数组,我们目前已知的能够直接得到有序的数组是长度为2或者1,因此我们都将他们拆分成长度为2的数组即,[6,5]和[3,1]。然后分别得到他们的顺序[5,6]和[1,3]这时候再合并[5,6]和[1,3]这两个有序数组即可。
综上所述,我们可以发现我们每次只需要将数组拆分成左右两个数组,然后再将左右数组不断拆分,拆分到数组中只剩下一个或者2个元素,这时候直接就能够得到有序数组,然后再不断地合并回来即可,最终就得到了一个有序的数组。关键是如何去合并两个有序数组,这个我们一开始就已经实现了。

我们可以查看下归并排序的动态演示图。

归并排序的简单实现

sort:对子序列递归排序

归并排序的实现,首先我们需要不断地拆分数组,每次都将数组进行均分,直到数组长度为1或者2。

const sort = (arr) => {
  let k = arr.length;
  if (k === 1) {
    return arr;
  }
  if( k===2){
      return arr[0] > arr[1] ?[arr[1],arr[0] ]:[arr[1],arr[0]]
  }
  let left = arr.slice(0, parseInt(k / 2));
  let right = arr.slice(parseInt(k / 2));
  // merge 也是复制到一个新的数组
  return merge(sort(left), sort(right));
}

如上代码所示:我们不断地分割,当分割的数组长度为1或者2时就很容易得到一个有序数组。然后只需要将有序数组进行合并即可。接下来就是实现去合并两个有序数组。

merge:合并两个有序数组

合并两个有序数组的方法,我们在上面已经实现了。

const merge = (a, b) => {
  let c = [];
  let i = 0;
  let k = 0;
  while (i < a.length || k < b.length) {
    if (i >= a.length) {
      c.push(b[k]);
      k += 1;
    } else if (k >= b.length) {
      c.push(a[i]);
      i += 1;
    } else {
      if (a[i] <= b[k]) {
        c.push(a[i]);
        i += 1;
      } else {
        c.push(b[k]);
        k += 1;
      }
    }
  }
  return c;
};

这样的话,我们就已经得到了简易的归并排序算法:

const sort = (arr) => {
  let k = arr.length;
  if (k === 1) {
    return arr;
  }
  if( k===2){
      return arr[0] > arr[1] ?[arr[1],arr[0] ]:[arr[1],arr[0]]
  }
  let left = arr.slice(0, parseInt(k / 2));
  let right = arr.slice(parseInt(k / 2));
  // merge 也是复制到一个新的数组
  return merge(sort(left), sort(right));
};
const merge = (a, b) => {
  let c = [];
  let i = 0;
  let k = 0;
  while (i < a.length || k < b.length) {
    if (i >= a.length) {
      c.push(b[k]);
      k += 1;
    } else if (k >= b.length) {
      c.push(a[i]);
      i += 1;
    } else {
      if (a[i] <= b[k]) {
        c.push(a[i]);
        i += 1;
      } else {
        c.push(b[k]);
        k += 1;
      }
    }
  }
  return c;
};

我们使用sort方法进行排序:

console.log(sort([1,3,2,4,5,6,7]));   // [1,2,3,4,5,6,7]
console.log(sort([5,8,1,3,2,0,4]));   // [ 0, 1, 2, 3, 4, 5, 8 ]

就地归并排序

什么是就地排序

好了,到目前为止我们已经实现了一个简单的归并排序算法。但是我们看上面的sort函数有没有发现什么问题:

const sort = (arr) => {
  let k = arr.length;
  if (k === 1) {
    return arr;
  }
  if( k===2){
      return arr[0] > arr[1] ?[arr[1],arr[0] ]:[arr[1],arr[0]]
  }
  let left = arr.slice(0, parseInt(k / 2));    // 看这里
  let right = arr.slice(parseInt(k / 2));      // 看这里
  // merge 也是复制到一个新的数组
  return merge(sort(left), sort(right));
};

我们发现每次在进行分解时,都创建了两个变量,用来复制原来的数组元素。也就是说我们每分解一次都需要开辟
两块内存空间。我们以数组[6,5,3,1,8,7,2,4]为例,看下内存示意图:

如何实现就地归并排序

仍然以数组[6,5,3,1,8,7,2,4]为例,我们之前是将其拆分成[6,5,3,1]和[8,7,2,4]两个有序数组,然后进行合并。那么我们可不可以理解为,以下标4作为分隔点,分别对数组下标为[0,4)和[4,8)进行排序,也就是说我们将数组拆分编程通过分隔点在原数组上进行排序,这样就避免了开辟新的内存。我们分析一下详细的排序过程:

  1. 第一次分隔点为中间位置也就是4,需要排序的是[0,4)和[4,8)。接下来我们先分割左边的。
  2. 接下来就是分割[0,4),分割点是中间位置parseInt(4)=2,因此,左边是[0,2),右边是[2,4)。
  3. 接下来就是分割[0,2),分割点是中间位置parseInt(2)=1,因此,左边是[0,1),右边是[1,2)。

这时候左边得到的就是数字6,右边得到的就是数字5,因此需要对它们进行就地合并操作。

从上面的分析中,我们可以知道我们想要实现就地排序,需要知道排序的起始位置start和结束位置end,(分隔点是起始位置和结束位置的中间位置)。接下来我们就需要改变一下sort函数的实现。

const sort = (arr) => {
  const inplaceSort = (arr,start,end) => {
    // 具体实现
    return arr;
  }
  return inplaceSort(arr,0,arr.length)
};

sort函数还是只能接收一个参数,但是内部的实现必须能够接收排序的起始位置和结束位置,因此,我们将sort函数的实现,转化成inplaceSort函数的实现。
inplaceSort的具体实现如下:

const inplaceSort = (arr,start,end) => {
    if(end-start <=1){
      return arr;
    }
    let middle = parseInt((start + end) /2);
    inplaceSort(arr,start,middle);
    inplaceSort(arr,middle,end);
    inplaceMerge(arr,start,middle,end);
    return arr;
  }

我们可以发现,就地排序的实现其实也是一样将其不断地拆分,只不过从拆分数组变成获取start和end。同理合并两个有序数组也需要变成合并从[start,middle)和[middle,end)。其中[start,middle)是有序的,[middle,end)也是有序的。因此,关键是实现implaceMerge函数。

const inplaceMerge = (arr, start, middle, end) => {
  let i = start,
      k = middle;
  while (i < middle && k < end) {
    let w = 0;
    while (arr[i] <= arr[k] && i < middle) {
      i += 1;
    }
    while (arr[i] >= arr[k] && k < end) {
      k += 1;
      w += 1;
    }
    let part = arr.splice(k - w, w);
    arr.splice(i, 0, ...part);
    i += w;
    middle += w;
  }
  return arr;
};

实现的过程其实跟之前的merge函数类似,也是左右手指各指向左边开始位置start和右边开始位置middle。
如果左边小就往右移动一位,直到碰到middle位置(左边到了middle,说明左边最大的都比右边最小的小了,因此直接结束);如果是右边小,需要移动一位使用w记录下来,然后继续往右移动,直到比左边的大,或者直到end结束。然后切割[middle,middle + w)的元素添加到左边元素。(其实也可以每小一个就切割一个,这里为了减少这种splice操作,把多个进行了)。
因此,我们最终实现的就地归并排序是:

const sort = (arr) => {
  return inplaceSort(arr,0,arr.length)
};

const inplaceSort = (arr, start, end) => {
  if (end - start <= 1) {
    return arr;
  }
  let middle = parseInt((start + end) / 2);
  inplaceSort(arr, start, middle);
  inplaceSort(arr, middle, end);
  inplaceMerge(arr, start, middle, end);
  return arr;
};

const inplaceMerge = (arr, start, middle, end) => {
  let i = start,
    k = middle;
  while (i < middle && k < end) {
    let w = 0;
    while (arr[i] <= arr[k] && i < middle) {
      i += 1;
    }
    while (arr[i] >= arr[k] && k < end) {
      k += 1;
      w += 1;
    }
    let part = arr.splice(k - w, w);
    arr.splice(i, 0, ...part);
    i += w;
    middle += w;
  }
  return arr;
};

总结

本文我们通过从一个简单地实现两个有序数组排序出发,逐步引出了归并排序的概念,并实现了归并排序。其主要内容包括:

  1. 如何实现两个有序数组的排序
  2. 数组的分割递归排序理念
  3. 实现了简单的归并排序
  4. 实现了就地归并排序
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。