常见排序方式的效率对比

我们之前介绍了多种排序算法,它们到底谁效率较高我们是前文介绍了用事前统计法统计了一下,他们的时间复杂度和空间复杂度情况如下表表示。

排序算法 平均时间复杂度 最坏时间复杂度 平均空间复杂度 稳定性
选择排序 O(n2) O(n2) O(1) 不稳定
冒泡排序 O(n2) O(n2) O(1) 稳定
直接插入排序 O(n2) O(n2) O(1) 稳定
希尔排序 O(nlogn) O(n2) O(log2n) 不稳定
快速排序 O(nlogn) O(n2) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(n) 稳定

可以看出,上面这些算法平均时间、最坏时间、平均空间的复杂度根据传递进来的数据不同都有可能会变化,而唯一与他们不同而且效率较快的就是堆排序,因为堆排序总是将所有的操作数依次放入堆然后再依次从堆中读取出来,所用的步骤是一样的多的,所以时间复杂度不会根据数据的顺序不同而变化。下面代码演示了不同算法对20000个数进行排序的效率结果。

2015-06-12_145414

评论