博客首页 » 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自由文档许可证下修改和再使用，仅有一个特殊要求，请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。

系列文章

文章列表

这篇文章对你有帮助吗，投个票吧？