分类

        排序算法             时间复杂度           是否基于比较            是否稳定排序        是否原地排序

        冒泡                     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.随机法

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

        快排缺陷&解决方案

            快速排序是用递归来实现的。递归要警惕堆栈溢出，我们有两种解决办法：

            第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归

            第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制