快速排序中的随机改组如何帮助提高代码效率？ [英] How does random shuffling in quick sort help in increasing the efficiency of the code?

问题描述

我正在看Robert Sedgwick讲演算法的视频，他解释说随机混洗可以确保我们不会快速遇到最坏的二次时间场景。

I was going through lecture videos by Robert Sedgwick on algorithms, and he explains that random shuffling ensures we don't get to encounter the worst case quadratic time scenario in quick sort. But I am unable to understand how.

推荐答案

虽然我们经常谈论平均用例复杂度，实际上我们并不希望每种情况都以相同的概率出现。

It's really an admission that although we often talk about average case complexity, we don't in practice expect every case to turn up with the same probability.

对已排序的数组进行排序在quicksort中是最坏的情况，因为无论何时您选择一个枢轴，您会发现所有元素都放置在枢轴的同一侧，因此根本不会分成两个大致相等的两半。通常，在实践中，这种已经排序的案例比其他案例更经常出现。

Sorting an already sorted array is worst case in quicksort, because whenever you pick a pivot, you discover that all the elements get placed on the same side of the pivot, so you don't split into two roughly equal halves at all. And often in practice this already sorted case will turn up more often than other cases.

首先随机整理数据是确保最终得到结果的快速方法所有情况均以相同的概率出现，因此这种最坏情况将与其他任何情况一样罕见。

Randomly shuffling the data first is a quick way of ensuring that you really do end up with all cases turning up with equal probability, and therefore that this worst case will be as rare as any other case.

值得注意的是，还有其他一些策略可以很好地应对已经排序的数据，例如选择中间元素作为枢轴。

It's worth noting that there are other strategies that deal well with already sorted data, such as choosing the middle element as the pivot.

这篇关于快速排序中的随机改组如何帮助提高代码效率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！