观察二次行为与快速排序 - 为O（n ^ 2）

问题描述

借助快速排序算法邻的平均时间复杂度（N *的log（n））并为O（n ^ 2）。

的最坏情况下的复杂性

假设一些变种霍尔的快速排序算法，什么样的输入将导致快速排序算法表现出最坏情况下的复杂性？

请注明相关的实施细则，对于特定的快速排序算法，如支点的选择等，或者如果它是从一个常用的库源，如libc中的任何假设。

一些阅读：

1. 一个杀手敌手的快速排序
2. 快速排序是最优的
3. 工程排序功能
4. 内省排序和选择算法

解决方案

快速排序执行最差也就是在为O（n ^ 2）时所选择的支点所有的值或者是采取集的最大或最小。考虑这个例子。

1 2 3 4 5

选择的枢轴说是1，则必须在右侧的枢轴的4元素和左侧没有元素。分别递归地施加这种相同的逻辑和所选择的枢轴为2，3，4，5，我们取得的情况下这种已在其最坏的时间进行。

据建议，并证明，快速排序执行好，如果输入的是打乱很好。

此外，选择一种通常取决于对输入域明确的认识。例如，如果输入是巨大的，则有一种叫做作为外部排序可能使用外部存储器。如果输入大小是非常小的，我们可能会去合并排序但不为介质和巨大的输入集，因为它使用额外存储器。快速排序的主要优点是它的就地内斯的意义，没有额外的内存被用于输入数据。最坏情况下的时间在纸面上是O（n ^ 2），但仍是普遍preferred和使用。在这里我想说的是，排序算法可以根据输入设置和preference其问题的知识来改变。

The quicksort algorithm has an average time complexity of O(n*log(n)) and a worst case complexity of O(n^2).

Assuming some variant of Hoare’s quicksort algorithm, what kinds of input will cause the quicksort algorithm to exhibit worst case complexity?

Please state any assumptions relating to implementation details regarding the specific quicksort algorithm such as pivot selection, etc. or if it's sourced from a commonly available library such as libc.

Some reading:

1. A Killer Adversary for Quicksort
2. Quicksort Is Optimal
3. Engineering a Sort Function
4. Introspective Sorting and Selection Algorithms

解决方案

The Quick sort performs worst ie, at O(n^2) when all the values of the pivot chosen is either the largest or smallest of the taken set. Consider this example.

1 2 3 4 5

The pivot chosen say is 1, you will have 4 elements on the right side of the pivot and no elements on the left side. Applying this same logic recursively and the pivot chosen is 2, 3, 4, 5 respectively, we have attained a situation where this sort has performed at its worst possible time.

It has been recommended and proven that Quicksort performs well if the input is shuffled well.

Moreover, selection of a sort usually depends on a clear knowledge about the input domain. For example, if the input is huge, then there is something called as external sort which may use external memory. If the input size is very small, we may go for a merge sort but not for medium and huge input sets since it uses extra memory. The main advantage of Quick sort is its "in-place"ness meaning, no extra memory is being used for the input data. Its worst case time on paper is O(n^2) but still is widely preferred and used. My point here is, sorting algorithms can be changed based on the knowledge on the input set and its a matter of preference.

这篇关于观察二次行为与快速排序 - 为O（n ^ 2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！