外观
约 263 字小于 1 分钟
数据结构与算法排序
2023-09-08
《数据结构与算法-王争》学习笔记,记录备查
各排序算法情况:
快速排序,时间复杂度在 O(nlogn) 和 O(n2)之间。在极坏的情况的,时间复杂度会退化为O(n2)。这种 O(n2) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。
最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。
两种选择分区点的方法:
三数取中法 取首、尾、中间,分别取出一个数,然后对比大小,取这3个数的中间值作为分区点。如果排序的数组比较大,则可以采用“五数取中” “十数取中”。
随机法 随机法就是每次从要排序的区间中,随机选择一个元素作为分区点。
版权归属:pylixm
许可证:署名 4.0 国际 (CC-BY-4.0)