为什么QuickSort不能对几乎排序的数据进行排序 [英] Why QuickSort bad at sorting almost sorted data

问题描述

为什么QuickSort对排序几乎排序的数据不利?相比之下，为什么插入排序更好?试图了解Big O符号！

Why is QuickSort bad at sorting almost sorted data? In comparison, why is insertion sort better? Trying to understand Big O notation!

推荐答案

您的声明对于某些QS变体是正确的，具体取决于选择的枢轴. QS性能取决于将数据分成大小大致相等的数据块的数据透视操作，然后将这些数据分别进行分类.如果枢轴是数据的最小值或最大值，或代表较高或较低的百分位数，则枢轴操作会将数据分为两部分，因此大多数数据位于这两者之一中，仍然需要排序.如果将数据的第一个元素选择为枢轴，并且对数据进行了排序，则会发生这种最坏情况.通过仅选择一个随机元素作为枢轴，最坏的情况发生的机会就可以忽略不计.这与最坏情况的分析无关，但是平均而言(在可能的支点上，最坏情况的wrt输入)或在实践中会产生良好的性能.

Your statement is true for certain variants of QS depending on the choice of pivot. QS performance depends on the pivoting operation to divide the data into approximately equally sized chunks, which will then be sorted separately. If the pivot is the min or max of the data, or represents a high or low percentile, the pivoting operation will divide the data into two parts whereby most of the data is in one of the two, which still needs to be sorted. If the first element of the data is chosen as a pivot, and the data is sorted, this worst case scenario occurs. By just choosing a random element as pivot, the worst case scenario has a negligible chance of occurring. This is irrelevant to worst case analysis, but on average (over possible pivots, worst case wrt input) or in practice this results in good performance.

这篇关于为什么QuickSort不能对几乎排序的数据进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！