堆排序Java实现以及使用场景

堆排序Java实现以及使用场景

堆排序是基于大小堆来实现的，利用数组中左右子树的数学规律来进行构建最大树或者是最小树，在这基础上将最大数或者是最小树下沉，并将树的长度减1，直到树的长度为1，最后数组即为排序后的数组

场景：跟快排一样是一个O(nLogn)的算法，但是在堆排序中有较多次数的交换，所以总体来说，是比不上快排的，但是如果你需要的不是整个排序，而是最大或者是最小的一部分，那么堆排序就具有很大优势了

实现：

private static void heapSort(int[] arrays){
        buildMaxHeap(arrays,arrays.length);
        for(int i = arrays.length;i>1 ;i--){
            swap(arrays,0,i-1);
            adjustHeap(arrays,0,i-1);
        }
    }

     
    private static void buildMaxHeap(int[] arrays ,int length){
        for(int i = (length>>1)-1;i>=0 ;i--){
            adjustHeap(arrays,i ,length);
        }
    }

    
    private static void adjustHeap(int[] arr ,int i ,int length){
        int left = (i<<1)+1 ;
        int right = (i<<1)+2 ;
        if(left < length && arr[left] > arr[i]){
            swap(arr,left,i);
            adjustHeap(arr,left ,length);
        }
        if(right < length &&arr[right] > arr[i]){
            swap(arr,right,i);
            adjustHeap(arr,right ,length);
        }
    }

    private static void swap(int[] arr , int i , int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

调用heapSort即可对数组进行排序