归并排序

归并排序

         归并排序是利归并的思想实现的排序算法,即采用经典的分治策略。

归并排序的示意图1   基本思想

归并排序的示意图2  合并有序子序列

       上图中最后一次合并是将[4,5,7,8]以及[1,2,3,6]合并为[1,2,3,4,5,6,7,8]图示结果如下

分解和合并代码如下

将两个有序子序列合并
 public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//左边数组初始索引
        int j=mid+1;//右边数组初始索引
        int t=0;
        //有序数组转移到temp,直到左右两边有一边数组完成转移
        while (i<=mid&&j<=right){
            if(arr[i]<arr[j]){
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }
        //剩余的转移到temp
        //如果左边数组有剩余,则继续进行转移
        while (i<=mid){
            temp[t]=arr[i];
            t++;
            i++;
        }
        //如果右边数组有剩余,则继续进行转移
        while (j<=right){
            temp[t]=arr[j];
            t++;
            j++;
        }
        //temp数组转移到arr;
        t=0;
        while (left<=right){
            arr[left]=temp[t];
            t++;
            left++;
        }

    }
采用递归的方法对数组进行分解

public static void mergesort(int[] arr,int left,int right,int[] temp){
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        //向左递归进行分解
        mergesort(arr,left,mid,temp);
        //向右递归进行分解
        mergesort(arr,mid+1,right,temp);
        //合并两个有序数组
        merge(arr,left,mid,right,temp);

    }

完整代码如下

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr={8,4,5,7,1,3,6,2,10,-1,2000,10,7,8};
        int[] temp=new int[arr.length];
        mergesort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));

    }
    //分解+合并
    public static void mergesort(int[] arr,int left,int right,int[] temp){
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        //向左递归进行分解
        mergesort(arr,left,mid,temp);
        //向右递归进行分解
        mergesort(arr,mid+1,right,temp);
        //合并两个有序数组
        merge(arr,left,mid,right,temp);

    }
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//左边数组初始索引
        int j=mid+1;//右边数组初始索引
        int t=0;
        //有序数组转移到temp,直到左右两边有一边数组完成转移
        while (i<=mid&&j<=right){
            if(arr[i]<arr[j]){
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }
        //剩余的转移到temp
        //如果左边数组有剩余,则继续进行转移
        while (i<=mid){
            temp[t]=arr[i];
            t++;
            i++;
        }
        //如果右边数组有剩余,则继续进行转移
        while (j<=right){
            temp[t]=arr[j];
            t++;
            j++;
        }
        //temp数组转移到arr;
        t=0;
        while (left<=right){
            arr[left]=temp[t];
            t++;
            left++;
        }

    }
}



#堆排序小根堆#
全部评论
似乎学习到了
点赞 回复 分享
发布于 2022-10-08 12:07 陕西

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务