博客首页 » Arch Java数据结构与算法 - 高级排序
发布于 23 Jul 2015 15:09
标签 blog
高级排序算法有希尔排序和快速排序。
希尔排序 Shell Sort
插入排序的问题在于移动(复制)数据次数过多。如果能让调换的数据一次就接近应该的位置,就可以避免大量的移动(复制)操作。
对于每隔h个数的子数列执行插入排序,得到若干个有序的字数列。再对间隔更小的子数列执行插入排序,直到间隔为1。最后得到完全排序完成的结果。
h = 3*h + 1
希尔排序算法效率在不同的输入下有不同的效率。基本稳定在 N*(logN)^2
快速排序
通过分区,不断把数列对于某个数分成大小两个分区;对于每一个分区,再不断重复这一过程,直至分区大小为1,或者足够小的时候,用其他排序方法解决。
分区的枢纽pivot可以取任一值,也可以通过抽取多个数字取均值而定。
快速排序算法效率 N*logN
对于很短的数列效率不明显。
本页面的文字允许在知识共享 署名-相同方式共享 3.0协议和GNU自由文档许可证下修改和再使用,仅有一个特殊要求,请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。
系列文章
文章列表
- Arch Java数据结构与算法 - 高级排序
这篇文章对你有帮助吗,投个票吧?
留下你的评论