一道归并排序题的解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/53710263

设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后的结果为 ()。


二路归并:如果序列中有n 个记录,可以先把它看成n个子序列,每个子序列中只包含一个记录,因而都是排好序的。二路归并排序先将每相邻的两个子序列合并,得到n/2(向上取整)个较大的有序子序列,每个子序列包含2个记录。再将这些子序列两两合并。如此反复,直到最后合并成一个有序序列,排序即告完成。

设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1};

第二次归并后:{6,100,202,301},{1,8,38};

第三次归并后:{1,6,8,38,100,202,301}

对于本题,初始数列为:{Q,D,F,X,A,P,N,B,Y,M,C,W}

初始状态:Q,D,F,X,A,P,N,B,Y,M,C,W

第一次归并后:{D,Q},{F,X},{A,P},{B,N},{M,Y},{C,W};

第二次归并后:{D,F,Q,X},{A,B,N,P},{C,M,Y,W};

第三次归并后:{A,B,D,F,N,P,Q,X},{C,M,Y,W};

第四次归并后:{A,B,C,D,F,M,N,P,Q,X,Y,W};


参考答案 :DQFXAPBNMYCW

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏令仔很忙

新手学JAVA(三)----StringBuilder类

上一篇文章新手学JAVA(二)----String类与StringBuffer类的区别中了解到,String的值是不可变的,这就导致

761
来自专栏用户2442861的专栏

Java基础之String中equals,声明方式,等大总结

    转载请注明出处:http://blog.csdn.net/dmk877/article/details/49420141 

832
来自专栏决胜机器学习

PHP面向对象核心(二)——继承、多态、接口

PHP面向对象核心(二) (原创内容,转载请注明来源,谢谢) 三、继承与多态 3.1 继承 1、继承是类级别的复用,关键词为extends;多态是方法级别的复用...

37412
来自专栏大闲人柴毛毛

String类中你不知道的知识

直接量创建对象更高效 在Java中,创建一个字符串有两种方法: //第一种方法 String str1 = "字符串1"; //第二种方法 String str...

2926
来自专栏AI研习社

最常见的 35 个 Python 面试题及答案(2018 版)

作为一个 Python 新手,你必须熟悉基础知识。在本文中我们将讨论一些 Python 面试的基础问题和高级问题以及答案,以帮助你完成面试。包括 Python ...

7303
来自专栏微信公众号:Java团长

深入理解Java:String

按照官方的说法:Java 虚拟机具有一个堆,堆是运行时数据区域,所有类实例和数组的内存均从此处分配。

1071
来自专栏数据结构与算法

1013. 识别三角形

1013. 识别三角形 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 输入三个正整数,判断...

3333
来自专栏技术栈大杂烩

Python: 作用域(scope) 和 LEGB

不管在什么编程语言, 都有作用域这个概念.作用域控制在它范围内代码的生存周期, 包括名字和实体的绑定.

1203
来自专栏java一日一条

Java编程入门(2.4):变量和基本类型

查看 API 会发现,String、StringBuffer、StringBuilder 都实现了 CharSequence 接口,内部都是用一个char数组实...

781
来自专栏java工会

Java基础第二阶段知识点,招初级java的面试官都在问这些

JDK:是java开发的工具箱,包含jre,还包含将java文件编译为class文件的javac工具类(编译器),除此之外还包括java原生的API;包含J2S...

1301

扫码关注云+社区

领取腾讯云代金券