排序优化

Tuesday, April 23, 2019

如何选择合适的排序算法

file

  • 线性排序场景比较特殊,如果要选择通用排序,不能选择限行排序。
  • 小规模数据排序,可以选择时间复杂度为o(n^2)的排序算法
  • O(ologn)的排序算法有快排,归并排序,堆排,但是归并排序用的很少,因为归并排序内存占用要翻倍。

如何优化快排

如果数据原来就有序或者接近有序,每次分区都选择最后一个数据,快排时间复杂度会退化为O(n^2),出现这种情况主要原因是分区点选择的不够合理。

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

三数取中法

  • 从区间头,中,尾各取一个数,对比大小,选中间的值作为分区点。

随机法

  • 随机选取一个元素作为分区点

分析Glibc的qsort()方法

  • qsort()会优先使用归并排序,因为数据量小的时候,即使内存占用翻倍,也不影响,属于典型的空间换时间技巧。
  • 数据量大的时候,qsort()会用快排,且选择分区点用的是“三数取中法”。
  • 当要排序的区间中,元素个数小于4时,会退化为插入排序,不再继续用递归来做快排。
  • 小规模数据时,O(n^2)并不一定比O(nlogn)执行时间长,因为在大O复杂度里,我们会省略低阶,系数和常数,比如O(knlogn + c),而k和c有可能是比较大的数,这种情况,n^2的值实际比knlogn + c 还要小。
数据结构-算法

二分查找(上)

线性排序