堆排序是是指利用堆这种数据结构所设计的一种排序算法。
c语言的实现如下:
#include <stdio.h> #define SIZE 10 //打印数组 void display(int array[],int size){ printf("the array is:"); int i; for(i=0;i<size;i++){ printf("%d ",array[i]); } printf("\n"); } //创建堆,使最大的数位于树根 void createHeap(int array[], int size){ int parent,child,temp; //刚开始时,parent的值为最后一个父节点,依次往前将斤左右孩子中较大的节点与父节点交换,最后使树根为最大数 for(parent=(size+1)/2-1;parent>=0;parent--){ //获取父节点的左孩子 child = parent*2+1; //如果该父节点存在右孩子,并且比做孩子大,则使用右孩子,否则还是使用左孩子 if((child+1)<=size){ if(array[child+1] > array[child]){ child++; } } //将左右孩子中较大者与父节点交换 if(array[parent] < array[child]){ temp = array[parent]; array[parent] = array[child]; array[child] = temp; } } } //堆排序 void heap(int array[], int size){ int i,temp; for(i=size-1;i>=0;i--){ //创建堆,使最大的数位于树根 createHeap(array,i); //将树根和最后一个节点交换 temp = array[i]; array[i] = array[0]; array[0] = temp; display(array,SIZE); } } int main(void){ int array[SIZE]={34,45,1,39,21,68,65,100,4,51}; display(array,SIZE); //堆排序函数 heap(array,SIZE); display(array,SIZE); return 0; }