void HeapSort(int *a, int n) //堆排序 { //建立堆 for(int i = n/2-1; i >= 0; i--) //非叶节点最大序号值为n/2 HeapAdjust(a, i, n); for(int j = n-1; j > 0; j--) SWAP(a[0], a[j]); //交换堆顶和最后一个元素， HeapAdjust(a, 0, j); //重新调整成为大顶堆 }
#define SWAP(a,b) { a ^= b; b ^= a; a ^= b;} void HeapAdjust(int *a, int i, int n) //调整堆 { int lchild = 2*i+1; //i的左孩子节点序号 int rchild = 2*i+2; //i的右孩子节点序号 int max = i; //临时变量 if(i <= n/2-1) //如果i不是叶节点就不用进行调整 if(lchild < n && a[lchild] > a[max]) max = lchild; if(rchild < n && a[rchild] > a[max]) max = rchild; if(max != i) SWAP(a[i], a[max]); //避免调整之后以max为父节点的子树不是堆 HeapAdjust(a, max, n); }