【正确答案】归并排序是利用递归与分治技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思,即递归地将数组折半地分离为单个数组。例如,数组[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的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列为止。
所以,归并排序的关键就是两步:第一步,划分子表;第二步,合并半子表。以数组{49,38,65,97,76,13,27}为例(假设要求为升序排列),排序过程如下:
【答案解析】[考点] 如何进行归并排序