从键盘任意输入一组数， 比如：3216549870。要求对它进行排序，使它顺序排列。
我理解的堆排序思路如下：
NO.1 首先想着让这组数按下面这种方式形成完全二叉树树型结构。
A
我先给出这棵完全二叉树所具备的一些基本性质：
a: 不管这组数是奇数个还是偶数个，假设总数为count，倒数第一个非叶子节点的下标总是 count / 2 - 1。 （你可以列举奇数个试一下）
b: 叶子节点下标都大于count / 2 - 1，小于count。
c: 左孩子的下标 = 父节点下标 * 2 + 1。右孩子的下标 = 父节点下标 * 2 + 2。
NO.2 接着通过调整上面的树来构造大根堆（所有父节点的值都比其左右孩子值大的完全二叉树），步骤如下（若题目要求逆序排列，则构造小根堆，两者思路很相似）：
第一步：对树A的倒数第一层处理 。先比较0和5的值，5大于0，则不动；接着比较8和7，8大于7，用8（8与7中更大的）和6比较，8大于6，交换8和6，这样交换是为了把尽可能大的数往上移动。在交换完毕后，6处于叶子节点位置，最后一层便调整完毕了，得到下面树B：（此步其实处理了下标为4和3的元素，使其分别形成大根堆，没明白先往下看）
A
B
第二步：对树B倒数第二层进行处理。先比较4和9，9大于4，用9和1比较，9大于1，交换9和1；接着比较8和5，8大于5，用8和2比较，8大于2，交换8和2，因为在8和2交换后，2处于非叶子节点位置，所以应将6，7中更大的那个数和2比较，7大于2，交换7和2，交换完毕后，2处于叶子节点位置，本层便处理完毕。得到下面这棵树：（此步其实处理了下标为2和1的元素，使其分别形成大根堆）
C
第三步：处理第二层（对第2步调整后的树处理），比较8和9，9大于8，用9和3比较，9大于3，交换9和3，此时，因为在9和3交换后，3处在非叶子节点位置，所以应用4（4与1中更大的）和3比较，4大于3，交换4和3，交换完毕后，3处于叶子节点位置，本层调整完毕。得到下面这棵树：（此步其实处理了下标为0的元素，使其形成大根堆）
这棵树便成了大根堆。 上面便是构造大根堆的过程。
NO.3 因为在上面这大根堆中，9(这组数中最大的)的位置恰好是下标为0的，交换9和最末尾的0，便把最大值放到最末尾了。
NO.4 接着把上面这棵树继续调整为大根堆（9不用考虑），调整思路很简单：从下标为0的位置，即0所处位置开始，往下调整，直到调整到叶子节点为止。
调整过程： 比较8和4，8大于4，用8和0比较，8大于0，交换8和0，因为8和0交换，0处在非叶子节点位置，所以应用7（7，5中更大的那个数）和0比较，7大于0，交换7和0，交换完毕后，0仍处在非叶子节点位置，继续往下比较，最终得到下面这棵树（也是大根堆）：
接着交换8（下标为0的）和2（倒数第二个），再忽略8，继续构造大根堆，大根堆构造好了交换下标为0的和倒数第三个，依次循环，直到可忽略的数字为这组数总数减1时停下，此时，你会发现这组数已经顺序排列了！
现在我希望你能把这堆排序的整个思路串起来想一下。
第一步：形成树（当然此步不需要任何操作）。
第二步：构造大根堆。
第三步：交换下标为0和末尾的，交换后使末尾往前移动一位(--count 实现)。
第四步：从下标为0的往下调整，继续形成大根堆。
第五步：重复第三步和第四部，直到末尾移动到下标为0处，便顺序了。
稍加思考发现，思路可以更简便些，上面第二步可以修改为：停留在第一次刚好形成大根堆的前一步（即将要调整下标为0的那个节点），然后紧接着做第四步，然后做第三步，再四三四三步循环。
现在最终思路出来了！
第一步：形成树（当然此步不需要任何操作）。
第二步：停留在构造成功大根堆的前一步。
第三步：从下标为0的往下调整，形成大根堆。
第四步：交换下标为0和末尾的，交换后使末尾往前移动一位(--count 实现)。
第五步：重复第三步和第四部，直到末尾移动到下标为0处，便顺序了。
开始贴代码了：
#include <stdio.h> #include <malloc.h>
void adjuctHeap(int i, int *arr, int count); void heapSort(int *arr, int count); void adjuctHeap(int i, int *arr, int count) {
int tmp; int max; while(i <= count / 2 - 1) { // 条件判断检测是否到了叶子节点 tmp = 2 * i + 2 >= count ? 0 : arr[2 * i + 2]; //总数为偶数，最后一个父节点没有右孩子 max = arr[2 * i + 1] >= tmp ? 2 * i + 1 : 2 * i + 2; //max值：左右孩子中更大的那个孩子节点的下标 if(arr[max] > arr[i]) { tmp = arr[max]; arr[max] = arr[i]; arr[i] = tmp; i = max; } else
break; } } void heapSort(int *arr, int count) { int i; int tmp;
for(i = count / 2 - 1; i > 0; i--) { // 停留在构造成功大根堆的前一步。 count / 2 - 1 表示倒数第一个非叶子节点。 adjuctHeap(i, arr, count); } while(count > 1) { adjuctHeap(0, arr, count); // 构造大根堆 tmp = arr[0]; arr[0] = arr[count - 1]; // 交换 arr[count - 1] = tmp; --count; // 末尾往前移动 } } int main() { int i; int *arr; int count; printf("please input the count of numbers:"); scanf("%d", &count); arr = (int *) calloc(sizeof(int), count); printf("please input the numbers:"); for(i = 0; i < count; i++) { scanf("%d", &arr[i]); } heapSort(arr, count); for(i = 0; i < count; i++) { printf("%d ", arr[i]); } printf("\n"); free(arr); return 0; }
结果
please input the count of numbers:10
please input the numbers:3 2 1 6 5 4 9 8 7 0
0 1 2 3 4 5 6 7 8 9