《数据结构与算法-王争》学习笔记,记录备查

各排序算法情况:

快速排序的优化

快速排序,时间复杂度在 O(nlogn) 和 O(n^2)之间。在极坏的情况的,时间复杂度会退化为O(n^2)。这种 O(n2) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。

最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。

两种选择分区点的方法:

  • 三数取中法 取首、尾、中间,分别取出一个数,然后对比大小,取这3个数的中间值作为分区点。如果排序的数组比较大,则可以采用“五数取中” “十数取中”。

  • 随机法 随机法就是每次从要排序的区间中,随机选择一个元素作为分区点。