And*_*ech 11 sorting algorithm deterministic quicksort
我一直在阅读有关Quicksort的文章,并发现有时候它被称为"确定性的Quicksort".
这是普通Quicksort的替代版本吗？普通Quicksort和确定性Quicksort有什么区别？
Ano*_*on. 12
普通("确定性")Quicksort在特定数据集上的行为可能非常差(例如,选择第一个未排序元素的实现在已排序数据上具有O(n ^ 2)时间复杂度).
随机Quicksort(选择随机数据,而不是确定性选择)有时用于在所有数据集上提供更好的预期性能.
Quicksort在O(n log n)预期/平均时间内运行,但O(n^2)最糟糕的情况.如果选择的枢轴始终是最小值或最大值,则会发生这种情况.
理想情况下,您希望选择中位数作为您的支点.如果直接找到中位数太昂贵(通常情况下,如果你试图使用quicksort就是这种情况),通常做的是取三个潜在枢轴元素的中位数,或者只选择一个随机元素作为你的支点.
由于枢轴选择过程固有的随机性,后一种方法使快速排序不确定.
| 归档时间： |
|
| 查看次数： |
8023 次 |
| 最近记录： |