【数据结构】排序 归并排序和基数排序
1.归并排序
归并排序中的"归并"的意义就是把多个有序表合并为一个新的有序表。
算法思想：
二路归并排序：初始情况下将长度为n的待排序表分为n个子表，则每个子表的长度为1，是有序的。每趟排序尽量将这些子表按位置相邻两两归并，重复直到合并为一个长度为n的有序表为止。
具体实现：
在归并排序的实现过程中必须要用到一个辅助数组。
代码解释：
归并排序的算法过程是基于分治法实现的，先利用递归将整个表的归并排序分治为最基本的长度为1的表的归并排序，然后不断进行合并。
性能分析：
在这里分析2路归并排序算法
空间效率：O(n)，需要用到辅助数组B
时间效率：每趟归并的时间复杂度为O(n),共进行⌈ log2n⌉趟归并，所以算法的时间复杂度为O(nlog2n)
稳定性：2路归并排序是稳定的排序算法。
2.基数排序
基数排序是一种特殊的算法，其运行机制是基于关键字各数位的大小进行排序。
是一种借助多关键字排序的思想对单逻辑关键字进行排序的算法。
算法思想：
基数排序的算法思想可以概括为从低位到高位一次进行计数排序。
实现过程：