void Sift(int R[],int low,int high) { int i=low,j=2*i; int temp=R[i]; while (j<=high) { if (j<high && R[j]<R[j+1]) j++; if (temp<R[j]) { R[i]=R[j]; i=j; j= ; } else break; } R[i]= ; } void HeapSort(int R[],int n) { int i,j; int temp; for (i= ;i>=1;i--) Sift(R,i,n); for (i=n;i>=2;i--) { swap(R[1],R[i]); //将R[1]与R[i]进行交换。 ; } }

这段代码是一个基于堆排序的排序算法。其中Sift函数是用来对堆进行调整的，HeapSort函数是主函数。

在Sift函数中，参数R表示待排序的数组，low和high表示当前堆中需要调整的范围。变量i和j分别表示当前节点和它的左孩子节点，temp保存当前节点的值。循环中，如果右孩子比左孩子大，则选择右孩子作为比较对象；如果比较对象比当前节点大，则将比较对象赋值给当前节点，然后i更新为j，j更新为新的左孩子节点，继续循环，直到当前节点比它的左右孩子都大为止。最后将temp赋值给R[i]，完成一次调整。

在HeapSort函数中，首先使用Sift函数将整个数组构建成一个堆。然后从后往前遍历数组，每次将堆顶元素（即最大值）与当前遍历到的元素进行交换，然后将堆的范围缩小1，并重新调整堆，直到数组有序。

相关问题

完善代码1.冒泡排序 2.快速排序 3.堆排序#include <iostream> #include<cstdlib> #include<Windows.h> #include<ctime> using namespace std; void randomAssign(int a[],int n){ srand(time(0)); for(int i = 0; i < n;i++) a[i] = rand()%n+1; } void print(const char* str,int a[],int n){ cout<<str<<"="; for(int i = 0; i < n; i++) cout<<a[i] <<" "; cout<<endl; } void bubbleSort(int a[],int n){ for(int i = n; i >= 1; i--) for(int j = 1; j < i; j++) if(a[j+1] > a[j]) swap(a[j+1],a[j]); } int onePartition(int a[],int left,int right){ int pivot = a[left]; int i = left; int j = right; while(i < j){ while(XXXXXXXXXXXXX;) j++; if( i < j) a[i] = a[j]; XXXXXXXXXXXXX; XXXXXXXXXXXXX; if( i < j) a[j] = a[i]; } XXXXXXXXXXXXX; return i; } void quickSort(int a[],int left,int right){ if(left >= right) return ; int pos = XXXXXXXXXXXXX;; XXXXXXXXXXXXX; quickSort(a,pos+1,right); } void quickSort(int a[],int n){ quickSort(a,0,n-1); } void sift(int a[],int pos,int n){ //n表示长度 int parent = pos; int son = parent * 2 + 1; int tmp = a[parent]; while (son <= n - 1){ // 有效下标 0...n-1 if (son + 1 <= n - 1 && a[son] < a[son + 1]) son++; if(XXXXXXXXXXXXX) return; else { XXXXXXXXXXXXX; parent = son; son = parent * 2 + 1; } } } void heapSort(int a[],int n) { int i = 0; for (i = n / 2 - 1; i >= 0; i--) //从最后一个非叶结点开始 sift(a,i,n); for (i = n-1; i> 0; i--) { swap(a[0],a[i]); XXXXXXXXXXXXX; } } typedef void(*SortFunc)(int[], int); void testSort(SortFunc sortFunc,int n = 10){ DWORD start, end; int* a = new int[n]; randomAssign(a,n); if(n < 20) print("排序前",a,n); start = GetTickCount(); sortFunc(a,n); end = GetTickCount(); if(n < 20) print("排序后",a,n); cout<<"花费时间="<<end - start<<"毫秒"<<endl<<endl; delete [] a; } int main(){ testSort(bubbleSort,10); testSort(quickSort,10); testSort(heapSort,10); return 1; }

冒泡排序、快速排序和堆排序的代码已经提供，下面是完整的代码：

#include <iostream>
#include <cstdlib>
#include <Windows.h>
#include <ctime>

using namespace std;

void randomAssign(int a[], int n) {
    srand(time(0));
    for (int i = 0; i < n; i++)
        a[i] = rand() % n + 1;
}

void print(const char* str, int a[], int n) {
    cout << str << "=";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

void bubbleSort(int a[], int n) {
    for (int i = n; i >= 1; i--)
        for (int j = 1; j < i; j++)
            if (a[j + 1] > a[j])
                swap(a[j + 1], a[j]);
}

int onePartition(int a[], int left, int right) {
    int pivot = a[left];
    int i = left;
    int j = right;
    while (i < j) {
        while (a[j] >= pivot && i < j)
            j--;
        if (i < j)
            a[i++] = a[j];
        while (a[i] <= pivot && i < j)
            i++;
        if (i < j)
            a[j--] = a[i];
    }
    a[i] = pivot;
    return i;
}

void quickSort(int a[], int left, int right) {
    if (left >= right)
        return;
    int pos = onePartition(a, left, right);
    quickSort(a, left, pos - 1);
    quickSort(a, pos + 1, right);
}

void quickSort(int a[], int n) {
    quickSort(a, 0, n - 1);
}

void sift(int a[], int pos, int n) { // n表示长度
    int parent = pos;
    int son = parent * 2 + 1;
    int tmp = a[parent];
    while (son <= n - 1) { // 有效下标 0...n-1
        if (son + 1 <= n - 1 && a[son] < a[son + 1])
            son++;
        if (tmp >= a[son])
            break;
        else {
            a[parent] = a[son];
            parent = son;
            son = parent * 2 + 1;
        }
    }
    a[parent] = tmp;
}

void heapSort(int a[], int n) {
    int i = 0;
    for (i = n / 2 - 1; i >= 0; i--) //从最后一个非叶结点开始
        sift(a, i, n);
    for (i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        sift(a, 0, i);
    }
}

typedef void(*SortFunc)(int[], int);

void testSort(SortFunc sortFunc, int n = 10) {
    DWORD start, end;
    int* a = new int[n];
    randomAssign(a, n);
    if (n < 20)
        print("排序前", a, n);
    start = GetTickCount();
    sortFunc(a, n);
    end = GetTickCount();
    if (n < 20)
        print("排序后", a, n);
    cout << "花费时间=" << end - start << "毫秒" << endl << endl;
    delete[] a;
}

int main() {
    testSort(bubbleSort, 10);
    testSort(quickSort, 10);
    testSort(heapSort, 10);
    return 1;
}

需要注意的是：

1. 在快速排序的 onePartition 函数中，i 和 j 的初始值应该分别为 left 和 right，而不是 left + 1 和 right - 1。这是因为在 while 循环中，i 和 j 分别向中间移动，不会越界。
2. 在堆排序的 sift 函数中，比较的应该是 tmp 和 a[son]，而不是 a[parent] 和 a[son]。
3. 在堆排序的循环中，交换 a[0] 和 a[i] 后，应该对 a[0] 进行 sift 调整，而不是对 a[i] 进行 sift 调整。因为 a[i] 已经排好序了，不需要再调整。

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