堆排序——heap-sort

#include <stdio.h> #include <malloc.h> void init(int A[],int length); void print_A(int A[],int length); int LEFT(int i);//计算左叶节点的下标 int RIGHT(int i);//计算右叶结点的下标 void MAX_HEAPIFY(int A[],int i);//计算以i为跟节点的大根堆 void BUILD_MAX_HEAP(int A[],int length);//从最大非叶结点开始自底向上建立大根堆 void heap_sort(int A[],int length);//堆排序算法实现 int heap_size; /****************堆排序算法**************************/ int main() { printf("堆排序算法的实现:\n"); int length; printf("请输入数组长度:length="); scanf("%d",&length); heap_size=length; int *A = (int*)malloc(length * sizeof(int)); init(A,length); printf("待排序数组:\n"); print_A(A,length); heap_sort(A,length); printf("数组排序完成:\n"); print_A(A,length); free(A); return 0; } /***************************************************/ /*************初始化数组****************************/ void init(int A[],int length) { printf("\n请输入数组元素:"); int i; for(i=0;i<length;i++) { scanf("%d",&A[i]); printf("A[%d]=%d",i,A[i]); printf("\n"); } printf("\n"); } /***************************************************/ /*****************打印数组元素**********************/ void print_A(int A[],int length) { int i; for(i=0;i<length;i++) printf("%d ",A[i]); printf("\n"); } /****************************************************/ /*******************计算左叶节点的下标***************/ int LEFT(int i) { return (2*i+1); } /****************************************************/ /*******************计算右叶节点的下标***************/ int RIGHT(int i) { return (2*i+2); } /****************************************************/ /****************建堆的具体实现MAX_HEAPIFY***********/ void MAX_HEAPIFY(int A[],int i) { int l,r,largest,middle; l=LEFT(i); r=RIGHT(i); if(l<heap_size && A[l]>A[i]) largest = l; else largest= i; if(r<heap_size && A[r]>A[largest]) largest = r; if(largest!=i) { middle=A[largest]; A[largest]=A[i]; A[i]=middle; MAX_HEAPIFY(A,largest); } } /****************************************************/ /******************建立大根堆************************/ void BUILD_MAX_HEAP(int A[],int length) { int i; for(i=((length/2)-1);i>=0;i--)//length/2-1,为第一个非叶结点 MAX_HEAPIFY(A,i); } /****************************************************/ /*********************heap-sort实现******************/ void heap_sort(int A[],int length) { BUILD_MAX_HEAP(A,length); int i,middle; for(i=length-1;i>0;i--) { middle=A[0]; A[0]=A[i]; A[i]=middle; heap_size--; MAX_HEAPIFY(A,0); } } /****************************************************/