9.10 总结回顾         本章内容只是在讲排序，我们需要对已经提到的各个排序算法进行对比来总结回顾。         首先我们讲了排序的定义，并提到了排序的稳定性，排序稳定对于某些特殊需求来说是至关重要的，因此在排序算法中，我们需要关注此算

9.9.1 快速排序介绍         终于我们的高手要登场了，如果将来你工作后，你的老板要让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。         事实

9.8.3 归并排序复杂度分析         我们来分析一下归并排序的时间复杂度，一趟归并需要将SR[1]～SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]～TR1[n]中，这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行΀

9.8.1 归并排序介绍         前面我们讲了堆排序，因为它用到了完全二叉树，充分利用了完全二叉树的深度是⌊log2n⌋+1的特性，所以效率比较高。不过堆结构的设计本身是比较复杂的，老实说，能想出这样的结构就挺不容易，有没有更直接简单的办法利用完全二叉树来排序呢？当然是有。  

9.7.1 堆结构介绍         我们前面讲到简单选择排序，它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解，查找第一个数据需要比较这么多次正常的，否则如何知道它是最小的记录。         可惜的是，这样的操作并没

9.7.2 堆排序算法         堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就

9.6.3 希尔排序算法         好了，为了能够真正弄明白希尔排序的算法，我们还是老办法——模拟计算机在执行算法时的步骤还研究算法到底是如何进行排序的。         希尔排序算法代码如下。  1&nb

9.6.1 变不可能为可能         给大家出一道智力题。请问“VII”是什么？         嗯，很好，它是罗马数字的7。现在我们要给它加上一笔，让它变成8（VIII），应该是非常简单，只需要在右侧加一竖线即可。 &

9.5.1 直接插入排序算法         扑克牌是我们几乎每个人都可能从事过的游戏。而最基本的扑克玩法都是一边摸牌，一边理牌。假如我们拿到了这样一手牌，如图9-5-1。啊，似乎是同花顺呀，别急，我们得理一理顺序才知道是否是真的同花顺。请问，如果是你，应该如何理牌呢？      &