首页 > 代码库 > 排序算法比较和选择
排序算法比较和选择
排序算法有不少，当然，一般的语言中都提供某个排序函数，比如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)的排序方法较适宜。
- 如果强调稳定性，则使用归并排序。
参考：《零基础学算法》
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。