考研排序算法之堆排序

今天学习堆排序，我建议你先去这个网站https://bajdcc.github.io/html/heap.html看一下堆排序的可视化算法过程在过来看具体代码编程。

#include<iostream>
using namespace std;
void displayarray(int a[], int n);
void HeadSort(int a[], int n);
void CreateHead(int a[], int n);
void AdjustHead(int a[], int s,int m);
int main(){
    int a[] = { 67,48,23,81,38,19,52,40 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "排序前" << endl;
    displayarray(a, n);
    //排序
    HeadSort(a, n);
    cout << "排序后" << endl;
    displayarray(a, n);
    system("pause");
    return  0;
}
void displayarray(int a[], int n) {
    for (int i = 0; i < n; i++)
    {
        cout << a[i]<<" ";
    }
    cout << endl;
}
//建立大顶堆。
void CreateHead(int a[], int n)
{
    for (int  i = n/2-1; i >=0;i--)
    {
        AdjustHead(a, i, n - 1);
    }
}
//调整a[s，m使得其成为一个大顶堆]
void AdjustHead(int a[], int s, int m)
{
    int t, j;
    t = a[s];//根节点暂时保存在t之中。
    for ( j = 2*s+1; j <=m; j*=4)
    {
        if (j<m&&a[j]<a[j+1])
        {
            j++;
        }
        if (t > a[j]) {
            break;
        }
        a[s] = a[j];
        s = j;
    }
    a[s] = t;
}
void HeadSort(int a[], int n) {
    int t; int i;
    CreateHead(a, n);//创建堆
    for (i = n-1; i >0; i--)
    {
        t = a[0];
        a[0] = a[i];
        a[i] = t;
        cout << "第" << n-i<< "趟排序结果"<<endl;
        displayarray(a, n);
        AdjustHead(a, 0, i-1);//将a[0.....i-1]调整为最大堆。
    }

}

运行结果：

这里写图片描述