c++ - 快速排序排序降序数据时的奇怪行为

为什么在按升序降序（100，99，…，0，99，100）对包含数字的数组进行排序时，qs的实现工作如下？:

time for 50000 elements: 0.123 s
time for 100000 elements: 0.288 s
time for 150000 elements: 0.629 s
time for 200000 elements: 0.695 s
time for 250000 elements: 1.652 s
time for 300000 elements: 1.663 s
time for 350000 elements: 3.404 s
time for 400000 elements: 4.185 s
time for 450000 elements: 3.887 s
time for 500000 elements: 6.73 s
time for 550000 elements: 8.887 s
time for 600000 elements: 9.137 s
time for 650000 elements: 11.094 s
time for 700000 elements: 8.436 s
time for 750000 elements: 15.182 s

对于700000个元素，它的工作速度比650000个元素快我重复了几次测试。
代码如下：

    #include <iostream>
    #include <cstdlib>
    #include <time.h>
    #include <new>
    #include <math.h>

    using namespace std;
    inline void swap (int *a, int *b)
    {
        int tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
    void quick_sort(int tab[], int l, int r);
    int *allocate (int size);
    void dec_inc (int tab[], const int length);
    int main()
    {
        int step = 50000;
        int how_many = 15;
        int k = 1;
        int length = step * how_many;
        int *tab = allocate(length);
        clock_t t2, t1;
        long double dif;
        while (step * k <= length)
        {
            dec_inc(tab, step*k);
            t1 = clock();
            quick_sort(tab, 0, step*k - 1);
            t2 = clock();
            dif = (long double)(t2 - t1)/CLOCKS_PER_SEC;
            cout << "time for " << step * k << " elements: " << dif << " s" << endl;
            k++;
        }
        delete [] tab;
        system("pause");

    }
    int *allocate (int size)
    {
        try
        {
            return new int [size];
        }
        catch(bad_alloc)
        {
            cerr << "ERROR\n";
            exit(EXIT_FAILURE);
        }
    }
    void quick_sort(int tab[], int l, int r)
    {
        int v = tab[(l+r)/2];
        int i = l;
        int j = r;
        do
        {
            while(tab[i] < v) i++;
            while(tab[j] > v) j--;
            if (i <= j)
            {
                swap(&tab[i], &tab[j]);
                i++, j--;
            }
        }
        while(i <= j);
        if (l < j)
            quick_sort(tab, l, j);
        if(i < r)
            quick_sort(tab, i, r);
    }
    void dec_inc (int tab[], const int length)
    {
        int i = length/2;
        for (int j = 0; j < length/2; j++, i--)
        {
            tab[j] = i;
        }
        for (int j = length/2; j < length; j++, i++)
        {
            tab[j] = i;
        }
    }

最佳答案

使用quicksort的缺点之一是它的稳定性某些数据集需要比其他数据集更多的步骤进行排序。对于病理病例，它甚至可以标度为o（n^2）。我测量了quicksort对测试数据执行的比较次数，发现在700000个步骤中，要执行的比较少于650000个元素即使您的数据集看起来很相似，但显然对于quicksort来说它们不是。有多种方法可以提高quicksort的稳定性，请参见示例Programming Pearls。
以下是测量结果：
650000个元素的时间：4.41251 s.num.compariations 5061169826
700000个元素的时间：3.37787 s.num.比较3824058435
750000个元素的时间：6.07856 s.num.比较6900645055
这里是相应的代码：gist