为什么快速排序在有许多重复元素的情况下效率低下

Question

当我对一些有很多重复元素的数据进行排序时，快速排序算法效率很低。有人能解释一下原因吗
这是我的快速排序代码：

int partition(int arr[],int low,int high)
{
    int i = low + 1;
    int j = high;
    int tmp = arr[low];
    while(1)
    {
        while(j != low && arr[j] > tmp) --j;   //from right to left
        while(i != high && arr[i] <= tmp) ++i;  //from left to right
        if(i < j)
        {
            int t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
        }
        else
            break;
    }
    return j;
}
void QuickSort(int arr[],int low,int high)
{
    if(low < high)
    {
        int j = partition(arr,low,high);
        int t = arr[j];
        arr[j] = arr[low];
        arr[low] = t;
        if(low < j)
            QuickSort(arr,low,j-1);
        if(high > j)
            QuickSort(arr,j+1,high);
    }
}

Answer 1

我的心理调试技能告诉我，不仅你的输入有很多重复，而且重复的元素是连续的，这使得输入一开始大多是排序的。大部分排序的容器是快速排序的最坏情况，性能会降低到与O(n^2)一样差。

对于大多数有序输入，堆排序和合并排序等其他排序将提供更好的性能，因为它们的最坏情况只是平均情况下的常数更高。

Answer 2

下面的示例快速排序代码与问题中的示例代码相似，但如果重复次数较多，则耗时较少，如果数据已经排序或反向排序，则速度最快。主要区别是使用了修改的霍尔分区方案（动态枢轴）和中值3来选择初始枢轴。应该仍然存在导致最坏情况性能的模式，但我不确定这些模式会是什么

http://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

void QuickSort(uint32_t a[], int lo, int hi) {
    int i = lo, j = (lo + hi)/2, k = hi;
    uint32_t pivot;
    if (a[k] < a[i])            // median of 3
        std::swap(a[k], a[i]);
    if (a[j] < a[i])
        std::swap(a[j], a[i]);
    if (a[k] < a[j])
        std::swap(a[k], a[j]);
    pivot = a[j];
    while (i <= k) {            // partition
        while (a[i] < pivot)
            i++;
        while (a[k] > pivot)
            k--;
        if (i <= k) {
            std::swap(a[i], a[k]);
            i++;
            k--;
        }
    }
    if (lo < k)                 // recurse
        QuickSort(a, lo, k);
    if (i < hi)
        QuickSort(a, i, hi);
}