堆排序（Heap Sort）
1.什么是堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
2.算法步骤
- 创建一个堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互换；
- 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
- 重复步骤 2，直到堆的尺寸为 1。
3.代码实现
public static void main(String[] args) { int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9}; buildSort(arr); System.out.println(Arrays.toString(arr)); } private static void buildSort(int[] tree) { buildHeap(tree); for (int i = tree.length - 1; i >= 0; i--) { swap(tree, 0, i); heapify(tree, 0, i); } } private static void buildHeap(int[] tree) { int parent = (tree.length / 2) - 1; for (int i = parent; i >= 0; i--) { heapify(tree, i, tree.length); } } private static void heapify(int[] tree, int i, int length) { int leftChild = 2 * i + 1; int rightChild = 2 * i + 2; int max = i; if (leftChild < length && tree[leftChild] > tree[max]) { max = leftChild; } if (rightChild < length && tree[rightChild] > tree[max]) { max = rightChild; } if (max != i) { swap(tree, max, i); heapify(tree, max, length); } } private static void swap(int[] tree, int max, int i) { int temp = tree[max]; tree[max] = tree[i]; tree[i] = temp; }
4.输出结果
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
