本文较为深入地研究了各类基本的排序算法，并由此引伸到对于数据结构的认识。

      怎样选择算法？哪种排序算法最好？要回答这些问题首先要建立在数据特征和对数据的操作要求上，根据不同的数据特征和操作要求选择合适的数据存储结构。

       数据存储结构分类如下：

（1）顺序存储（2）链表结构（3）索引（4）散列表

       对于顺序表和链表，实际应用中又分栈、队列、树、图等。

再回头来看排序算法：

       直插、希尔、直选、堆、冒泡、快排、归并、基数排序。为O(n2)的是直插、直选和冒泡。直选的效率最低，其次是冒泡，直插比较好而且稳定，但是若用在顺序表上会大量挪动记录，插入和删除操作是顺序表上无法克服的弱点。直选和冒泡相比，直选比较的次数较多但是最多交换n-2次，而冒泡交换记录的次数稍微多一点，但是冒泡可改进：采用提前终止位置和交替扫描方向能使冒泡适应复杂多样的数据。但是效率的提升也是有限的，例如我用2万个整数去测试时，基本的冒泡用了2.428秒，设置了flag的用了2.279秒，提前终止位置的用了2.153秒，双向扫描用了1.652秒，相对于快排的零点几秒和堆排序的零点零零几秒，完全不在一个数量级。

       快排速度最快但是不稳定而且只适合顺序表，它用两个指针i、j左右移动，交换较小的元素到基准的前端，交换量取决于数据的初始有序情况，但我估计它的平均交换量小于改进的冒泡排序。快排有一个缺点就是数据越有序，那么它的效率越差，这是因为每次都是选首元素为基准的缘故。现实中有排过序的文件稍微打乱了一下顺序，要再次排序的情况，这时是基本有序，快排就比较吃力。这是就应该改进一下快排算法，取中间元素作为基准，但是又为了避免运气霉，抽到的中间那个元素偏偏是极大或者极小的情况，所以用首、中、尾三者取中作为基准的办法。但是快速排序除了不稳定和只能对顺序表进行排序外，还有一个很大的缺点就是空间开销大，因为它是用递归算法写的，需要在内存中开辟递归栈空间，最坏情况下空间开销为O(n)。当我测试快排的时候遇到了递归栈空间不足的情况，VC默认给栈空间开辟的内存最大为2~8M，我用最原始的快排算法，元素个数约为20W个时递归栈空间就不足了，用首、中、尾三者取中的改进的快排，内存开销更大，大约只能排3万个元素。而且排序的速度上快排并不是最快，要比堆排序慢很多。快速排序的最坏时间复杂度为O(n2)，平均时间复杂度和最坏时间复杂度均为nlg(n)。

       希尔排序其实就是分段的插入排序，定义一个初始增量d，然后依次减小d使得每次直插比较的元素增多，但是d变得越小，也就意味着元素变得越来越有序，就有利于直插排序。其交换量应该还是蛮大的，我估计与改进冒泡的交换量相当或者稍好。

       堆排序是一种树形（完全二叉树）的选择排序，效果非常好，当数据量较大时（比如1000个）比快速排序要快很多，但是也不稳定。由于建初始堆所需要的比较次数较多，所以堆排序不适合记录数较少的情况。堆排序的“最坏时间复杂度”为nlg(n)（由此可见它比快排要快），而且堆排序的空间开销要小于快排。

       总之，若顺序存储，假设存的是长度小于16的字符串，个数为1000或者10W，则用堆排序或者快排，因为如果用希尔排序或者改进的冒泡算法，则要多次挪动或交换数据，拷贝字符串（strcpy）也是要挺大的开销吧？但是如果比较的是数量少于300个，那就用直选吧，因为拷贝量大，不宜用希尔排序和冒泡排序以及快速排序，而且数据量确实很小，用快排好像效率也不算高，但如果比较的不是长度为16的字符串而是简单的4位整数，那显然用希尔排序，移动的数据量不大而且算法又稳定，但如果是4位的小数呢，用基数排序？还是快排、希尔、堆？没试过还真不知道！因为我不知道系统完成2>4?与2.125>2.112?的效率之间的差别，也不知道交换一对整数的值和交换一对实数的值时系统开销的差别，倘若整数之间的比较比实数之间的比较要麻烦很多，而且整数之间的赋值要比实数之间的赋值速度慢、开销大，则也许用基数排序才是王道！否则，类似于上面的16位字符串，用堆排序或者快排！

       对于链表结构，链表本身就有很多学问：是动态链表还是静态链表？是单链表还是双链表？是栈还是队列？是二叉树还是红黑树还是其他神马树甚至图？

       于是乎，在此我们只以完全二叉树为例，则用堆排序较好，也可以用插入排序。如果是双链表则用插入排序吧，如果是其他链表结构，不外乎也是与插入排序和堆排序类似的方法，但是会针对某一种结构优化算法，例如“败者树”“置换-选择排序”神马的！

       综上可知，最没用的是冒泡排序，直选有一点点用处（因为它记录移动次数少），直插（希尔）、快排和堆排序最有用了，特别是堆排序，速度最给力了，其思想适合用在树形结构上，分配排序（基数排序）也许有用，虽然打着O(n)的幌子，但是据我分析，其效率一般不及快排，除非你n上几十亿并且关键字的位数d、箱子的个数rd都很小（否则d*rd会大于lg(n)，lg(n)（2为底的对数）其实是一个很小的数，当n=1000W时，lg(n)才约为23）。而归并排序只是一种多文件归并的方法，实际上还是以内部排序（例如直插）为主，通常（直插+归并）搞定要求排序稳定的大链表文件。

       最后分析一下数据结构，首先要熟练掌握（甚至精通）的是（单/双链表、二叉树，包括在它上面的一些基本操作，必须熟练）。对于排序算法，要熟练掌握（甚至精通）的是（直插、希尔，直选、堆，快排）。补充一点：实际应用中，散列表查找算法是很有用，其O(n)的时间复杂度非常高效，例如输入法，拼音或者五笔，对于查找算法的要求非常苛刻，二叉查找和树查找算法根本达不到要求。