堆排序

public class HeapSort {

    public static void main(String []args){

        int [] arr = {20,50,20,40,70,10,80,30,60};

        heapSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    private static void heapSort(int[] arr) {

        if (arr == null || arr.length<2){

            return;

        }

        //构建大顶堆

        for (int i = arr.length>>1; i >=0; i--) {

            adjustHead(arr,i,arr.length);

        }

        //交换顶部文件并调整堆结构

        for (int j = arr.length-1; j >0 ; j--) {

            adjustHead(arr,0,j);

            swap(arr,0,j);

        }

    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    private static void adjustHead(int[] arr, int i, int length) {

        int temp = arr[i];

        for (int j = i*2+1; j < length; j=j*2+1) {

            if (j+1<length && arr[j]<arr[j+1]){

                j++;

            }

            if (arr[j]>temp){

                arr[i] = arr[j];

                i = j;

            } else {

                break;

            }

        }

        arr[i] = temp;

    }

//    private static void heapSort(int[] arr) {

//

//        //构建大顶堆

//        for (int i = arr.length/2; i >=0; i--) {

//            adjustHeap(arr,i,arr.length);

//        }

//        //交换堆顶元素与末尾元素，调整堆结构

//        for (int j = arr.length-1; j >0 ; j--) {

//            swap(arr, 0,j);

//            adjustHeap(arr,0,j);

//        }

//    }

//

//    private static void swap(int[] arr, int i, int j) {

//        int temp = arr[i];

//        arr[i]= arr[j];

//        arr[j]=temp;

//    }

//

//    private static void adjustHeap(int[] arr, int i, int length) {

////        int temp = arr[i];

////        for (int k = i*2+1; k < length; k = k*2+1) {

////            if (k+1<length && arr[k]<arr[k+1]){

////                k++;

////            }

////            if (arr[k]>temp){

////                arr[i]= arr[k];

////                i = k;

////            } else {

////                break;

////            }

////        }

////        arr[i] = temp;

//

//        int temp = arr[i];

//        for (int j = i*2+1; j < length; j=j*2+1) {

//            if (j+1<length && arr[j]<arr[j+1]){

//                j++;

//            }

//            if (arr[j]>temp){

//                arr[i] = arr[j];

//                i = j;

//            } else {

//                break;

//            }

//        }

//        arr[i]= temp;

//    }

}