Java：堆排序

1.步骤

先确定数组是升序排序或是降序排序。若是升序，则将数组创建为大根堆，降序则创建为小根堆。这里以升序为例。

第一步：将数组创建为大根堆。同时设置 usedSize == arr.length;

第二步：此时根为最大值，将根与最后的值进行对换，并 usedSize--;

第三步：将新的 usedSize 个元素用向下调换的方法重新排为大根堆。

第四步：如此重复至 usedSize == 0; 此时 arr 排序完成

2.代码

    // 堆排序public static void heapSort(int[] array) {// write code  herecreateHeap(array);int end = array.length - 1;while (end > 0) {swap(array, 0, end);siftDown(array, 0, end);end--;}}private static void createHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {siftDown(array, parent, array.length - 1);}}private static void siftDown(int[] array, int parent, int end) {int child = 2 * parent + 1;while (child < end) {if (child + 1 < end && array[child] < array[child + 1]) {child++;}if (array[parent] < array[child]) {swap(array, parent, child);parent = child;child = 2 * parent + 1;} else {break;}}}