美文网首页
归并排序

归并排序

作者: anny_4243 | 来源:发表于2023-03-22 11:21 被阅读0次

    归并排序是一种基于分治法的排序算法。为了排序长度为n的数组,需要先排序两个长度为n/2的子数组,然后合并这两个排序的子数组,于是整个数组也就排序完毕。

    归并排序可以用迭代代码实现。例如,输入一个长度为8的数组[4,1,5,6,2,7,8,3],可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组,如图(a)所示。图中的箭头表示源数据位于上面的数组中,合并时将数字写入下面的数组中。然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组,如图(b)所示。此时源数据位于下面的数组中,合并时将数字写入上面的数组中。最后合并相邻的长度为4的子数组,此时整个数组排序完毕,如图(c)所示。

    归并排序的过程

    说明:

    (a)合并相邻的长度为1的子数组得到排序的长度为2的子数组;
    (b)合并相邻的长度为2的子数组得到排序的长度为4的子数组;
    (c)合并相邻的长度为4的子数组得到排序的长度为8的数组

    归并排序需要创建一个和输入数组大小相同的数组,用来保存合并两个排序子数组的结果。数组src用来存放合并之前的数字,数组dst用来保存合并之后的数字。每次在完成合并所有长度为n的子数组之后开始新一轮合并长度为2n的子数组之前,交换两个数组。
    上述过程可以用如下所示的参考代码实现:

    public int[] sortArray (int[] nums) {
        int length = nums.length;
        int[] src = nums;
        int[] dst = new int[length];
        for (int seg = 1; seg < length; seg += seg) {
            for (int start = 0; start < length; start += seg * 2) {
                int mid = Math.min(start + seg, length) ;
                int end = Math.min(start + seg * 2, length) ;
                int i = start, j = mid, k = start;
                while ( i < mid || j < end) {
                    if (j == end || (i < mid && src[i] < src[j])) {
                        dst[k++] = src[i++];
                    } else {
                        dst[k++] = src[j++]:
                    }
                }
            }
            int[] temp = src;
            src = dst;
            dst = temp;
        }
        return src;
    }
    

    假设某一时刻准备合并数组src中从下标start开始的两个长度为seg的子数组,第1个子数组的起始下标是start,结束下标是start+seg-1;第2个子数组的起始下标是start+seg,结束下标是start+seg*2-1。变量i、j是分别指向数组src中两个子数组的下标,它们从左到右扫描两个子数组,变量k是指向数组dst的下标。每次从数组src的两个子数组中选择将较小的数字写入数组dst中,最终数组dst中下标从start到start+seg*2-1的子数组就是排序的。
    归并排序也可以用递归的代码实现。为了排序长度为n的数组,只需要排序两个长度为n/2的子数组,然后合并两个排序的子数组即可。排序长度为n/2的子数组和排序长度为n的数组是同一个问题,可以递归调用同一个函数解决。归并排序的递归代码如下所示:

    public int[] sortArray (int[] nums) {
        int[] dst = new int[nums.length];
        dst = Arrays.copyOf (nums, nums.length);
        mergeSort (nums, dst, 0, nums.length) ;
        return dst;
    }
    
    private void mergesort (int[] src, int[] dst, int start, int end) {
        if (start + 1 >= end) {
            return;
        }
        int mid = (start + end) / 2:
        mergeSort (dst, src, start, mid);
        mergeSort(dst, src, mid, end);
        
        int i = start, j = mid, k = start;
        while (i < mid || j < end) {
            if (j == end || (i < mid && src[i] < src[j])) {
                dst[k++] = src[i++];
            } else {
                dst[k++] = src[j++];
            }
        }
    }
    

    由于长度为n的数组每次都被分为两个长度为n/2的数组,因此不管输入什么样的数组,归并排序的时间复杂度都是O(nlogn)。归并排序需要创建一个长度为n的辅助数组。如果用递归实现归并排序,那么递归的调用栈需要O(logn)的空间。因此,归并排序的空间复杂度是O(n)

    摘自《剑指Offer(专项突破版):数据结构与算法名企面试题精讲》

    相关文章

      网友评论

          本文标题:归并排序

          本文链接:https://www.haomeiwen.com/subject/imivrdtx.html