常用内部排序算法之四：归并排序

时间：2022-12-23 00:10:48

归并排序（Merge Sort）


基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

 常用内部排序算法之四：归并排序


合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

  1. j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
  2. 若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
  3. //选取r[i]和r[j]较小的存入辅助数组rf
    如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵
    否则，rf[k]=r[j]； j++； k++； 转⑵
  4. //将尚未处理完的子表中元素存入rf
    如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
    如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
  5. 合并结束。

Java算法实现：

public class MergeSort2 {

    public void mergeSort(int[] a){
        mSort(a,a,0,a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    private void mSort(int[] b, int[] a, int i, int j) {
        int m = 0;
        int[] c = new int[a.length];
        if(i == j){//递归终止条件
            a[i] = b[i];
        }else {
            m = (i + j)/2;
            //将数组a分为a[i...m]并进行排序
            mSort(b,c,i,m);
            //数组a[m+1...j]部分进行排序
            mSort(b, c, m + 1, j);
            //将a[i...m]部分和a[m+1...j]部分的排序结果归并到a
            merge(c,a,i,m,j);
        }
    }

    private void merge(int[] b, int[] a, int i, int m, int t) {
        int j = 0,k = 0,l = 0;
        for(j = m+1,k = i;i <= m && j<=t;k++){
            //将b中记录由小到大归并到a中
            if(b[i] < b[j]){
                a[k] = b[i++];
            }else {
                a[k] = b[j++];
            }
        }
        //将剩余b[i...m]复制到a中
        if(i<=m){
            for(l=0;l<=m-i;l++){
                a[k+l]=b[i+l];
            }
        }
        //将剩余b[m+1...t]复制到数组a中
        if(j<=t){
            for(l=0;l<=t-j;l++){
                a[k+l]=b[j+l];
            }
        }
    }

    public static void main(String[] args) {
        new MergeSort2().mergeSort(new int[]{50,10,90,30,70,40,80,60,20});
    }
}

下面以序列{50,10,90,30,70,40,80,60,20}为例，说明归并排序的具体过程：

  1. 初始时刻，mSort方法中的数组b和数组a都是{50,10,90,30,70,40,80,60,20}
  2. i = 0，j = 9,显然两者不相等，将数组b分为b[i…m]和b[m+1…j]，此时m = 5，也就是数组b 正中间下标
  3. 然后递归调用mSort函数，继续将b[0…5]和b[6…9]拆成两组，直到每组只有一个元素
  4. 两次递归调用mSort函数之后，b[0…5]和b[6…9]已经排好序了，最后将这两组排好序的数组继续归并成最终排好序的数组，这个过程调用的是merge函数，该函数的主要目的就是将最好的两组进行归并排序
  5. 将排好序的数组返回给原数组a，排序结束

归并排序小结

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log2nlog2n的栈空间，因此归并排序的空间复杂度是O(nlog2n)。

归并排序的总的时间复杂度是O(nlog2n)。同时这也是最好、最坏、平均的时间复杂度。需要注意的是，归并排序的是一种稳定的排序算法，但是归并排序是比较占用内存的。



标签：

相关文章