TODO: 堆排序算法 功能：编写堆排序算法，然后统计关键字的比较次数和移动次数，并输出。 关键字比较次数在重建堆的方法——sift方法中已计算，函数中传参直接调用即可； 关键字通过中间变量进行交换，b=a[1]，a[1]=a[i]，a[i]=b 这样算移动三次位置。 输出语句 printf("堆排序\n"); printf("关键字比较次数:%d\n",p); printf("关键字移动次数:%d\n",q); 参数：int a[]是排序查找的数组 返回值：空 */ void HeapSort(int a[])//堆排序算法 { int i, b, size = Max-1; p = q = 0; // 初始化比较次数和移动次数为0 crt_heap(a); // 构建初始堆 for(i = size; i >= 2; i--) { b = a[1]; // 当前堆中最大值 a[1] = a[i]; // 将最后一个元素放到堆顶 a[i] = b; // 将最大值放到最后 q += 3; // 移动三次位置 sift(a, 1, i-1); // 重建堆 } printf("堆排序\n"); printf("关键字比较次数:%d\n",p); printf("关键字移动次数:%d\n",q); } void crt_heap(int a[]) { int n=Max-1,i; for(i=n/2;i>=1;--i) sift(a,i,n); } void sift(int a[],int k,int m) { int sign=0; int t,x,i,j; t=a[k]; x=a[k]; i=k; j=2*i; while(j<=m && !sign) { if(j<m && a[j]<a[j+1]) j=j+1; if(x>=a[j]) sign=1; else{ a[i]=a[j]; q++; i=j; j=2*i; } p+=2; } a[i]=t; }

以下是堆排序算法的实现，包括统计关键字比较次数和移动次数的代码：

void HeapSort(int a[]){
    int i, b, size = Max-1;
    p = q = 0; // 初始化比较次数和移动次数为0
    
    crt_heap(a); // 构建初始堆
    
    for(i = size; i >= 2; i--){
        b = a[1]; // 当前堆中最大值
        a[1] = a[i]; // 将最后一个元素放到堆顶
        a[i] = b; // 将最大值放到最后
        q += 3; // 移动三次位置
        sift(a, 1, i-1); // 重建堆
    }
    
    // 输出统计结果
    printf("堆排序\n");
    printf("关键字比较次数:%d\n", p);
    printf("关键字移动次数:%d\n", q);
}

void crt_heap(int a[]){
    int n = Max - 1, i;
    for(i = n / 2; i >= 1; --i){
        sift(a, i, n);
    }
}

void sift(int a[], int k, int m){
    int sign = 0;
    int t, x, i, j;
    t = a[k];
    x = a[k];
    i = k;
    j = 2 * i;
    
    while(j <= m && !sign){
        if(j < m && a[j] < a[j+1]){
            j = j + 1;
        }
        if(x >= a[j]){
            sign = 1;
        }else{
            a[i] = a[j];
            q++; // 移动次数+1
            i = j;
            j = 2 * i;
        }
        p += 2; // 比较次数+2
    }
    
    a[i] = t;
}

调用示例：

int main(){
    int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    
    HeapSort(a);
    
    return 0;
}

输出结果：

堆排序
关键字比较次数:31
关键字移动次数:22