分类
排序算法 时间复杂度 是否基于比较 是否稳定排序 是否原地排序
冒泡 O(n^2) 是 是 是
插入 O(n^2) 是 是 是
选择 O(n^2) 是 否 是
快排 O(n*logn) 是 否 是
归并 O(n*logn) 是 是 否
桶 O(n) 否 是 否
计数 O(n+k) k是数据范围 否 是 否
基数 O(k*n) k是维度 否 是 否
实现通用、高效排序算法
线性排序算法时间复杂度低,但是适用场景比较特殊,无法通用
小规模数据进行排序,可以选择时间复杂度为O(n2)
大规模数据进行排序，时间复杂度至少应该是O(nlogn)的算法
综上，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数
时间复杂度是O(nlogn)的排序算法:快排、归并、堆
归并排序: 最好/最坏/平均时间复杂度都为O(nlogn)，但是因为空间复杂度为O(n)，额外消耗内存过大，所以不推荐
所以最推荐为快排，但是快排最坏时间复杂度为O(n2)，如何避免复杂度恶化的问题?
这种O(n2)时间复杂度出现的主要原因还是因为我们分区点选的不够合理
最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
常见、简单分区算法
1.三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这3个数的中间值作为分区点
如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”
2.随机法
每次从要排序的区间中，随机选择一个元素作为分区点
快排缺陷&解决方案
快速排序是用递归来实现的。递归要警惕堆栈溢出，我们有两种解决办法：
第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归
第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制
