各个排序算法间的比较

如何优化快速排序

1. 快速排序的最坏时间复杂度是 O（n^2），出现最坏时间复杂度的原因是分区点选择的不够合理
2. 最理想的分区点：被分区点分开的两个分区中，数据的数量差不多
   • 比较常见的分区算法
     1. 三数取中法
        • 取区间的首、尾、中间 三个数的中间值作为分区点
        • 如果排序的数组比较大，“三数取中法”可能不够，需要“五数取中”或者“十数取中”
     2. 随机法
        • 每次从要排序的区间中，随机选择一个元素作为分区点
   • 快速排序使用递归实现，要警惕堆栈溢出
     1. 限制递归深度，一旦递归过深，停止递归
     2. 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程