算法与数据结构 --- 排序 --- 归并排序，基数排序以及总结

第一部分 --- 归并排序

 

1.归并排序一次归并只能够归并两个相邻的有序子序列

2.归并排序的整个过程就是一棵倒着的树（如上），我们将这棵树称为归并树，树的层数就是我们进行归并操作的总趟数 --- 设完全二叉树的最后一层层数为K，则这一层的最大容量为 2的K-1次方，在归并排序中我们是已知完全二叉树的最后一层的最大元素总数的（就是我们要排序的元素总数），自然就能够得到树的最后一层层数，也就能得到总比较趟数了

3.如果说要对奇数个元素进行排序的话，我们需要先将两个相邻的元素进行归，使得等待归并排序的总子序列为偶数个，然后再开始正式对所有子序列进行归并排序

答案就是我们之前学过的双指针法：分别用两个指针指向两个有序序列的第一个元素（假设都是从小到大有序），比较两个元素谁更小，将较小的元素存到新的数组中，然后将指向这个较小元素的指针++，接着继续比较

直到两个序列或者是某个序列所有元素都比较完毕时停止比较，如果存在序列还有剩余元素