归并排序

基本思想

基于归并的思想，归并即将两个或两个以上的有序表组合成一个新的有序表。
归并排序：用归并的方法进行排序。

2-路归并的算法思想

建设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。
两两归并，得到 n/2 个长度为2或1的有序子序列。
再两两归并，如此重复，直至得到一个长度为n的有序序列为止。

一次归并法

将两个有序子序列
r1[low…mid] r1[mid+1…high]
归并为一个有序序列，存入
r2[low…high]

归并排序的递归实现

将r1[]前半段排序放入r2[]的前半段
将r1[]后半段排序放入r2[]的后半段
归并r2[]的前半段和后半段存入r3[]

算法特点

时间复杂度O(nlog2n)
是一种稳定的排序方法
时间效率高，但空间效率低
适用于n较大的情况

基数排序

插入排序、选择排序、交换排序、归并排序，都是利用比较和交换关键字值两种操作实现的。

基数排序

基排序则是利用分配和收集两种基本操作实现。是一种按记录关键字的各位值逐步进行排序的一种方法。
基数排序属于“低位优先”排序法。排序时先按最低位排序，再按次最低位排序，依次进行，直至按最高位排序。
每趟排序进行一次分配和收集操作。