复习堆排序

堆的定义：

堆是一个具有以下性质的二叉树：每个结点的值都大于或者等于其左右孩子结点的值，称之为大顶堆。反之称之为小顶堆。

那么，在代码中如何表示大小顶堆？

arr[i]>=arr[2*i+1]&&arr[i]>=arr[2*i+2]//大顶堆

arr[i]<=arr[2*i+1]&&arr[i]<=arr[2*i+2]//小顶堆

堆排序の思想

1. 先把待排序序列构建成一个大（小）顶堆

2. 这时，整个序列的最大值就是堆顶的根节点（也就是数组的第一个元素）

3. 将其与末尾元素进行交换，此时末尾就是最大值

4. 然后将剩余的n-1个元素重新构造成一个新的堆，这样就得到n-1个元素的次小值，如此反复，就能得到一个有序序列——[重复（1），（2），（3）步骤]

代码实现：

import java.util.Arrays;
public class heapSort {
    public static void main(String[] args){
        int[] arr={25, 30, 11, 7, 22, 16, 18, 33, 40, 55};
        int temp=0;
        for(int i=arr.length/2-1;i>=0;i--){//从左往右，从下往上寻找非叶子节点进行初始的堆排序
            adjustHeap(arr,i, arr.length);
        }

        for(int j=arr.length-1;j>=0;j--){//初始堆建成后，首尾的元素进行交换，此时大顶堆的结构被破坏
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);//因为是首尾交换所以只有最顶部的结点不符合顶堆的定义，中间的非叶子节点均符合堆顶义，所此时的i等于0，也就是只从顶部开始调整
        }
        System.out.println("排序后的数组为："+Arrays.toString(arr));
    }
     /**
     * 
     * @param arr 待排序数组
     * @param i 以i为父节点进行堆排序的树（数组）
     * @param length 数组长度
     */
    public static void adjustHeap(int[] arr,int i,int length){
        int temp=arr[i];
        for(int k=2*i+1;k<length;k=2*k+1){//k指向i的较大的一个子结点
            if((k+1<length)&&arr[k]<arr[k+1]){//判断i叶子结点的左右结点的大小，如果左边的小于右边的，则k++
                k++;
            }
            if(arr[k]>temp){//如果该子结点大于它的父结点，则将该子结点赋值给父节点
                arr[i]=arr[k];
                i=k;//以k为父节点继续和它的子节点比较
            }
        }
        arr[i]=temp;//将最开始保存的arr[i]放到末尾
    }
}