什么是确定性快速排序？ [英] What is a Deterministic Quicksort?

问题描述

我一直在阅读有关Quicksort的信息，发现有时将其称为确定性Quicksort。

I have been reading about Quicksort and found that sometimes it' s referred to as "Deterministic Quicksort".

这是普通Quicksort的替代版本吗？普通Quicksort和确定性Quicksort有什么区别？

Is this an alternate version of the normal Quicksort ? What is the difference between a normal Quicksort and a Deterministic Quicksort ?

推荐答案

普通（确定性）Quicksort的效果很差特定数据集上的行为（例如，选择第一个未排序元素的实现对已排序数据的时间复杂度为O（n ^ 2）。）

The ordinary ("deterministic") Quicksort can have very poor behaviour on particular datasets (as an example, an implementation that picks the first unsorted element has O(n^2) time complexity on already-sorted data).

随机化Quicksort （选择随机支点，而不是确定性地选择）有时可用于在所有数据集上提供更好的预期性能。

Randomized Quicksort (which selects a random pivot, rather than choosing deterministically) is sometimes used to give better expected performance over all datasets.

这篇关于什么是确定性快速排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！