我有用于快速排序和合并排序的代码，并且我放置了一个全局计数器变量，该变量在每次迭代（比较）时都会递增。我认为这与我粗略的渐近分析相对应。对于合并排序，它可以，但对于快速排序，它没有。我不明白为什么。我选择输入数组的最后一个元素是每次迭代中的枢轴。我知道这不是最优的，但为了讨论，这并不重要。由于我选择了最后一个元素，我希望升序和降序数组都会导致 O(n^2) 比较。更具体地说，我希望比较次数为 n 选择 2，因为在最坏的情况下，您要添加 n + n-1 + n-2 + n-3 + .... + 1。但这似乎没有发生。
在输入大小为 100,000 时，输入按降序排序，我得到 705,082,704 次迭代。对于按升序排序的输入数组，我得到相同的数字。但是 100,000 选择 2 大约是 50 亿。为什么会出现差异？
对于合并排序，输入为 100,000，我得到大约 160 万次迭代，这似乎是正确的。
以下是包含我的快速排序实现以及我的计数技术的代码，两者都可能关闭，从而导致这种差异。否则一定是我的逻辑错了，这应该进行多少次迭代？
另外，顺便说一句，我很好奇，虽然在升序和降序输入数组中比较的次数是相同的，但升序版本的速度要快 2-3 倍。什么可以解释这一点。事不宜迟，这里是代码。
int counter = 0;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int partition(int *array, int low, int high){
int firsthigh = low;
int pivot = high;
for(int i = low; i < high; i++)
{
counter++;
if(array[i] < array[pivot])
{
swap(array[i], array[firsthigh]);
firsthigh++;
}
}
swap(array[pivot],array[firsthigh]);
return firsthigh;
}
void quicksort(int *array, int low, int high){
int p;
if(low < high)
{
p = partition(array, low, high);
quicksort(array, low, p-1);
quicksort(array,p+1,high);
}
}
int main(){
int array[100000];
for(int i = 0; i < 100000; i++)
array[i] = i;
struct timeval start, end;
for(int i = 0; i < 100000; i++)
cout << array[i] << " ";
gettimeofday(&start, NULL);
//mergesort(array, 0, 99999);
quicksort(array, 0, 99999);
gettimeofday(&end, NULL);
long long time = (end.tv_sec * (unsigned int)1e6 + end.tv_usec) -
(start.tv_sec * (unsigned int)1e6 + start.tv_usec);
for(int i = 0; i < 100000; i++)
cout << array[i] << " ";
cout << endl;
cout << endl << endl << time/1000000.0 << endl;
cout << endl << counter;
}