【数据结构】排序算法比较及一些总结

本文主要是介绍【数据结构】排序算法比较及一些总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

交换类排序趟数与初始状态有关；
选择、直接插入、折半插入、基数排序与初始状态无关；
序列初始状态基本有序：选用直接插入、冒泡排序；
\(n\) 较小（\(n≤50\)）：用直接插入、简单选择排序；
\(n\) 较大，用 \(O(n\log_2n)\)：快速排序（平均时间最短）、堆排序（辅助空间少于快排的\(O(\log_2n)\)）、归并排序；
稳定 + \(O(n\log_2n)\)：归并排序；
基于比较的排序方法中，当文件的 \(n\) 个关键字随机分布时，任何借助于“比较”的排序，至少需要 \(O(n\log_2n)\) 的时间；
\(n\) 很大 + 关键字位数少且可分辨：基数排序；
记录本身的信息量较大时，可用链表作为存储结构；
堆用于排序，在查找时无需，效率较低；
折半查找只能顺序存储，不能用链式存储；
基数排序 不需要进行记录关键字间的比较；
归并排序的 每趟归并 时间为 \(O(n)\)，整过排序过程为 \(O(n\log_2n)\)，空间复杂度为 \(O(n)\)；
堆排序每趟 \(O(\log_2n)\)，整个排序过程为 \(O(n\log_2n)\)，建堆时间 \(O(n)\)，调整时间 \(O(h)\)（\(h\) 为堆的高度）。

这篇关于【数据结构】排序算法比较及一些总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程