关于快速排序性能的疑问

[数据结构堆排序算法]#includevoid adjust(int *list,const int root,const int n); void HeapSort(int *list,const int n) { int i=0; for(i=n/2;i>=1;i--) adjust(list,i-1,n); int t=list[n]...+阅读

当然是递归，重复调用函数的开销并不会很大，待排序数组，元素为int型，元素大小为0-100k之间的随机数，初始状态无序 1：系统排序函数 100k个数据秒过，1000k个数据 0.125秒，10000k个数据1.25秒 2：冒泡排序 100k个数据 21秒 3：选择排序 100k个数据 10秒 4：插入排序 100k个数据 5秒 5：希尔排序 100k个数据秒过，1000k个数据 0.3秒，10000k个数据 4.5秒 6：希尔排序（位运算） 100k个数据秒过，1000k个数据 0.3秒，10000k个数据 3.7秒 7：归并排序 100k个数据 1.2秒 8：快速排序（0点起）100k个数据秒过，1000k个数据 0.156秒，10000k个数据 2.047秒 9：快速排序（0点起，位运算）100k个数据秒过，1000k个数据0.141秒，10000个数据 1.5秒 10：堆排序 100k个数据秒过，1000k个数据 0.3秒，10000k个数据 6秒 11：基数排序（字符运算）100k个数据秒过，1000k个数据0.312秒，10000k个数据 1.781秒 12：基数排序（位运算）100k个数据秒过，1000k个数据0.06秒，10000k个数据 0.6秒 13：鸽巢排序 10000k个数据 0.05秒

系统的快速排序是随机化快速排序，所以速度稍微快一点，不过我自己写的指定0起点的快速排序，在10000k个数据的时候只比系统快速排序慢了0.25秒而已，应该不算是性能变差了吧这是我做的各种排序的比较结果，所有排序都是我自己写的，自认为都已经优化到了极点了。所以我这个数据应该有参考价值排序算法比较总结

（1）冒泡排序作为排序的始祖有着不可磨灭的光辉，但是随着时代的进步，这种最简洁的代码执行效率已经无法满足时代的要求。

（2）选择排序作为一个算法进步的过渡产物，比冒泡排序的执行速度快上一倍，已经是一个相当大的进步。但是由于是不稳定排序，所以实用价值稍微降低了一些。

（3）插入排序作为一个崭新的排序思想，还是值得表扬的，四倍于冒泡排序的效率，让它在排序算法界分得了一杯羹。

（4）归并排序这种采用分治思想的排序是稳定排序算法的历史转折点，十倍于冒泡算法的执行效率带给他一度的辉煌。

（5）堆排序倚靠优秀的二分法遍历数组，比较和交换次数都随着数据的增多成几何次方减少，是在数据量非常大且不需求数据稳定性的时候的一个不错的选择。

（6）希尔排序作为插入排序的改良版，绝对是产生了质的飞跃，比插入排序的执行效率提高了三百多倍。即便如此，跟更优秀的算法相比，还是相差甚远。

（7）快速排序不愧为经验证明相当快的排序算法，甚至有句名言叫做“随机化快速排序可以满足一个人一辈子的人品需求。”，以至于微软将快速排序列入了官方函数库，比冒泡排序快一千四百倍的速度，让它拥有不可撼动的地位。

（8）基数排序又称捅排序，而且是稳定排序，由于它没有任何数据的比较，所以执行速度会明显高于一切比较排序算法，虽然快速排序的速度已经达到了冒泡排序的一千四百被，但是基数排序比起快速排序，仍然能再快3.3倍以上，使用基数排序绝对会让你觉得对得起你付出的每一行代码。

（9）鸽巢排序和基数排序一样是稳定排序且没有任何数据的比较，各种教程中说它很少可以在灵活性，简便性，尤是速度上超过其他排序算法，但是经过实践的证明，鸽巢排序不会出现任何最坏的情况，而且在对于【大体正序】、【大体逆序】、【无序】普遍情况来说，可以比基数排序再快十倍以上，绝对是排序算法王道中的王道。