常用内部排序算法之一:归并排序-阿里云开发者社区

开发者社区> rhwayfun> 正文

常用内部排序算法之一:归并排序

简介:
+关注继续查看

前言
归并排序是所有常用内部排序算法中稳定性最好的,无论是平均时间复杂度、最坏时间复杂度还是最好时间复杂度,其时间复杂度都是O(nlogn)。由于这个特性,在需要考虑排序稳定性的情况下,归并排序是所有优化算法(直接插入排序、冒泡排序和简单选择排序)使用最多的。其实归并排序算法的思想很简单:假设初始序列含有n个记录,则可以看成是n个有序的子序列,每一个子序列的长度都是1,然后把这些子序列两两归并,得到n/2x表示不小于x的最小整数)个长度为2或者1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止。这种方法也被称为2路归并排序。

首先看代码的实现过程:

package com.rhwayfun.algorithm.sort;

/**
 * 归并排序
 * @author Administrator
 *
 */
public class MergeSort2 {

    public void mergeSort(int[] a){
        mSort(a,a,0,a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    private void mSort(int[] b, int[] a, int i, int j) {
        int m = 0;
        int[] c = new int[a.length];
        if(i == j){//递归终止条件
            a[i] = b[i];
        }else {
            m = (i + j)/2;
            //将数组a分为a[i...m]并进行排序
            mSort(b,c,i,m);
            //数组a[m+1...j]部分进行排序
            mSort(b, c, m + 1, j);
            //将a[i...m]部分和a[m+1...j]部分的排序结果归并到a
            merge(c,a,i,m,j);
        }
    }

    private void merge(int[] b, int[] a, int i, int m, int t) {
        int j = 0,k = 0,l = 0;
        for(j = m+1,k = i;i <= m && j<=t;k++){
            //将b中记录由小到大归并到a中
            if(b[i] < b[j]){
                a[k] = b[i++];
            }else {
                a[k] = b[j++];
            }
        }
        //将剩余b[i...m]复制到a中
        if(i<=m){
            for(l=0;l<=m-i;l++){
                a[k+l]=b[i+l];
            }
        }
        //将剩余b[m+1...t]复制到数组a中
        if(j<=t){
            for(l=0;l<=t-j;l++){
                a[k+l]=b[j+l];
            }
        }
    }

    public static void main(String[] args) {
        new MergeSort2().mergeSort(new int[]{50,10,90,30,70,40,80,60,20});
    }
}

下面以序列{50,10,90,30,70,40,80,60,20}为例,说明归并排序的具体过程:

  1. 初始时刻,mSort方法中的数组b和数组a都是{50,10,90,30,70,40,80,60,20}
  2. i = 0,j = 9,显然两者不相等,将数组b分为b[i…m]和b[m+1…j],此时m = 5,也就是数组b 正中间下标
  3. 然后递归调用mSort函数,继续将b[0…5]和b[6…9]拆成两组,直到每组只有一个元素
  4. 两次递归调用mSort函数之后,b[0…5]和b[6…9]已经排好序了,最后将这两组排好序的数组继续归并成最终排好序的数组,这个过程调用的是merge函数,该函数的主要目的就是将最好的两组进行归并排序
  5. 将排好序的数组返回给原数组a,排序结束

归并排序小结

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log2n的栈空间,因此归并排序的空间复杂度是O(n+logn)

归并排序的总的时间复杂度是O(nlogn),同时这也是最好、最坏、平均的时间复杂度。需要注意的是,归并排序的是一种稳定的排序算法,但是归并排序是比较占用内存的。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【算法练习】IDEA集成leetcode插件实现快速刷题
【算法练习】IDEA集成leetcode插件实现快速刷题
3 0
人类首次完全利用AI发现「迄今最强抗生素」,登上《细胞》杂志封面
MIT 科学家用深度学习模型发现的「halicin」抗生素分子展示了前所未有的广谱抗菌能力,这是人类首次完全使用人工智能的方法发现新抗生素。研究人员表示,halicin 可以消灭一些世界上最危险的细菌。他们的这一研究登上了生命科学顶级期刊《Cell》。
6 0
使用JDK自带的VisualVM进行Java程序的性能分析
使用JDK自带的VisualVM进行Java程序的性能分析
4 0
使用JDK自带的VisualVM进行Java程序的性能分析
使用JDK自带的VisualVM进行Java程序的性能分析
3 0
摆脱电缆、可移除四肢,NASA 人形机器人「女武神」替人类奔赴灾难场景
本文对NASA开发的Valkyrie人形机器人进行了详解,包括这款机器人与机器宇航员2号(Robonaut 2)的区别、算法与技术以及任务完成情况等。相信读者会对Valkyrie人形机器人的研发背景、构造算法以及未来场景的应用有更清楚的了解。
3 0
MySQL8.0实战(二) - 数据库设计(上)
MySQL8.0实战(二) - 数据库设计(上)
3 0
【学习路线】Java后端高薪学习路线超全超详细总结,附资料领取
Java后端高薪学习路线超全超详细总结,附资料领取
3 0
AAAI 2020 | BERT稳吗?亚马逊、MIT等提出针对NLP模型的对抗攻击框架TextFooler
不久前,AAAI 2020 在美国纽约召开。大会官方公布了今年的论文收录信息:收到 8800 篇提交论文,评审了 7737 篇,接收 1591 篇,接收率 20.6%。为向读者们分享更多的优质内容、促进学术交流,机器之心策划了多期 AAAI 2020 论文线上分享。
6 0
使用JDK自带的VisualVM进行Java程序的性能分析
使用JDK自带的VisualVM进行Java程序的性能分析
3 0
+关注
111
文章
0
问答
来源圈子
更多
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载