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

各排序算法情况：

快速排序的优化

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

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

两种选择分区点的方法：

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

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