C语言 当所有元素都相同时，快速排序的复杂性？

Quicksort complexity when all the elements are same?

提问by Sandeep Pathak

I have an array of N numbers which are same.I am applying Quick sort on it. What should be the time complexity of the sorting in this case.

我有一个由 N 个数字组成的数组，它们是相同的。我正在对其应用快速排序。在这种情况下排序的时间复杂度应该是多少。

I goggled around this question but did not get the exact explanation.

我盯着这个问题，但没有得到确切的解释。

Any help would be appreciated.

任何帮助，将不胜感激。

回答by tobyodavies

This depends on the implementation of Quicksort. The traditional implementation which partitions into 2 (<and >=) sections will have O(n*n)on identical input. While no swapswill necessarily occur, it will cause nrecursive calls to be made - each of which need to make a comparison with the pivot and n-recursionDepthelements. i.e. O(n*n)comparisons need to be made

这取决于 Quicksort 的实现。划分为 2 (<和>=) 部分的传统实现将具有O(n*n)相同的输入。虽然不一定会发生交换，但它会导致进行n递归调用 - 每个调用都需要与枢轴和n-recursionDepth元素进行比较。即O(n*n)需要进行比较

However there is a simple variant which partitions into 3 sets (<, =and >). This variant has O(n)performance in this case - instead of choosing the pivot, swapping and then recursing on 0to pivotIndex-1and pivotIndex+1to n, it will put swap all things equal to the pivot to the 'middle' partition (which in the case of all identical inputs always means swapping with itself i.e. a no-op) meaning the call stack will only be 1 deep in this particular case n comparisons and no swaps occur. I believe this variant has made its way into the standard library on linux at least.

然而，有一个简单的变体，它分为​​ 3 个集合 ( <,=和>)。这种变体O(n)在这种情况下具有性能 - 而不是选择主元，交换然后递归0到pivotIndex-1和pivotIndex+1to n，它将交换所有等于主元的东西到“中间”分区（在所有相同输入的情况下总是意味着与自身交换，即无操作）意味着在这种特殊情况下调用堆栈将只有 1 深 n 比较并且不发生交换。我相信这个变体至少已经进入了 linux 上的标准库。

回答by ltjax

The performance of quicksort depends on the pivot selection. The closer the chosen pivot is to the median element, the better is quicksort's performance.

快速排序的性能取决于枢轴选择。选择的枢轴越靠近中间元素，快速排序的性能就越好。

In this specific case you're lucky - the pivot you select will always be amedian, since all values are the same. The partition step of quicksort will hence never have to swap elements, and the two pointers will meet exactly in the middle. The two subproblems will have therefore be exactly half the size - giving you a perfect O(n log n).

在这种特殊情况下，你是幸运的-你选择的支点将永远是一个中位数，因为所有的值都是一样的。因此，快速排序的分区步骤永远不必交换元素，并且两个指针将恰好在中间相遇。因此，这两个子问题的大小正好是它的一半——给你一个完美的O(n log n).

To be a little more specific, this depends on how well the partition step is implemented. The loop-invariant only needs to make sure that smaller elements are in the left-hand sub-problem, while greater elements are in the right-hand sub-problem. There's no guarantee that a partition implementation never swaps equal elements. But it is always unnecessary work, so no clever implementation should do it: The leftand rightpointers will never detect an inversion respective the pivot (i.e. you will never hit the case where *left > pivot && *right < pivot) and so the leftpointer will be incremented, the rightpointer will be decremented every step and they will finally meet in the middle, generating subproblems of size n/2.

更具体地说，这取决于分区步骤的实施情​​况。循环不变式只需要确保较小的元素在左侧子问题中，而较大的元素在右侧子问题中。不能保证分区实现永远不会交换相等的元素。但这始终是不必要的工作，因此没有聪明的实现应该这样做：left和right指针永远不会检测到与枢轴对应的反转（即您永远不会遇到 where 的情况*left > pivot && *right < pivot），因此left指针将递增，right指针将每隔step ，它们最终会在中间相遇，产生大小为 的子问题n/2。

回答by aaz

It depends on the particular implementation.

这取决于特定的实现。

If there is only one kind of comparison (≤ or <) to determine where the other elements go relative to the pivot, they will all go into one of the partitions, and you will get O(n²) performance, since the problem size will decrease by only 1 each step.

如果只有一种比较（≤ 或 <）来确定其他元素相对于枢轴的位置，它们将全部进入其中一个分区，并且您将获得 O( n ²) 性能，因为问题的大小每一步只会减少 1。

The algorithm listed hereis an example (the accompanying illustration are for a different algorithm).

此处列出的算法是一个示例（随附的插图适用于不同的算法）。

If there are two kinds of comparisons, for example < for elements on the left and > for elements on the right, as is the case in a two-pointer implementation, andif you take care to move the pointers in step, then you might get perfect O(nlog n) performance, because half the equal elements will be split evenly in the two partitions.

如果有两个类型的比较，例如<左侧元素和>在右边元素，是在两指针实现的情况下，并且如果你照顾到移动步骤中的指针，那么你可能会获得完美的 O( nlog n) 性能，因为一半的相等元素将在两个分区中平均分配。

The illustrations in the link above use an algorithm which doesn't move pointers in step, so you still get poor performance (look at the "Few unique" case).

上面链接中的插图使用了一种不会逐步移动指针的算法，因此您的性能仍然很差（查看“少数独特”案例）。

So it depends whether you have this special case in mind when implementing the algorithm.

因此，这取决于您在实现算法时是否考虑到这种特殊情况。

Practical implementations often handle a broader special case: if there are no swaps in the partitioning step, they assume the data is nearly sorted, and use an insertion sort, which gives an even better O(n) in the case of all equal elements.

实际实现通常处理更广泛的特殊情况：如果在分区步骤中没有交换，他们假设数据几乎已排序，并使用插入排序，这在所有元素相等的情况下提供更好的 O( n)。

回答by rusty

tobyodavies has provided the right solution. It does handle the case and finish in O(n) time when all the keys are equal. It is the same partitioning as we do in dutch national flag problem

tobyodavies 提供了正确的解决方案。当所有键都相等时，它确实处理案例并在 O(n) 时间内完成。与我们在荷兰国旗问题中所做的划分相同

http://en.wikipedia.org/wiki/Dutch_national_flag_problem

http://en.wikipedia.org/wiki/Dutch_national_flag_problem

Sharing the code from princeton

分享普林斯顿的代码

http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html

http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html

回答by Farhan Haque

If you implement the 2-way partitioning algorithm then at every step the array will be halved. This is because when identical keys will be encountered, the scan stops. As a result at each step, the partitioning element will be positioned at the center of the subarray thereby halving the array in every subsequent recursive call. Now, this case is similar to the mergesort case which uses ~N lg Ncompares to sort an array of N elements. Ergo for duplicate keys, the traditional 2-way partitioning algorithm for Quicksort uses ~N lg Ncompares, thereby following a linearithmic approach.

如果您实现 2 路分区算法，那么在每一步，数组都将减半。这是因为当遇到相同的密钥时，扫描就会停止。因此，在每个步骤中，分区元素将位于子数组的中心，从而在每次后续递归调用中将数组减半。现在，这种情况类似于使用~N lg N比较对 N 个元素的数组进行排序的归并排序情况。因此，对于重复键，快速排序的传统 2 路分区算法使用~N lg N比较，从而遵循线性方法。