快速排序的复杂性，当所有的元素都一样吗？ [英] Quicksort complexity when all the elements are same?

问题描述

我有N个编号，且same.I正在申请快速排序上的数组。 应该是什么分拣的时间复杂度在此情况下

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.

我瞪大眼睛解决这个问题，但没有得到确切的解释。

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

任何帮助将是AP preciated。

Any help would be appreciated.

推荐答案

这取决于快速排序的实现。传统的实现，它分割成2（＆LT; 和＆GT; = ）段将有在相同的输入O（N * N）。虽然没有的互换的必然发生，就会造成 N 来进行递归调用 - 每一个需要做的支点和一个比较正recursionDepth 元素。即 O（N * N）的比较需要进行

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 swaps will necessarily occur, it will cause n recursive calls to be made - each of which need to make a comparison with the pivot and n-recursionDepth elements. i.e. O(n*n) comparisons need to be made

然而，有一个简单的变体，它分割成3组（＆LT; ， = 和＆GT; ）。这种变体具有 O（N）在这种情况下的性能 - 而不是选择的支点，交换，然后递归的 0 以 pivotIndex-1 和 pivotIndex + 1 到 N ，它会把掉所有的东西等于支点的中间分区（这在所有相同的输入总是意味着与自己交换的情况下，即无操作），这意味着调用堆栈将只1深藏在这个特殊的当n比较和无掉期出现。我相信，这种变异使得它的方式成至少在Linux标准库。

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-1 and pivotIndex+1 to 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.

这篇关于快速排序的复杂性，当所有的元素都一样吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！