堆排序Java实现

----

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {3,5,1,7,6,2};
        heapSort(arr);
        for (int i = 0; i < arr.length ; i++) {
            System.out.println(arr[i]);

        }
    }
    public static void heapSort(int[] arr){

        if(arr == null || arr.length<2){
            return;
        }
        //插入，使其变成一个大根堆
        for (int i = 0; i < arr.length ; i++) {
            heapInsert(arr,i);
        }
        //第一个数和最后一个数交换
        int size = arr.length;
        swap(arr,0,--size);
        while (size>0){
            heapfy(arr,0,size);
            swap(arr,0,--size);

        }

    }
    /*
    (index-1)/2为父节点的位置，不断的比较和父节点的大小
    这是一个向上调整的过程
     */

    public static void heapInsert(int[] arr,int index){
        //如果比父节点大，需要和父节点交换
        while (arr[index] > arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }

    }

    /*
    调整堆 ，左右两个孩子的最大值和我比，如果比我大，就和我交换，这是一个向下调整
    的过程
     */
    public static void heapfy(int[] arr,int index,int size){
        //左节点位置
        int left = index*2+1;
        while (left<size){
            //找左右两个孩子中较大的一个，left+1<size,确保不越界
            int largest = left+1<size && arr[left+1]>arr[left]?left+1:left;
            largest = arr[largest]>arr[index]?largest:index;
            if(largest == index){
                break;
            }
            //孩子比自己大，那么就需要调整了
            swap(arr,largest,index);
            index = largest;
            left = index*2+1;

        }
    }


    /*
    交换两个节点
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

---