快速排序对不同类型数组的性能问题

Question

使用递归快速排序，对长度为十万的数组排序，元素值是随机生成的。四种情况：元素顺序是随机的，元素顺序升序，元素顺序降序，元素值为重复的一个值。后三种情况的计算时间相差很多，理论上不应该都是 n*n吗？

下面代码中，data.txt包含十万个数字，是随机生成的。

#include <iostream>
#include <cstdlib>
#include <vector>
#include <fstream>
#include <algorithm>
#include <ctime>
using namespace std;
void quicktSort(vector<int> &nums, int start, int end);
int partition(vector<int> &nums, int start, int end);
int main()
{
    int len=100000;
    vector<int>nums_random(len);//随机数组
    vector<int>nums_increase(len);//升序数组
    vector<int>nums_decrease(len);//降序数组
    vector<int>nums_repeat(len,10);//重复数组，全为10
    ifstream file("data.txt");
    if (!file.is_open())
    {
        cout << "open file fair" << endl;
        return 0;
    }
    int num;
    for(int i=0;i<len;i++)
    {
            file>>num;
            nums_random[i]=nums_increase[i]=nums_decrease[i]=num;
    }
    sort(nums_increase.begin(),nums_increase.end(),less<int>());
    sort(nums_decrease.begin(),nums_decrease.end(),greater<int>());

    clock_t start_sort,end_sort;
    //随机数组排序时间
    start_sort=clock();
    quicktSort(nums_random,0,len-1);
    end_sort=clock();
    cout<<double(end_sort-start_sort)/CLOCKS_PER_SEC*1000<<endl;
    //升序数组排序时间
    start_sort=clock();
    quicktSort(nums_increase,0,len-1);
    end_sort=clock();
    cout<<double(end_sort-start_sort)/CLOCKS_PER_SEC*1000<<endl;
    //降序数组排序时间
    start_sort=clock();
    quicktSort(nums_decrease,0,len-1);
    end_sort=clock();
    cout<<double(end_sort-start_sort)/CLOCKS_PER_SEC*1000<<endl;
    //重复数组排序时间
    start_sort=clock();
    quicktSort(nums_repeat,0,len-1);
    end_sort=clock();
    cout<<double(end_sort-start_sort)/CLOCKS_PER_SEC*1000<<endl;
    file.close();
    return 0;
}
void quicktSort(vector<int> &nums, int start, int end)
{
    if (end <= start)
        return;

    int divideLoc = partition(nums, start, end);
    if(divideLoc>start)
         quicktSort(nums, start, divideLoc - 1);
    if(divideLoc<end)
         quicktSort(nums, divideLoc + 1, end);
}
int partition(vector<int> &nums, int start, int end)
{
    int baseValue = nums[start];
    while (end > start)
    {
        while (start < end && nums[end] > baseValue)
            end--;
        if(start<end)
              nums[start++] = nums[end];
        while (start < end && nums[start] <= baseValue)
            start++;
        if(start<end)
           nums[end--] = nums[start];
    }
    nums[start] = baseValue;
    return start;
}

运行结果：

Answer 1

https://blog.csdn.net/weshjiness/article/details/8660583