stdsort的优化实现

3 分钟阅读 • 508 字 + 275 词
首先说明快排的partition的pivot的取法
众所周知，快速排序算法的具体时间复杂度取决于递归时数组的分割比例。 比如说，如果我们在每个递归中都能将数组分成均等的两份，那么算法的时间复杂度将是最佳的O(nlogn) ；而 如果我们在每个递归中都倒霉地把数组分成大小1和大小n-1这样的两份 ， 快速排序就退化成了递归版的冒泡排序，时间复杂度为O(n^2)。
比较好的选择： 三数取中法，即取三个元素（一般是第一个、最后一个和中间的元素）的中间值
元素数量较小的数组对快排不友好，此时快排需要开栈递归，选pivot，分数组，所以不划算，当元素数量较小时，可以直接用插入排序。
还可以 使用预排序检查 ，在实践中，大部分数组经常出现有序片段，所以这个优化有不错的提升
当元素个数小于16的时候，使用插入排序。
或者超过了最大递归深度，采用堆排序
否则使用快排
具体步骤：
  1. 初始化：设置递归深度限制2*log2n，元素分区大小阈值10~16
  2. 如果数组大小大于等于阈值，且递归深度没有达到限制，使用快排
    1. 快排平均为O(n*log2n)，但是最坏会退化到O(n^2)，最坏情况为已经排序或者接近排序的情况
    2. 快排是不稳定的排序
  3. 如果数组大小小于阈值，则使用插入排序
    1. 在 数据规模较小 ，且 相对有序 的情况下，插入排序在最好情况下比较高效(O(n))
    2. 插入排序是稳定的排序
  4. 如果数组大小大于等于阈值，且递归深度达到限制，使用堆排序
    1. 堆排序的时间复杂度是O(n*log2n)
所以std::sort是不是稳定的排序算法？
数据量小是的
数据量大不是的

目录