本文介绍: 归并排序是一种常见的排序算法,也是一种分治策略的典型应用。该算法基本思想是将待排序序列分成若干个子序列然后递归地对这些子序列进行排序,最终将排好序的子序列合并一个有序序列。具体来说,归并排序过程可以分为两个阶段。第一个阶段是分解,即将原序列分成若干个长度相等的子序列,每个子序列再分成若干个长度相等的子序列,直到无法分解为止。第二个阶段是合并,即将已排好序的子序列合并一个有序序列。

一、什么是归并排序

归并排序是一种常见的排序算法,也是一种分治策略的典型应用。该算法基本思想是将待排序的序列分成若干个子序列,然后递归地对这些子序列进行排序,最终将排好序的子序列合并一个有序序列。

具体来说,归并排序的过程可以分为两个阶段。

第一个阶段是分解,即将原序列分成若干个长度相等的子序列,每个子序列再分成若干个长度相等的子序列,直到无法分解为止。

第二个阶段是合并,即将已排好序的子序列合并成一个有序序列。

二、代码实现 

  递归

 public static void mergeSort(int[] nums,int left,int right){
        if(left >= right){
            return ;
        }
        int mid = (left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    public static void merge(int[] nums,int left,int mid,int right){
        // 左子数组区间 [left, mid], 右子数组区间 [mid+1, right]
        // 创建一个临时数组 tmp用于存放合并后的结果
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int s2 = mid+1;
        // 当左右子数组都还有元素时,比较并将较小的元素复制到临时数组中
        while(s1 <= mid &amp;&amp; s2 <= right){
            if(nums[s1] <= nums[s2]){
                tmp[k++] = nums[s1++];
            }else{
                tmp[k++] = nums[s2++];
            }
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (s1 <= mid){
            tmp[k++] = nums[s1++];
        }
        while (s2 <= right){
            tmp[k++] = nums[s2++];
        }
         // 将临时数组 tmp 中的元素复制回原数组 nums对应区间
        for (int i = 0; i < tmp.length; i++) {
            nums[i+left] = tmp[i];
        }
    }

递归: 

public  static void mergeSort(int[] nums){
        //模拟递归的效果
        int gap = 1;
        while(gap < nums.length){
            for (int i = 0; i < nums.length; i += gap * 2) {
                int left = i;
                int mid = left + gap -1;
                if(mid >= nums.length){
                    mid  = nums.length -1;
                }
                int right = mid + gap;
                if(right >= nums.length){
                    right  = nums.length -1;
                }
                merge(nums,left,mid,right);
            }
            gap *= 2;
        }
    }
 public static void merge(int[] nums,int left,int mid,int right){
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int s2 = mid+1;
        while(s1 <= mid &amp;& s2 <= right){
            if(nums[s1] <= nums[s2]){
                tmp[k++] = nums[s1++];
            }else{
                tmp[k++] = nums[s2++];
            }
        }
        while (s1 <= mid){
            tmp[k++] = nums[s1++];
        }
        while (s2 <= right){
            tmp[k++] = nums[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            nums[i+left] = tmp[i];
        }
    }

三、算法特性 

时间复杂度 O(n ^ log n),划分产生高度为 log ⁡n 的递归树,每层合并的总操作数量为 n ,因此总体时间复杂度为 O(n ^ log⁡ n) 。

空间复杂度:O(n),递归深度为 log⁡ n ,使用 O(log⁡ n) 大小的栈帧空间合并操作需要借助辅助数组实现使用 O(n) 大小的额外空间。

稳定排序:在合并过程中,相等元素的次序保持不变。

原文地址:https://blog.csdn.net/f7ashion/article/details/134610284

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_12395.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注