排序算法比较和选择

排序算法有不少,当然,一般的语言中都提供某个排序函数,比如Python中,对list进行排序,可以使用sorted(或者list.sort()),关于这方面的使用,在我的github代码库algorithm中有几个举例,有兴趣的看官可以去那里看看(顺便告知,我在Github中的账号是qiwsir,欢迎follow me)。但是,在某些情况下,语言中提供的排序方法或许不适合,必须选择某种排序算法。

这里整理一些排序算法的比较,供看官参考。

计算复杂度比较

名称平均速度最坏情况
冒泡排序法O(n^2)O(n^2)
快速排序法O(nlogn)O(n^2
选择排序O(n^2)O(n^2)
堆排序O(nlogn)O(nlogn)
插入排序O(n^2)O(n^2)
希尔排序O(n^3/2)O(n^2)
归并排序O(nlogn)O(nlogn)

系统资源占用比较

上述各个方法中,除了归并排序,只需要使用1个元素的临时存储单元,用于交换数据。归并排序则需要n个元素的存储单元,用来保存多遍合并操作。

稳定度比较

冒泡、插入、归并三种方法稳定性较好,其余稍逊。

如何选择排序法

没有哪一种排序方法是全面胜出的,只有根据具体具体情况选择了。一般下面的原则可以考虑:

  • 当数据为正序时,尽可能用冒泡、插入、快速方法
  • 如果n值较小(不超过50,但也要根据硬件状况确定),可以采用插入、选择排序。插入排序对小数量较为适用。
  • 如果n值较大,采用时间O(nlogn)的排序方法较适宜。
  • 如果强调稳定性,则使用归并排序。