常用排序算法的实现（C语言版）-堆排序

chiyx

堆排序：
/***排序过程中使用到的堆的结构*/typedef struct heap {int heapSize;int *ap;int apLength;} Heap;/**调整i位置上的元素，以保持最大堆的性质*/void maxHeapify(int a[], int i, int hSize) {int l, r, largest;l = 2 * i + 1;r = l + 1;if (l < hSize && a[l] > a[i]) {largest = l;} else {largest = i;}if (r < hSize && a[r] > a[largest]) {largest = r;}if (largest != i) {swap(a, i, largest);maxHeapify(a, largest, hSize);}}/**构建最大堆*/Heap buildMaxHeap(int a[], int n) {Heap hp;int i;hp.ap = a;hp.heapSize = n;hp.apLength = n;for (i = n / 2 - 1; i >= 0; i--) {maxHeapify(a, i, n);}return hp;}/**堆排序算法*/void heapSort(int a[], int n) {int i;//build max-heapHeap heap = buildMaxHeap(a, n);for (i = n - 1; i > 0 ; i--) {swap(a, i , 0);heap.heapSize--;maxHeapify(a, 0, heap.heapSize);}}