Skip to content

Latest commit

 

History

History
34 lines (23 loc) · 1.64 KB

chose_sort_algorithm.md

File metadata and controls

34 lines (23 loc) · 1.64 KB

#排序算法比较和选择

排序算法有不少,当然,一般的语言中都提供某个排序函数,比如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)的排序方法较适宜。
  • 如果强调稳定性,则使用归并排序。