在快速排序中使用中位数选择？

Question

我对Quicksort有一个小问题.在选择阵列的最小值或最大值的情况下,分区的枢轴值非常低效,因为阵列大小仅减小1.

但是,如果我添加选择该数组中值的代码,我认为Ii会更有效率.由于分区算法已经是O(N),因此它将给出O(N log N)算法.

可以这样做吗？

Answer 1

您绝对可以使用线性时间中值选择算法来计算快速排序中的数据透视.这为您提供了最坏情况的O(n log n)排序算法.

然而,线性时间选择的常数因子往往是如此之高,以至于在实践中,所得到的算法将比在每次迭代中随机选择枢轴的快速排序慢得多.因此,看到这样的实现并不常见.

避免O(n ²)最坏情况的一种完全不同的方法是使用类似于introsort的方法.该算法监视快速排序的递归深度.如果算法似乎开始退化,它会切换到不同的排序算法(通常是heapsort),并保证最坏情况为O(n log n).这使得整体算法O(n log n)没有显着降低性能.

希望这可以帮助!