说明：本章不同于其他章，需要记忆的东西比较多，下面做一下小结，以方便考生记忆。

1.复杂度总结

（1）时间复杂度

平均情况下，快速排序、希尔排序（复杂度了解即可）、归并排序和堆排序的时间复杂度均为O（nlog₂n），其他都是O（n²）。一个特殊的是基数排序，其时间复杂度为O（d（n+r_d））。

最坏情况下，快速排序的时间复杂度为O（n²），其他都和平均情况下相同。

故事助记：如军训时，教官说：“快些以nlog₂n的速度归队。”其中，“快”指快速排序，“些”指希尔排序（发音近似），“归”指归并排序，“队”指堆排序（谐音），这4种排序的平均复杂度都是O（nlog₂n）。

（2）空间复杂度

记住几个特殊的就好，快速排序为O（log₂n），归并排序为O（n），基数排序为O（r_d），其他都是O（1）。

（3）其他

直接插容易插变成O（n），起泡起得好变成O（n），所谓“容易插”或“起得好”都是指初始序列已经有序。

2.算法稳定性总结

一句话记忆：“考研复习痛苦啊，情绪不稳定，快些选一堆好友来聊天吧”。

这里，“快”指快速排序，“些”指希尔排序，“选”指简单选择排序，“堆”指堆排序，这4种是不稳定的，其他自然都是稳定的。(www.daowen.com)

注意：关于简单选择排序，按照本书的算法（同时也是绝大多数学校在考研数据结构中所使用的算法）来实现，一定是不稳定的。例如，对于序列“4（1）、3、4（2）、1、5”进行简单选择排序，括号中标出了相同关键字的前后顺序，第一趟选出1为当前最小值，与4（1）交换，得到的序列为1、3、4（2）、4（1）、5，显然是不稳定的。如果把交换操作换成插入操作，即每次选出的最小值都插入到已排好的有序序列尾部，则此算法变成了稳定的。

由此可见，简单选择排序算法有两个版本——交换版和插入版。在以数组为关键字载体的情况下，显然用交换版比较合适，因为在数组上执行插入操作需要移动大量关键字；而对于以链表为关键字载体的情况，用插入版就比较合适，且能得到稳定的结果。

对于简单选择排序，在考研数据结构中出现最多的在于对其算法稳定性的考察。在题目没有明确说明以链表为关键字载体且没有说明算法具体执行流程的情况下，答案都应该是不稳定的。

3.其他细节（与排序原理有关）

1）经过一趟排序，能够保证一个关键字到达最终位置，这样的排序是交换类的那两种（起泡、快速）和选择类的那两种（简单选择、堆）。

2）排序算法的关键字比较次数和原始序列无关——简单选择排序和折半插入排序。

3）排序算法的排序趟数和原始序列有关——交换类的排序。

4.再次比较一下直接插入排序和折半插入排序

二者最大的区别在于查找插入位置的方式不同。直接插入按顺序查找的方式，而折半插入按折半查找的方式。这里将排序和查找两章的内容结合，大家在复习时也应该融会贯通，计算机的知识都是相通的。

5.一个有用的结论

借助于“比较”进行排序的算法，在最坏情况下的时间复杂度至少为O（nlog₂n）。