pol*_*nts 42
我认为人们会混淆Quicksort基于分区的排序算法,并且"qsort"各种库实现.
我更喜欢将Quicksort算法视为具有可插拔的枢轴选择算法,这在分析其行为时非常重要.
如果始终选择第一个元素作为数据透视表,则已经排序的列表是最坏情况.通常,阵列很可能已经/几乎已经排序,因此这种实现方式相当差.
类似地,选择最后一个元素作为枢轴也是出于同样的原因.
一些实现尝试通过选择中间元素作为枢轴来避免此问题.这对于已经/几乎排序的数组不会表现得那么糟糕,但是仍然可以构造一个输入来利用这个可预测的数据透视选择并使其在二次时间内运行.
因此,您获得随机枢轴选择算法,但即使这样也无法保证O(N log N).
因此开发了其他算法,在选择枢轴之前使用序列中的一些信息.您当然可以扫描整个序列并找到中位数,并将其用作枢轴.这保证了O(N log N),但当然在实践中较慢.
因此,一些角落被削减,人们设计了3的中值算法.当然,后来甚至可以被所谓的3中位数"杀手"所利用.
因此,在提出更多"智能"枢轴选择算法时会做出更多尝试,这些算法保证O(N log N)渐近行为仍然足够快,实际上具有不同程度的成功.
实际上,除非指定Quicksort的特定实现,否则最坏情况发生的时间问题是不明确的.如果使用所谓的中位数中值枢轴选择算法,则不存在二次最坏情形.
然而,大多数库实现可能会丧失O(N log N)在一般情况下更快排序的保证.一些非常古老的实现使用第一个元素作为枢轴,现在已经很好地理解为差,并且不再是广泛遵循的实践.
Jen*_*ens 34
我认为,快速排序的最坏情况取决于每一步中枢轴元素的选择.如果枢轴可能是列表中的最小元素或最大元素(例如已排序列表的第一个或最后一个元素),则Quicksort的性能最差.
例如,如果您选择列表的中间元素,则已排序的列表不具有最差情况运行时.
因此,如果您怀疑自己的方案可能是快速排序的错误案例,您可以简单地更改您对pivot元素的选择,以使quicksort更好地执行.
注意:我知道,这并没有给出快速排序最坏情况的真实世界场合的更多例子.此示例取决于您正在使用的实现.
实际的问题是:"这种情况(几乎已经分类)何时会以自然输入发生？".
尽管所有答案都涉及"导致最坏情况性能的原因",但没有一个涉及"导致数据遇到最坏情况性能情况的原因".
程序员错误:基本上你需要两次排序列表.通常这是因为列表在代码中的一个位置排序.后来在另一段代码中,您知道需要对列表进行排序,因此您需要再次对其进行排序.
使用几乎按时间顺序排列的数据:您的数据通常按时间顺序接收,但偶尔会有一些元素不合适.(考虑一个多线程环境,将时间戳元素添加到列表中.竞争条件可能导致元素以不同的顺序添加到时间戳中.)在这种情况下,如果需要排序数据,则必须重新排序-分类.因为无法保证数据的顺序.
将项添加到列表:如果您有一个排序列表,只需附加一些项(即不使用二进制插入).您需要重新排序几乎排序的列表.
来自外部源的数据:如果您从外部源接收数据,则可能无法保证其已排序.所以你自己排序.但是,如果外部源已排序,您将重新排序数据.
自然排序:这类似于计时数据.基本上,您收到的数据的自然顺序可能会被排序.考虑一家保险公司添加汽车注册.如果分配汽车注册的机构以可预测的顺序进行,则可能会提供更新的汽车,但不能保证有更高的注册号.由于您无法保证它已经排序 - 您必须重新排序.
交错数据:如果您从具有重叠键的多个已排序源接收数据,您可以获得类似于以下内容的键:1 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18.尽管有一半的元素已经输出与其邻居的序列,列表"几乎排序".当然使用在第一个元素上枢轴转动的QuickSort会表现出O(n^2)性能.
因此,鉴于上述所有情况,实际上很容易找到几乎排序的数据.这正是为什么最好避免在第一个元素上转动的QuickSort的原因.polygene提供了一些有关替代旋转考虑因素的有趣信息.
作为旁注:通常表现最差的排序算法之一,实际上与"几乎排序"的数据相当好.在上面的交错数据中,冒泡排序只需要9次交换操作.它的性能实际上是
O(n).
| 归档时间： |
|
| 查看次数： |
72892 次 |
| 最近记录： |