[数据结构与算法]C语言堆排序：随机产生10000个无序数后排序、贴出程序运行完成时的屏幕截图或者输出文件的内容

这是一篇实验报告

一、实验内容：

堆排序。

二、所用算法的基本思想及复杂度分析：

1. 基本思想

堆排序是利用完全二叉树的性质的排序方法，在逻辑上将序列看成一棵树，由于需要利用结点坐标之间的乘除特点，故不用序列的零位置。
首先将待排序序列构造成一个大顶堆（从最后一个分支结点开始，通过比较筛选确定该位置的结点数值比它的左右孩子都要大，然后从后往前筛选每一个分支结点，最终即可得到大顶堆）,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值，如此反复执行,便能得到一个有序序列了。

2. 复杂度分析

整个堆排序的时间复杂度: O(n*logn)

三、源程序及注释：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY 10000    //生成多大的数组
#define RANGE 10000   //数组的元素大小从1到RAGNE
void swap(int array[],int x,int y){
    int key=array[x];
    array[x]=array[y];
    array[y]=key;
}

void Down(int array[],int i,int n){ // 最后结果就是大顶堆
    int parent=i;                    // 父节点下标
    int child=2*i+1;            // 子节点下标
    while(child<n){
        if(child+1<n&&array[child]<array[child + 1]){ // 判断子节点那个大，大的与父节点比较
            child++;
        }
        if(array[parent]<array[child]){ // 判断父节点是否小于子节点
            swap(array,parent,child);     // 交换父节点和子节点
            parent=child;                 // 子节点下标 赋给 父节点下标
        }
        child=child*2+1; // 换行，比较下面的父节点和子节点
    }
}

void BuildHeap(int array[], int size){
    for(int i=size/2-1;i>=0;i--){ // 倒数第二排开始, 创建大顶堆，必须从下往上比较
        Down(array,i,size);       // 否则有的不符合大顶堆定义
    }
}

void HeapSort(int array[],int size){
    BuildHeap(array, size); // 初始化堆
    for (int i=size-1;i>0;i--){
        swap(array,0,i); // 交换顶点和第 i 个数据
        Down(array,0,i); // 重新建立大顶堆
    }
}

int main(){
	srand((unsigned)time(NULL)); //用时间做种，每次产生随机数不一样
	int array[10000];
    for (int i =0;i<ARRAY;i++){
        array[i]=rand()%RANGE+1;  
    }
    int size=sizeof(array)/sizeof(int);
    
    FILE *f;
	f=fopen("排序前.txt","w");
	for(int i=0;i<size;i++){
    		if(i==0){
    			fprintf(f,"%d",array[i]);	
			}
			else
    			fprintf(f," %d",array[i]);
		}
    fclose(f);
    
    HeapSort(array, size);

	FILE *f1;
	f1=fopen("排序后.txt","w");
	for(int i=0;i<size;i++)
    	{
    		if(i==0){
    			fprintf(f1,"%d",array[i]);
			}
			else
    			fprintf(f1," %d",array[i]);
		}
    fclose(f1);
    return 0;
}

四：运行输出结果：

随机产生10000个无序数后排序、贴出程序运行完成时的屏幕截图或者输出文件的内容。详见排序前后文件

五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：

重新巩固了生成随机数组以及文件读写方面的知识