算法导论 第六章 堆排序
堆是一个棵完全二叉树，通常用一个数组表示。这样的数组有两个属性：lenght(A)是数组中的元素个数，heap-size(A)是存放在A中的堆的元素个数。
堆排序的时间复杂度为O(nlgn).
给定堆中结点i的下标，其父为i/2,其左孩子为i*2，右孩子为i*2 + 1。
堆分为大根堆和小根堆。小根堆通常在构造优先级队列时使用。
常用的过程有：max-heaplify （堆调整）、build-max-heap （堆构造）、heap-sort （堆排序）。
以下程序根据书中思想而来：
1 /** 2 * Max Heap Sort 3 * It is a in-place sort. Its time is O(nlgn). 4 * An array A[1...n] has the following features: 5 * i is among 1 and n. 6 * its parent is i/2 (i >> 1); 7 * its left child is i*2 (i << 1); 8 * its right child is i*2 + 1 (i << 1 + 1; 9 * parent >= {left child, right child}10 * ---------------------------------------------11 */12 #include<stdio.h>13 14 void buildmaxheap(int* A, int length);15 void maxheap(int* A, int i, int length);16 void maxheapsort(int* A, int length);17 18 void buildmaxheap(int* A, int length) {19 int i = 0;20 for (i = length >> 1; i >= 1; i--) {21 maxheap(A, i, length);22 }23 }24 25 void maxheap(int* A, int i, int length) {26 int left = i << 1;27 int right = left + 1;28 int largest = i;29 30 if (left <= length && A[left] > A[largest]) {31 largest = left;32 }33 34 if (right <= length && A[right] > A[largest]) {35 largest = right;36 }37 38 if (largest != i) {39 A[0] = A[largest];40 A[largest] = A[i];41 A[i] = A[0];42 maxheap(A, largest, length);43 }44 }45 46 void maxheapsort(int* A, int length) {47 int i = length;48 49 if (A == NULL) return;50 51 buildmaxheap(A, length);52 53 // We need n-1 loop to get the other in order.54 for(;i >= 2;i--) {55 A[0] = A[i];56 A[i] = A[1];57 A[1] = A[0];58 59 maxheap(A, 1, i - 1);60 }61 }62 63 int main() {64 int A[] = {0,2,8,7,1,3,5,6,4};65 int len = sizeof(A) / sizeof(int) - 1;66 int i = 1;67 68 maxheapsort(A, len);69 70 for (i = 1; i <= len; i++)71 printf("%d,",A[i]);72 73 printf("\n");74 return 0;75 }转载于:https://www.cnblogs.com/lotushy/archive/2012/01/03/2311127.html
相关资源：数据结构—成绩单生成器