我有快速排序和归并排序的代码,并放置了一个全局计数器变量,该变量在每次迭代(比较)时都会递增。我认为这应该对应于我的粗略渐近分析。对于归并排序,它确实是这样的,但对于快速排序,它却不是。我不明白为什么。我选择输入数组的最后一个元素作为每次迭代的枢轴。我知道这是非最优的,但对于这个讨论来说并不重要。由于我选择了最后一个元素,我希望升序和降序数组都会产生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倍。是什么原因?没有进一步的话,这里是代码。
对于归并排序,输入为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;
}
high
作为你的枢轴(除其他事项外)。尝试随机选择枢轴。 - IVladgettimeofday()
。你目前还在测量打印数组所需的时间。 - Blastfurnace