预备知识：顺序存储的二叉树
一．顺序存储二叉树的性质
1. 第n个元素的左子节点：2*n+1
2. 第n个元素的右子节点：2*n+2
3. 第n个元素的父节点：（n-1）/2
二．顺序存储二叉树的遍历
堆排序：利用堆这种数据结构
堆分为：大顶堆、小顶堆
大顶堆：父节点永远都大于它的任何一个子节点（不论是左子节点还是右子节点）
升序排列使用：大顶堆
降序排列使用：小顶堆
把数组画成一颗完全二叉树：
已经可以把一个数组写成一个树了
假设我们可以把一个树转换成大顶堆
把最大的数字和最后一个数字交换
然后把最大的数字挪出来放到最后
此时堆已经不是一个大顶堆了，重新将其排列成一个大顶堆
这样可以每次都取出最大的那个堆顶元素（父节点）
如何将一个堆转化为大顶堆：从最后一个非叶子节点开始调整
【叶子节点：没有子节点的节点】
拿着这个节点跟它的子节点比较，如果不是最大的，那么就交换
7处理完毕后，处理8【顺序是从后往前处理下一个非叶子节点】
第一次将数组调整为大顶堆的结果：
import java.util.Arrays; //堆排序 public class HeapSort { public static void main(String[] args) { int[] arr = {9,6,8,7,0,1,10,4,2}; heapSort(arr); System.out.println(Arrays.toString(arr)); } /** * 把数组调整为一个大顶堆 * @param arr * @param size 第一次是把所有的数字都调整，调整后把最大的数字放到最后， * 第二次就不用调整那个最大的数字了 * @param index 调整哪一个数字：从最后一个非叶子节点开始调整(最后一个节点的父节点) */ public static void maxHeap(int[] arr,int size,int index) { //左子节点的下标 int left = index*2+1; //右子节点的下标 int right = index*2+2; //最大的节点的下标 int max = index; //父节点和两个子节点分别对比，找出最大的值(子节点存在) if(left<size && arr[left]>arr[max]) {//坑：left<size不是left<arr.length max = left; //就是：已经排好序的堆就不要再比较了 } if(right<size && arr[right]>arr[max]) { max = right; } //如果index就是最大的那么不需要交换位置,否则交换位置 if (max != index) { int temp = arr[max]; arr[max]=arr[index]; arr[index] = temp; //交换位置后可能会破坏之前排好的堆，所以之前排好的堆需要重新调整 //max是调整之后的位置 maxHeap(arr, size, max); } } public static void heapSort(int[] arr) { //1.将数组调整为大顶堆 //想全部节点都调整，不能只调整一个 //从最后一个非叶子节点开始调整(最后一个节点的父节点) int start = (arr.length-1-1)/2; // int start = (arr.length-1)/2; for(int i=start;i>=0;i--) { maxHeap(arr, arr.length, i); } //2.把数组中的第0个元素和堆中的最后一个数交换，再把前面处理为大顶堆 for (int j = arr.length-1;j>0;j--) { int temp = arr[j]; arr[j]=arr[0]; arr[0] = temp; //交换顺序后，把前面处理为大顶堆 maxHeap(arr, j, 0); } } }