我正在观看 Robert Sedgwick 关于算法的讲座视频，他解释说随机改组确保我们不会在快速排序中遇到最坏的二次时间场景。但我无法理解。
最佳答案
这确实是一种承认，虽然我们经常谈论平均案例复杂度，但实际上我们并不期望每个案例都以相同的概率出现。
对一个已经排序的数组进行排序是快速排序中最糟糕的情况，因为每当你选择一个主元时，你会发现所有元素都被放置在主元的同一侧，所以你根本不会分成大致相等的两半.通常在实践中，这种已经分类的情况会比其他情况更频繁地出现。
首先随机打乱数据是一种快速的方法，可以确保您确实最终以相同的概率出现所有情况，因此这种最坏的情况与其他情况一样罕见。
值得注意的是，还有其他策略可以很好地处理已排序的数据，例如选择中间元素作为基准。
关于algorithm - 快速排序中的随机改组如何帮助提高代码效率？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27645471/