堆排序正确版本

#include <iostream>void swap(int* a, int* b){*a = *a ^ *b;*b = *a ^ *b;*a = *a ^ *b;};void siftDown(int* a, int idx, int n){int curIdx = idx;int swapIdx;while (curIdx * 2 < n){swapIdx = curIdx;if (a[swapIdx] < a[curIdx * 2 + 1])swapIdx = curIdx * 2 + 1;if (curIdx * 2 + 2 <= n && a[swapIdx] < a[curIdx * 2 + 2])swapIdx = curIdx * 2 + 2;if (swapIdx == curIdx)break;swap(&a[swapIdx], &a[curIdx]);curIdx = swapIdx;}};void heapify(int* a, int n){int curIdx = (n - 1) / 2;while(curIdx >= 0){siftDown(a, curIdx, n);curIdx--;}};void heapSort(int* a, int n){heapify(a, n);for (int i = n; i > 0; i--){swap(&a[0], &a[i]);siftDown(a, 0, i - 1);}};int main(int argc,char *argv[]){int a[10] = {24, 1145, 21, 10, 4, 5, 9, 13, 7, 101};  heapSort(a, 9);return 0;}

堆排序(Heap Sort)是使用堆这一数据结构概念产生的排序算法，堆概念上是一个近似完全二叉树(Complete Binary Tree)，性质为：子节点始终小于(大于)父节点。

实现时，使用数组来储存树，从0号位置开始储存的话，父节点在位置i，子节点则为2*i+1和2*i+2。

这里需要用以下函数：

Heapify, SiftDown, HeapSort(堆排序调用函数)

算法流程如下：(这里讨论升序排列)

1. 最大堆创建。即为0号单元为最大元素。从(n - 1) / 2号元素向前进行siftdown，n为数组最末尾索引。从(n-1)/2开始而不是从n开始的原因是，从(n-1)/2+1到n的结点都为叶子结点，所以siftdown操作并不会有任何变化。

2. 取一个索引每次向前移动1，用来保存最大数值，每次将0号元素与此元素交换。

3. 交换元素后，需要做SiftDown操作，将当前堆(堆始终在缩小，因为后面部分的数据渐渐被排序)最大元素置于0号索引。

4. 重复2，直到堆大小变为1

第一次尝试写算法思想，欢迎讨论，指出不足！