排序算法性能分析

微软技术部 2007 年秋季招新技术部大二以上笔试题 071323 李启磊 一． （50 分）比较，冒泡排序，选择排序，插入排序，希尔排序，快速排序的性能和特点，说说你能从这里发现什么。 要求： 1. 能给出性能从小到大的顺序 2. 能对你给出的顺序一个合理的解释 在不同的应用环境和要求下，不同的排序算法有不同的表现，因此不能笼统的说哪种算法优或劣。 冒泡排序、插入排序、希尔排序以及快速排序对数据的有序性比较敏感，尤其是冒泡排序和插入排序；相比而言，选择排序不关心表的初始次序，它的最坏情况的排序时间与其最佳情况没多少区别，其比较次数为)1(21nn，但选择排序可以非常有效的移动元素。因此对次序近乎正确的表，选择排序可能比插入排序慢很多。冒泡排序在最优情况下只需要经过n-1次比较即可得出结果（即对于完全正序的表），最坏情况下也要进行)1(21nn次比较，与选择排序的比较次数相同，但数据交换的次数要多余选择排序，因为选择排序的数据交换次数顶多为1n，而冒泡排序最坏情况下的数据交换 )1(21nn。冒泡排序不一定要进行1n趟，但由于它的记录移动次数较多，所以它的平均时间性能比插入排序要差一些。插入排序在最好的情况下有最少的比较次数1n，但是它在元素移动方面效率非常低下，因为它只与毗邻的元素进行比较，效率比较低。希尔排序实际上是预处理阶段优化后的插入排序，一般而言，在 n 比较大时，希尔排序要明显优于插入排序。快速排序采用的“大事化小，小事化了”的思想，用递归的方法，将原问题分解成若干规模较小但与原问题相似的子问题进行求解。快速算法的平均时间复杂度为)lg(0nn，平均而言，快速排序是基于关键字比较的内部排序算法中速度最快者；但是由于快速排序采用的是递归的方法，因此当序列的长度比较大时，对系统栈占用会比较多。快速算法尤其适用于随机序列的排序。 因此，平均而言，对于一般的随机序列顺序表而言，上述几种排序算法性能从低到高的顺序大致为：冒泡排序、插入排序、选择排序、希尔排序、快速排序。但这个优劣顺序不是绝对的，在不同的情况下，甚至可能出现完全的性能逆转。 对于序列初始状态基本有正序，可选择对有序性较敏感的如插入排序、冒泡排序、选择排序等方法。 对于序列长度 n 比较大的随机序列，应选择平均时间复杂度较小的快速排序方法。 各种排序算法都有各自的优缺点，适应于不同的应用环境，因此在选择一种排序算法解决实际问题之前，应当先分...