如何使用归并排序算法

本篇内容介绍了“如何使用归并排序算法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

归并排序算法思路

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

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

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

原地归并实现

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

• 在此过程中我们需要引入一个辅助数组；

• 定义的方法签名为merge(a, lo, mid, hi)，这个方法将数组a[lo..mid]与a[mid..hi]归并成一个有序的数组，结果存放到a[lo..mid]中；

• 该方法中需要使用的上一篇中的公共函数 less ，参考上一篇文章《常见的初级排序算法，这次全搞懂》

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         //待实现     }      private void merge(Comparable[] a, int lo, int mid, int hi) {         for (int i = lo; i <= hi; i++) {             aux[i] = a[i];         }         int i = lo, j = mid + 1;         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] = aux[i++];             } else {                 a[k] = aux[j++];             }         }     }  }

自顶向下的归并排序

基于分而治之的思想，大的数组排序，先递归拆分成小的数组，保证小的数组有序再归并，直到整个数组有序，这个操作就是自顶向下的归并排序

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         aux = new Comparable[array.length];         doSort(array, 0, array.length - 1);     }      private void doSort(Comparable[] array, int lo, int hi) {         if (lo >= hi) {             return;         }         int mid = (hi - lo) / 2 + lo;         doSort(array, lo, mid);         doSort(array, mid + 1, hi);         merge(array, lo, mid, hi);     }      private void merge(Comparable[] a, int lo, int mid, int hi) {         //省略     }  }

以上代码是标准的递归归并排序操作，但是经过仔细思考之后，该算法还有可以优化的地方

「测试数组是否已经有序」；如果a[mid]<=a[mid+1]，那么我们就可以跳过merge方法，减少merge操作；修复之后的doSort方法

private void doSort(Comparable[] array, int lo, int hi) {     if (lo >= hi) {         return;     }     int mid = (hi - lo) / 2 + lo;     doSort(array, lo, mid);     doSort(array, mid + 1, hi);     if (array[mid].compareTo(array[mid + 1]) >= 0) {         merge(array, lo, mid, hi);     } }

「对于小规模的数组可以是用插入排序」；对于小规模的数组使用归并排序会增加递归调用栈，所以我们可以考虑使用插入排序来处理子数组的排序

private void doSort(Comparable[] array, int lo, int hi) {     if (lo >= hi) {         return;     }      if (hi - lo < 5) { //测试，小于5就使用插入排序         insertionSort(array, lo, hi);         return;     }      int mid = (hi - lo) / 2 + lo;     doSort(array, lo, mid);     doSort(array, mid + 1, hi);     if (less(array[mid + 1], array[mid])) {         merge(array, lo, mid, hi);     } }  //插入排序 private void insertionSort(Comparable[] array, int lo, int hi) {     for (int i = lo; i <= hi; i++) {         for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {             exch(array, j, j - 1);         }     } }

「节省复制元素到辅助数组的时间」；要实现该操作较麻烦，需要在每一层递归的时候交换输入数据和输出数组的角色；修改之后的完整代码如下：

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         aux = array.clone();         doSort(aux, array, 0, array.length - 1);     }      private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) {         if (lo >= hi) {             return;         }          if (hi - lo < 5) { //测试，小于5就使用插入排序             insertionSort(dest, lo, hi);             return;         }          int mid = (hi - lo) / 2 + lo;         doSort(dest, src, lo, mid);         doSort(dest, src, mid + 1, hi);         if (less(src[mid + 1], src[mid])) {             merge(src, dest, lo, mid, hi);         }     }      //插入排序     private void insertionSort(Comparable[] array, int lo, int hi) {         for (int i = lo; i <= hi; i++) {             for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {                 exch(array, j, j - 1);             }         }     }      private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {         int i = lo, j = mid + 1;         for (int k = lo; k <= hi; k++) {             if (i > mid) {                 dest[k] = src[j++];             } else if (j > hi) {                 dest[k] = src[i++];             } else if (less(src[i], src[j])) {                 dest[k] = src[i++];             } else {                 dest[k] = src[j++];             }         }     }  }

每一层递归操作都会让子数组有序，但是子数组可能是aux[lo..hi]也有可能是a[lo..hi]；由于第一次调用doSort传入的是src=aux，dest=array，所以递归最后的结果一定是输入到了array中，保证了array整体排序完成

自底向上的归并排序

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

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         int length = array.length;         aux = new Comparable[length];         for (int sz = 1; sz < length; sz += sz) {             for (int i = 0; i < length - sz; i += 2 * sz) {                 merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));             }         }     }      private void merge(Comparable[] a, int lo, int mid, int hi) {         for (int i = lo; i <= hi; i++) {             aux[i] = a[i];         }         int i = lo, j = mid + 1;         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] = aux[i++];             } else {                 a[k] = aux[j++];             }         }     }  }

“如何使用归并排序算法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！