如何实现一个通用的、高性能的排序函数？

• 选择合适的排序算法

  • 如下, 首先线性排序只适用于特殊场景, 排除; 因此要优先选择时间复杂度为**

    $$ O(n^2) $$

    或

    $$ O(nlogn) $$

    **的算法

  • 归并排序虽然时间复杂度是**

    $$ O(nlogn) $$

    *, 但空间复杂度是O(n), 所以实际情况下快排用的更多 快排优化: 合理选择分区点, 三数取中法, 随机法

    • 快排避免递归堆栈溢出, 可以限制递归深度, 或是在推上模拟实现一个函数调用栈, 手动模拟压栈出栈

• 牛人的评论, Java的Arrays.sort:
  • java1.8中的排序，在元素小于47的时候用插入排序，大于47小于286用双轴快排，大于286用timsort归并排序，并在timesort中记录数据的连续的有序段的的位置，若有序段太多，也就是说数据近乎乱序，则用双轴快排，当然快排的递归调用的过程中，若排序的子数组数据数量小，用插入排序