算法-堆排序

整体架构流程

大顶推：是构建一个完整的二叉树
大顶推：即父节点的值大于左右子树的值。

循环构建大顶推
在给定的数组，既可以明确树的高度。
在循环的时候，构建树的高度从lgn至0。即从堆低往堆顶构建。
构建过程中：如果左右子树大于父节点，则交互数据后，在调整被交换的节点使其满足大顶推。

提取大顶堆获取排序值
从数组长度(i = a.length-1)至0循环：

1. 交换0和i的值（即大顶堆的跟节点，即最大值）。完成升序排序最大值在数组末尾。
2. 因将i的值替换到0的值位置，需要重新调整大顶堆。且将数组的长度限制小于i。

技术细节

package study.algorithm.sort;import java.util.Arrays;/*** 堆排序，是先构建一个完整的二叉树*/
public class HeapSort {public static void main(String... args){int[] arr = {12, 11, 13, 5, 6, 7};System.out.println("排序前："+ Arrays.toString(arr));sort(arr);System.out.println("排序后："+ Arrays.toString(arr));}public static void sort(int[] arr) {builderMaxHeap(arr);// 逐个提取堆顶元素（最大值）并调整堆// 大顶堆的，最大值的索引是0。for (int i = arr.length - 1; i > 0; i--) {// 将当前堆顶元素（最大值）与末尾元素交换(即i)// 交换完成之后， 大于等于i的索引不参(i至arr.length)与后续大顶堆调整。int tmp = arr[0];arr[0] = arr[i];arr[i] = tmp;//调整剩余元素为最大堆，将最大值放在索引为0的位置。//指定需要调整的数组长度 i,从0索引位置开始调整大顶对。//因上一步，将未尾值换到了索引为0的位置，而索引0的左右子树的值是剩余的最大值。maxHeap(arr,i,0);}}/*** 构建大顶推，即父节点的值，大于左右子树的值*/public static void builderMaxHeap(int[] arr) {int n = arr.length;for (int i = n / 2; i >= 0; i--) {maxHeap(arr, n, i);}}/*** 构建大顶推，即父节点的值，大于左右子树的值** @param arr 数组* @param n   需要调整整个数组的长度* @param i   父节点索引位置*/public static void maxHeap(int[] arr, int n, int i) {//最大值索引默认为i，i的左右子树在数组中索引的位置int largest = i;int right = 2 * i + 1;int left = 2 * i + 2;//如果左子树索引不越界(即存在左子树)，且左子树的值大于，最大值索引的值if (left < n && arr[left] > arr[largest]) {largest = left;}//如果右子树索引不越界(即存在右子树)，且右子树的值大于，最大值索引的值if (right < n && arr[right] > arr[largest]) {largest = right;}//说明父节点的值，小于左右子树的值//1. 调整堆的最大值位于父节点//2. 因左右子树的值，存在修改则需要调整当前修改节点的堆，满足大顶堆if (i != largest) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;maxHeap(arr, n, largest);}}
}

小结

构建大顶堆是从堆低往堆顶开始构建
每次获取大顶堆最大的值，完成排序