9.8.3 归并排序复杂度分析 我们来分析一下归并排序的时间复杂度，一趟归并需要将SR[1]～SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]～TR1[n]中，这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行log2n趟，因此，总的时间复杂度为O(nlogn)，而且这是归并排序算法中最好、最坏、平均的时间性能。... [阅读全文]

9.8.1 归并排序介绍 前面我们讲了堆排序，因为它用到了完全二叉树，充分利用了完全二叉树的深度是log2n+1的特性，所以效率比较高。不过堆结构的设计本身是比较复杂的，老实说，能想出这样的结构就挺不容易，有没有更直接简单的办法利用完全二叉树来排序呢？当然是有。 先来举一个例子。你们知道高考一本、二本、专科分数线是如何划分出来的吗？ 简单地说，如果各高校本科专业在某省高三理科学生中计划招收1万... [阅读全文]