常用排序算法有哪些?
时间：2010-08-31
来源：互联网
大哥大姐各位好,我有个问题请教诸位。
常用的排序算法有哪些?我买的书上堆排序都没有...,谢谢大家。
作者: alleva 发布时间: 2010-08-31
O(nlogn)：快排，归并排序，堆排序
O(n^2):冒泡排序，选择排序，插入排序
O(n):基数排序，桶排序
以上的是按照平均时间复杂度分的
此外希尔排序的不好定，因为根据步长不同有所差异，比如如果是n/2^i步长的是O(n^2)，2^k − 1的是O(n^1.5)，如果是以2^i和3^i的据说是O(n(logn)^2)，目前发现最好的步长序列是1，4，10，23，57，132，301，701，1750，…
O(n^2):冒泡排序，选择排序，插入排序
O(n):基数排序，桶排序
以上的是按照平均时间复杂度分的
此外希尔排序的不好定，因为根据步长不同有所差异，比如如果是n/2^i步长的是O(n^2)，2^k − 1的是O(n^1.5)，如果是以2^i和3^i的据说是O(n(logn)^2)，目前发现最好的步长序列是1，4，10，23，57，132，301，701，1750，…
作者: daybreakcx 发布时间: 2010-08-31
QUOTE:
O(nlogn)：快排，归并排序，堆排序
O(n^2):冒泡排序，选择排序，插入排序
O(n):基数排序，桶排序
以上的 ...
daybreakcx 发表于 2010-08-31 16:38
O(n^2):冒泡排序，选择排序，插入排序
O(n):基数排序，桶排序
以上的 ...
daybreakcx 发表于 2010-08-31 16:38
就7种吗？
作者: alleva 发布时间: 2010-08-31
上头有点打错了，希尔排序第三个应该是2^i*3^j的时候是O(n(logn)^2)，此外利用公式9*4^i-9*2^i+1或者4^i-3*2^i+1能达到O(n^(4/3))的复杂度。
此外传说中有用斐波那契数列来生成的在数据量大的时候效果很好：
0，1，1，2，3，5，8，13，...
去掉0，1后的5^0.5+1次方：
1, 9, 34, 182, 836, 4025, ...
这种步长
此外传说中有用斐波那契数列来生成的在数据量大的时候效果很好：
0，1，1，2，3，5，8，13，...
去掉0，1后的5^0.5+1次方：
1, 9, 34, 182, 836, 4025, ...
这种步长
作者: daybreakcx 发布时间: 2010-08-31
回复 alleva
不是说就7种，至少这些是比较常用的，排序很多的，针对性也很强，不过这几种是常见的内存中数据的排序方法
不是说就7种，至少这些是比较常用的，排序很多的，针对性也很强，不过这几种是常见的内存中数据的排序方法
作者: daybreakcx 发布时间: 2010-08-31
哦谢谢大哥。
作者: alleva 发布时间: 2010-08-31
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读：74
-
如何安装mysql8.0
阅读：31
-
Word快速设置标题样式步骤详解
阅读：28
-
20+道必知必会的Vue面试题（附答案解析）
阅读：37
-
HTML如何制作表单
阅读：22
-
百词斩可以改天数吗？当然可以，4个步骤轻松修改天数！
阅读：31
-
ET文件格式和XLS格式文件之间如何转化？
阅读：24
-
react和vue的区别及优缺点是什么
阅读：121
-
支付宝人脸识别如何关闭?
阅读：21
-
腾讯微云怎么修改照片或视频备份路径?
阅读：28
