【出自JD笔试题】
难度系数:★★★★☆ 被考察系数:★★★☆☆
题目描述:
分析与解答:
归并排序是利用递归与分治技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思,即递归地将数组折半地分离为单个数组。例如,数组[2,6,1,0]会先折半,分为[2,6]和[1,0]两个子数组,然后再折半将数组分离分为[2],[6]和[1],[0]。“并”就是将分开的数据按照从小到大或者从大到小的顺序再放到一个数组中。如上面的[2]、[6]合并到一个数组中是[2,6],[1]、[0]合并到一个数组中是[0,1],然后再将[2,6]和[0,1]合并到一个数组中即为[0,1,2,6]。
具体而言,归并排序算法的原理如下:对于给定的一组记录(假设共有n个记录),首先将每两个相邻的长度为1的子序列进行归并,得到n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列为止。(www.xing528.com)
所以,归并排序的关键就是两步:第一步,划分子表;第二步,合并半子表。以数组{49,38,65,97,76,13,27}为例(假设要求为升序排列),排序过程如下:
程序示例如下:
程序的输出结果如下:
9 8 7 6 5 4 3 2 1 0
二路归并排序的过程需要进行log2n趟。每一趟归并排序的操作,就是将两个有序子序列进行归并,而每一对有序子序列归并时,记录的比较次数均小于等于记录的移动次数,记录移动的次数均等于文件中记录的个数n,即每一趟归并的时间复杂度为O(n)。因此二路归并排序在最好、最坏和平均情况的时间复杂度为O(nlog2n)。而且是一种稳定的排序方法,空间复杂度为O(1)。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。