C.堆排序.计算交换和比较的数量

Question

排序似乎工作正常。至少它的排序是正确的：(它只计算比较和交换的数量。如何计算和输出？不知怎的在这一点上停滞不前。。我将非常感谢你的帮助。如果您用更新的代码演示它，我将加倍感激。

#include <stdio.h>
#include <stdlib.h>
void keyDown(int* arr, int n, int head)
{
int j;
if(2*head + 2 < n && arr[2*head + 1] < arr[2*head + 2])
{
j = 2*head + 2; 
}
else j = 2*head + 1;
while(arr[head] < arr[j] && head < n / 2)
{
int tmp = arr[head];
arr[head] = arr[j];
arr[j] = tmp;

head = j;
if(2*head + 2 < n && arr[2*head + 1] < arr[2*head + 2])
{
j = 2*head + 2; 
}
else j = 2*head + 1;
}
}
void heapSort(int* arr, int n)
{  
int i;
for(i = n/2 - 1; i >= 0; i--)
{
keyDown(arr,n,i);
}
int l = n;
while(l > 1)
{  
l--;

int tmp = arr[l];
arr[l] = arr[0];
arr[0] = tmp;

keyDown(arr,l,0);
}
}
int main(int argc, char *argv[]) {
int n=10;
int start, end,i;
int *arr;
arr=(int *)malloc(n*sizeof(int));
time_t invocation_time = time(NULL);
srand(invocation_time);
int s;
for (s=0;s<n;s++)
{
arr[s] = rand() % 50;
printf ("%d n", arr[s]);
}
printf ("n");  
heapSort(arr, n);
for (i=0;i<n;i++){
printf ("%d n", arr[i]);   
}
return 0;
}

Answer 1

计算比较和交换的数量

使函数

//global counters
unsigned comparisons = 0, swaps = 0;
int lessthan(int a, int b) {
comparisons++;
return (a < b);
}
void swap(int *a, int *b) {
swaps++;
int tmp = *a; *a = *b; *b = tmp;
}

然后用所需的特定函数替换现有代码中的比较和交换。

int main(int argc, char **argc) {
//...
if (lessthan(a[i], a[j])) swap(a+i, a+j);
//...
printf("comparisons: %u; swaps: %un", comparisons, swaps);
}