堆排序，假设需要从小到大排序。利用大顶堆
代码实现：
package sai.HeapSort; /** * 1,堆排序 * * @author WangSai * */ public class HeapSort { public static void main(String[] args) { int[] arr = { 1, 2, 5, 3, 6, 9 }; mySort(arr); } // 1，构建当前数组的大顶堆 // 2，把堆顶数字放到数组的尾部，并且数字长度减少一个 // 3，重复2。 private static void mySort(int[] arr) { // 异常值检测 if (arr == null || arr.length <= 0) return; // 把arr创建为大顶堆 buildMaxTopHeap(arr); System.out.println(arr[0]); int high = arr.length - 1; while (high > 0) { // 交换堆顶和堆尾数字 swap(arr, 0, high); high--; // 重新调整为大顶堆 adjustMaxHeap(arr, high, 0); } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } /** * 数字arr[i]和arr[high]交换 * * @param arr,数组 * @param i，带交换的数字的角标 * @param high，带交换的数字的角标 */ private static void swap(int[] arr, int i, int high) { int temp = arr[i]; arr[i] = arr[high]; arr[high] = temp; } /** * 把当前数组arr[0,high]创建大顶堆 * * @param arr,带排序数组 */ private static void buildMaxTopHeap(int[] arr) { int high = arr.length - 1; for (int i = (high - 1) / 2; i >= 0; i--) { adjustMaxHeap(arr, high, i); } } /** * 调整当前节点及其子树为大顶堆 * * @param arr,带排序数组 * @param high，数组的最后一个数字的角标 * @param i，带排序节点 */ private static void adjustMaxHeap(int[] arr, int high, int i) { int temp = arr[i]; for (int j = 2 * i + 1; j <= high; j = 2 * j + 1) { if (j <= high - 1 && arr[j] < arr[j + 1]) { j++; } if (temp < arr[j]) { arr[i] = arr[j]; i = j; } else break; } arr[i] = temp; } }