c++ - 为什么快速排序在重复元素多的情况下效率低下？

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)。

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