CSort机制快排插排堆排快速排序回顾总思想随便取一个元素为枢轴通过一系列操作将枢轴左边元素小于枢轴右边大于枢轴然后递归处理左右一般取开头结尾中间随机等使用pivot暂存枢轴元素然后用双指针进行一次操作使得枢轴左边元素小于本身右边大于本身时间复杂度O(n)空间复杂度O(1)处理完一遍后递归的处理枢轴左边和右边的元素快速排序不稳定不严格排序的情况下最好的情况O(nlogn)时间和(logn)空间复杂度最坏O(n^2)时间和O(n)辅助空间堆排序回顾堆一个完全二叉树大顶堆任意一个结点左右孩子根为最大值小顶堆任意一个结点左右孩子根为最小值由于是完全二叉树非常适合用顺序存储下标1开始方便计算建堆假设一共有n个结点那么从[n/2]开始倒着遍历遍历的元素检查并下沉保证遍历到每个结点的时候它的子树已经是堆下沉如果此结点A存在比它大的子结点则在左右之间找出最大的结点和A交换追踪这个A继续判断它是否其子结点若是则退出循环否则重复上述操作一次排序/取值取出堆顶根元素/堆顶元素放到最后然后将最后一个元素放到堆顶根然后进行下沉操作或者说堆顶元素和末尾元素交换接着下沉堆顶元素然后隐藏末尾元素时间复杂度建堆O(n)每次下沉是O(logn)全部取完是(nlogn)总体排序是O(nlogn)空间复杂度O(1)不稳定不严格序列不保证相同大小元素的相对位置不变CSort方法使用分治的方式进行sort以尽可能的高效的完成所有的排序主体仍是快速排序先以快速排序的方式不断二分区间。递归深度超限时切换为堆排序当某次递归深度超过2 * log2(N)时说明快速排序有退化为 O(N²) 的风险于是把这个子区间交给堆排序来处理保证整体最坏时间复杂度稳定在 O(N·logN)。小区间留给最后的插入排序当子区间长度 ≤_S_threshold时暂时不对其排序而是留到最后——整个数组大部分元素已经“接近有序”这时再做一次插入排序就能以 O(N) 级别的代价完成收尾最终得到完全有序的结果。libstdc 中**_S_threshold**取 16sort八股