[Arch] Java数据结构与算法 - 高级排序

博客首页 » 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数据结构与算法 - 高级排序

这篇文章对你有帮助吗,投个票吧?

rating: 0+x

留下你的评论

Add a New Comment