堆排序：利用堆这种数据结构所设计的一种排序算法。
大堆： 根节点值大于子节点的值，对应为升序序列。
小堆： 根节点值小于子节点的值，对应为降序序列。
堆排序实现的两个步骤：
创建堆堆排序下述例子是进行大堆创建：
创建大堆：图例 创建步骤： 寻找最后一个分支的根节点(记为pos)pos挨个减小，对每个分支，都进行大堆排列。根节点比子节点值大终止条件：pos < 0,不再进行大堆创建。 大堆排序：升序 排序步骤： 堆顶元素和末尾元素值交换最大值排在末尾，该值不再做交换调整堆结构，满足大堆定义。重复执行步骤1，2，直到达到堆顶位置C代码实现：
void ShiftDown(int *arr, int left, int right, int pos) { int i = pos;//根节点 int j = 2 * i + 1 + left;//子节点 int n = right - left; int tmp = arr[i]; while (j < n) { if (j + 1 < n && arr[j + 1] > arr[j])//找子节点最大值 j++; if (arr[j] > tmp)//子节点比根节点大 { arr[i] = arr[j];//根节点值等于子节点的值 i = j;//往下调整 j = 2 * i + 1; } else break; } arr[i] = tmp;//循环退出，根节点的值等于最开始的arr[pos]值 } void HeapSort(int *arr, int left, int right) { int n = right - left; int pos = (n - 2) / 2 + left;//寻找最后一个分支的根节点 while (pos >= 0)//建堆 { ShiftDown(arr, left, right, pos--); } int end = n; while (end >= 2)//排序 { end--; Swap(&arr[end], &arr[left]);//交换堆顶和尾部元素 ShiftDown(arr, left, end, left); } }堆排序整体步骤：
建堆：大堆或小堆。先找到最后一个分支的根节点。再对个分支都进行调整。排序：堆顶和末尾数据交换，调整堆结构，尾部下标-1。再进行排序。特性总结：
时间复杂度：O(N*logN)空间复杂度：O(1)稳定性：不稳定