Tag Archives: 归并排序

归并排序

归并排序算法是典型的分治算法,对于规模较大的问题,可以分解成若干容易求解的简单的问题,最后把解合并构成初始问题的解。不存在跳跃比较,所以归并排序是一种稳定的排序算法。比较占用内存,效率高且稳定。

基本思想:假设初始序列有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2](上括号,不小于它的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,称为2路归并排序。 Continue reading