Par*_*dey 11 sorting algorithm shuffle
我正在阅读Robert Sedgwick关于算法的讲座视频,他解释说随机改组确保我们不会遇到快速排序中最坏情况的二次时间场景.但我无法理解如何.
chi*_*ity 15
这是一个承认,尽管我们经常谈论平均案例复杂性,但我们实际上并不认为每个案例都会以相同的概率出现.
在快速排序中对已经排序的数组进行排序是最坏的情况,因为每当您选择一个数据透视图时,您会发现所有元素都放置在数据透视图的同一侧,因此您根本不会分成两个大致相等的一半.而且在实践中,这种已经分类的案例会比其他案例更频繁地出现.
首先随机地改组数据是一种快速的方法,可以确保您确实最终以相同的概率出现所有情况,因此这种最坏的情况将与其他情况一样罕见.
值得注意的是,还有其他策略可以很好地处理已排序的数据,例如选择中间元素作为支点.
假设最糟糕的情况 - 一切已经排序 - 经常值得担心,并且洗牌是一种黑魔法最不费力的方式来避免这种情况,而不必承认通过改善这种情况你将问题转移到另一个问题,这个问题恰好被随机改组为排序顺序.希望这种不良情况是一种非常罕见的情况,即使它确实出现了随机性意味着问题不能轻易复制并归咎于这种欺骗.
以罕见的方式为代价来改进常见案例的概念很好.随机性作为实际考虑哪些案例或多或少常见的替代方案有点草率.