堆是一棵完全二叉树。
其中每个节点的值都不大于其父节点的堆，被称为大根堆；
其中每个节点的值都不小于其父节点的堆，被称为小根堆；
在非降序排列中，需要使用的是大根堆。以上图中的大根堆序列arr[7]为例，arr[0]的左孩子是arr[1]，右孩子是arr[2]；arr[1]的左孩子是arr[3]，右孩子是arr[4]。所以arr[i]的左孩子节点是arr[2*i+1]；arr[i]的右孩子节点是arr[2*i+2]。
简单来说堆排序分为两个操作，分别是（1）创建堆，（2）排序堆。（本质上来说，两个操作的过程就是不断调整堆的过程）
还是以序列{ 4, 6, 3, 0, 2, 5, 1 }为例：
时间复杂度： 创建初始堆最多需要2N次比较和交换，它的时间复杂度为O( N )。排序堆的过程中，最多需要交换2NlogN次，所以空间复杂度为O( NlogN )。两个操作综合来看，堆排序的时间复杂度为O( NlogN )；
空间复杂度：需要一个临时变量保存当前的父节点， 所以空间复杂度为O( 1 )；
稳定性：在堆排序的过程中，堆顶会和堆尾交换，可能会出现相同数据前后位置关系发生改变的情况，所以是不稳定的。
#include <stdio.h> void Swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } /* * 调整堆的过程 */ void HeapAdjust(int arr[], int parent, int length) { int temp = arr[parent]; int child = 2 * parent + 1; while(child < length) { //选择左右子节点中较大值 if(child + 1 < length && arr[child] < arr[child+1]) child++; //如果父节点大于子节点，则结束 if(temp >= arr[child]) break; //如果父节点小于子节点，则将子节点的值赋于父节点 else arr[parent] = arr[child]; parent = child; child = 2 * child + 1; } arr[parent] = temp; } void HeapSort(int arr[], int length) { //创建初始堆 for (int i = length / 2; i >= 0; i--) HeapAdjust(arr, i, length); //对堆进行排序操作 for (int j = length - 1; j > 0; j--) { Swap(&arr[0], &arr[j]); HeapAdjust(arr, 0, j); } } int main() { int arr[] = {4,6,3,0,2,5,1}; int length = sizeof(arr)/sizeof(arr[0]); printf("排序前:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } HeapSort(arr, length); printf("\n排序后:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } return 0; }
