归并排序算法详解

算法介绍

引用百度百科的介绍。

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法描述

归并排序，采用是分治法，先将数组分成子序列，让子序列有序，再将子序列间有序，合并成有序数组。

算法描述：

（1）把长度为n的输入序列分成长度 n/2的子序列；
（2）对两个子序列采用归并排序；
（3）合并所有子序列。

算法实现

    void mergeSortInOrder(int[] arr,int bgn,int mid, int end){
        int l = bgn, m = mid +1, e = end;
        //相当于对一个数组的前半部分和后半部分进行排序排序，从开始的只有两个数，到后面
        //因为基本有序，所以只需要进行合并就行
        int[] arrs = new int[end - bgn + 1];
        int k = 0;
        //进行有序合并
        while(l <= mid && m <= e){
            if(arr[l] < arr[m]){
                arrs[k++] = arr[l++];
            }else{
                arrs[k++] = arr[m++];
            }
        }
        //如果前半部分大的比较多，直接接在后面
        while(l <= mid){
            arrs[k++] = arr[l++];
        }
        //如果后半部分大的比较多，直接接在后面
        while(m <= e){
            arrs[k++] = arr[m++];
        }
        //对我们原来的数组进行值的覆盖
        for(int i = 0; i < arrs.length; i++){
            arr[i + bgn] = arrs[i];
        }
    }
     void mergeSort(int[] arr, int bgn, int end){
        //如果开始指针大于结束指针，结束
        if(bgn >= end){
            return;
        }
        //通过分治将我们的数组分成多个小数组
        int mid = (bgn + end) >> 1;
        mergeSort(arr,bgn,mid);
        mergeSort(arr,mid + 1, end);
        //对我们的小数组进行排序
        mergeSortInOrder(arr,bgn,mid,end);
    }

算法分析

稳定排序

外排序（需要消耗额外的内存）

时间复杂度O(nlogn)，空间复杂度为O(1)

本文作者：CryFace

本文链接：https://www.cnblogs.com/CryFace/p/13706441.html

版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。