数据结构中堆排序问题

Question

#代码可以跑，但是堆排序运行结果不正确，结构体运用不熟练，不会转化
#代码如下

#include <iostream>
#include <cstring>

using namespace std;
struct student{
    int stn;
    char name[9];
    int score;
    char sex;
};
typedef student ElemType;

void QuickSort(ElemType A[], int s, int t)
{
    int i=s+1, j=t;
    ElemType x=A[s];
    while(i<=j) {
        while(A[i].score<=x.score && i<=j) i++;
        while(A[j].score>=x.score && j>=i) j--;
        if(i<j) {
            ElemType temp=A[i]; A[i]=A[j]; A[j]=temp;
            i++; j--;
        }
    }
    if(s!=j) {A[s]=A[j]; A[j]=x;}
    if(s<j-1) QuickSort(A,s,j-1);
    if(j+1<t) QuickSort(A,j+1,t);
}
void Sift(ElemType A[], int n, int i)
{
    ElemType x=A[i];
    int j;
    j=2*i+1;
    while(j<=n-1) {
        if(j<n-1 && A[j].stn<A[j+1].stn) j++;
        if(x.stn<A[j].stn) {
            A[i]=A[j]; i=j; j=2*i+1;
        }
        else break;
    }
    A[i]=x;
}


void HeapSort(ElemType A[], int n)
{
    ElemType x;
    int i;
    for(i=n/2-1; i>=0; i--) Sift(A,n,i);
    for(i=1; i<=n-1;i++) {
        x=A[0]; A[0]=A[n-i]; A[n-i]=x;
        Sift(A,n-i,0);
    }
}

int Binsch(ElemType A[], int n,int key) {
    int low=0, high=n-1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key == A[mid].score)
        {
            return mid;
        }
        else if (key < A[mid].score)
        {
            high = mid - 1;
        }
        else { low = mid + 1; }
    }
    return -1;
}
void Display(ElemType A[]){
    cout<<endl;
    cout<<"ID\tName\tScores\tSex"<<endl;
    for(int i=0;i<=3;i++){
        cout<<A[i].stn<<"\t"<<A[i].name<<"\t  "<<A[i].score<<"\t"<<A[i].sex<<endl;
    }
}
int main(){
    ElemType D[3];
    D[0].stn=1000;
    strcpy(D[0].name,"ZhanSan");
    D[0].score=95;
    D[0].sex='F';

    D[1].stn=1001;
    strcpy(D[1].name,"LiSi");
    D[1].score=75;
    D[1].sex='M';

    D[2].stn=1002;
    strcpy(D[2].name,"wangWU");
    D[2].score=96;
    D[2].sex='M';

    D[3].stn=1003;
    strcpy(D[3].name,"ZhaoLiu");
    D[3].score=76;
    D[3].sex='F';

    Display(D);
    //QuickSort(D,0,3);
    HeapSort(D,3);
    Display(D);
    int k,d;
    cout<<"Please enter the score you need to find:"<<endl;
    cin>>k;
    d=Binsch(D,4,k);
    if(d>=0)
        cout<<"Successed!"<<endl;
    else
        cout<<"Failed!"<<endl;
    return 0;
}

Answer 1

//时间复杂度O(logN)
void DwonAdjust(int *a, int n, int root)//向下调整,左右子树都为同种堆才能使用
{
    int parent = root;
    int child = parent * 2 + 1;//默认左孩子
    while (child<n)
    {
        //选出左右孩子中大的那一个，建大堆换一下比较符
        if (a[child + 1] > a[child] && child < n - 1)
            child++;
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}
//整体时间复杂度O(NlogN)
void HeapSort(int*a, int n)
{
    //建堆，时间复杂度O(N)
    for (int i = (n - 2) / 2; i >= 0; i--)//从最后一个非叶节点调
        DwonAdjust(a, n, i);
    //排升序建大堆
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        DwonAdjust(a, end, 0);
        end--;
    }
}