归并排序算法

前言

本篇我们谈一种基于归并操作完成排序的算法。

归并排序算法思路

要将一个数组排序，可以先将数组分为两个数组分别排序，然后再将结果归并在一起，重复递归这个过程，直到数组整体有序，这就是归并排序的算法思路。

归并排序的优点是它能够保证任意长度为N的数组排序所需的时间与 NlogN 成正比，这个优点是初级排序无法达到的。

缺点是因为归并操作需要引入额外的数组，额外的空间与N成正比

原地归并实现

在实现归并排序之前，我们需要先完成两个有序数组的归并操作，即将两个有序的数组合并成一个有序的数组；

• 在此过程中我们需要引入一个辅助数组；
• 定义的方法签名为merge(a, lo, mid, hi)，这个方法将数组a[lo..mid]与a[mid..hi]归并成一个有序的数组，结果存放到a[lo..mid]中；
• 该方法中需要使用的上一篇中的公共函数 less ，参考上一篇文章《常见的初级排序算法，这次全搞懂》上代码是标准的递归归并排序操作，但是经过仔细思考之后，该算法还有可以优化的地方

  「测试数组是否已经有序」；如果a[mid]<=a[mid+1]，那么我们就可以跳过merge方法，减少merge操作；修复之后的doSort方法每一层递归操作都会让子数组有序，但是子数组可能是aux[lo..hi]也有可能是a[lo..hi]；由于第一次调用doSort传入的是src=aux，dest=array，所以递归最后的结果一定是输入到了array中，保证了array整体排序完成

  自底向上的归并排序

  实现归并算法还有另一种思路，就是先归并哪些小的数组，然后再成对归并得到子数组，直到整个数组有序
  

（编辑：甘孜站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!