目前给大家介绍过了6种排序冒泡排序选择排序 插入排序希尔排序归并排序快速排序，并且在上期讲 快速排续 时给出了快排的优化方案对于大数据集排序先使用 快排 ，当分区达到一定小的时候使用 插入排序 ，有同学就有疑惑为什么当分区达到一定小时要用 插入排序 ，这样真的会变快吗。

随机选择快速排序是一种比较常见的优化快速排序的方法，即随机选取一个元素作为主元，而不是像普通快速排序那样选取第一个元素作为主元，这种情况下虽然最坏情况仍然是On^2，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳实际上，随机化快速排序得到理论最坏情况的可能性仅为12^n。

然而，快速排序在最坏情况下的时间复杂度为On^2，这种情况通常发生在输入的数组已经有序或者接近有序的情况下为了避免这种情况，可以通过一些优化手段来提高算法的效率，例如随机化分区函数或者使用三数取中法来选择分区点快速排序优势1高效快速快速排序的时间复杂度通常为Onlogn，在大。

快速排序的优化主要在于基准数的选取 快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定 前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定 具体步骤，设。

希尔排序是对插入排序的优化希尔排序的思想先使用数组中任间隔为h的元素有序，然后对全局进行排序h该怎么取值呢如果数组长度比较小，则可设置 h=3，h=1若数组长度比较大，可以取 h=4，但最终还是得对全局进行排序h=1但如果数组很长呢则可以设置 h=10，h=4，h=1那如果再来一。