首页 / 算法 / 排序算法五：归并排序

排序算法五：归并排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法五：归并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1967字，纯文字阅读大概需要3分钟。

内容图文

效率仅次于快排的一种排序算法， 一般用于对总体无序，但是各子项相对有序的数列

思想： 采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序

排序算法五：归并排序 - 文章图片
平均时间复杂度为 nlog2n ，空间复杂度为n，稳定

public class Merge {
    /**
     * 对数组进行排序
     * @param arr：要排序的数组
     * @param left：数组的开始下标
     * @param right：数组的终止下标
     */
    public void sort(int[] arr,int left,int right){
        if(left==right) return;
        int mid=(left+right)/2;               //记录中间位置下标,将数组分成两半
        sort(arr,left,mid);                   //左边排序
        sort(arr,mid+1,right);            //右边排序
        merge(arr,left,mid+1,right);
    }

    /**
     *归并排序
     * @param arr:要排序的数组
     * @param leftptr:排序的左指针
     * @param rightptr：排序的右指针
     * @param bound：边界
     */
    public void merge(int[] arr , int leftptr , int rightptr , int bound){
        //int mid=rightptr-1;                  //记录中间位置的下标
        int[] temp=new int[bound-leftptr+1];        //用于存放排好序的数组
        int i=leftptr;                               //记录前半截数组的初始下标
        int j=rightptr;                           //记录后半截数组的初始下标
        int k=0;                               //记录新数组的第一个下标
        while (i<rightptr&&j<=bound){         //当前半截数组与后半截数组都有未排好序的数时
            if(arr[i]<=arr[j]){                 //判断前半截数组与后半截数组值的大小
                temp[k]=arr[i];                //交换，将小的数存放在新的数组中
                i++;
                k++;
            }else{
                temp[k]=arr[j];
                j++;
                k++;
            }
        }
        while (i<rightptr) {            //如果一方已排好序而另一方还有数剩，则说明剩下的数已排好序，直接存放在新数组中
            temp[k]=arr[i];
            i++;
            k++;
        }
        while (j<=bound){
            temp[k]=arr[j];
            j++;
            k++;
        }
        for(int a=0;a<temp.length;a++){
             arr[leftptr+a]=temp[a];
        }
    }


}

主函数：

public class main {
    public static void main(String[] args) {
        int[] arr={4,5,7,3,5,42,6,1,2,1,75};
        Merge merge=new Merge();
        merge.sort(arr,0,arr.length-1);
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }

}

输出：1 1 2 3 4 5 5 6 7 42 75

MoreMbb 发布了18 篇原创文章 · 获赞 43 · 访问量 1万+ 私信 关注

内容总结

以上是互联网集市为您收集整理的排序算法五：归并排序全部内容，希望文章能够帮你解决排序算法五：归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/640690.html

来源：【匿名】