实验题目：
堆排序算法
[实验目的] 验证堆排序算法。
[实验内容及要求]
1. 实现堆排序算法。
2.输入待排序元素个数，利用随机函数生成指定数目的元素，元素值的取值范围为[10,1000000]。
3.运行堆排序程序对所生成元素进行排序，要求将元素的初始输入序列和排序后的结果序列都输出在一个文件中。
4.对相同的待排序元素数，要求程序运行 10 次，将每次排序所进行的元素比较次数和平均比较次数输出在文件中。
函数部分：
using namespace std;
void swap(int* a, int* b){ //交换元素
int node = *b;
*b = *a;
*a = node;
}
void restore(int arr[], int start, int end,int &count){ //建立堆
int dad = start;
int son = dad * 2 + 1;
while (son <= end){
if (son + 1 <= end && arr[son] < arr[son + 1]){
son++;
}
if (arr[dad] > arr[son]){
count++;
return;
}
else
{
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
count+=2;
}
}
void heap_sort(int arr[], int len,int &count){ //堆排序
int i;
for (i = len / 2 - 1; i >= 0; i--)
restore(arr, i, len - 1,count);
for (i = len - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
restore(arr, 0, i - 1,count);
}
}
inline int rand_area(int a,int b){ //生成随机数
return (rand() % (b-a+1))+ a;
}
void save_arr(string str,int arr[],int len){ //存储数据到文件，文件路径请自行更改
ofstream save;
save.open("/Users/duyifan/Desktop/heap_sort.txt",ios::app);
save<<str;
for(int i=0;i<len;i++)
save<<arr[i]<<' ';
save<<endl;
save.close();
}
调用部分：
ofstream save;
int len,count=0,counts=0;
cout<<"Please enter the number of elements:";
cin>>len;
int *arr=new int[len];
for(int i=0;i<10;i++){
srand((unsigned)time(NULL));
for(int i=0;i<len;i++)
arr[i]=rand_area(10, 1000);
cout<<"The randomly generated array is:"<<endl;
for(int i=0;i<len;i++)
cout<<arr[i]<<' ';
cout<<endl;
save_arr("randomly generated array:",arr, len);
heap_sort(arr, len, count);
save_arr("sort result:",arr,len);
cout<<"The sort result is:"<<endl;
for (int i = 0; i < len; i++)
cout<<arr[i]<<' ';
cout<<endl;
save.open("/Users/duyifan/Desktop/heap_sort.txt",ios::app);
save<<"count:"<<count<<endl;
save.close();
counts+=count;
count=0;
}
save.open("/Users/duyifan/Desktop/heap_sort.txt",ios::app);
save<<"average count:"<<counts/10<<endl;
save.close();