今天学习堆排序，我建议你先去这个网站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]调整为最大堆。
}
}
运行结果：
这里写图片描述
