java语言堆排序（Heap Sort）详解-蒲公英云

首先阐述一下其基本思想：

①、基本思想：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

②、算法描述：

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
③、动图演示：

④、完整的测试代码演示：

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
 * @author wanghuainan
 * @date 2021/5/28 16:13
 */
public class NandaoHeapSort {
    //自定义比较器
    public static class Naodaocomparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }
    public static void main(String[] args) {
        //默认小根堆
        PriorityQueue<Integer> testHeap = new PriorityQueue<>(new Naodaocomparator());
        testHeap.add(6);
        testHeap.add(0);
        testHeap.add(3);
        testHeap.add(2);
        System.out.println("非删除弹出："+testHeap.peek());
        testHeap.add(1);
        testHeap.add(8);
        System.out.println(testHeap.peek());
        while (!testHeap.isEmpty()) {
            System.out.println(testHeap.poll());
        }
        int testTime = 5;
        int maxSize = 20;
        int maxValue = 20;
        boolean successed = true;
        for(int i = 0;i < testTime; i++){
            int[] arr1 = generateRandomArray(maxSize,maxValue);
            int[] arr2 = copyArray(arr1);
            heapSort(arr1);
            comparator(arr2);
            if(!isEq(arr1,arr2)){
                successed = false;
                break;
            }
        }
        System.out.println(successed ? "Nice":"fail失败了");
        int[] arr = {6,1,3,2,4,5,9,6};
        printArray(arr);
        heapSort(arr);
        printArray(arr);
    }
    //打印数组
    private static void printArray(int[] arr) {
        if(arr == null){
            return;
        }
        for(int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    //比较两个数组是否相等
    private static boolean isEq(int[] arr1, int[] arr2) {
        if((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)){
            return false;
        }
        if(arr1 == null && arr2 == null){
            return true;
        }
        if(arr1.length != arr2.length){
            return false;
        }
        for(int i = 0;i < arr1.length;i++){
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }
    // 堆排序额外空间复杂度O(1)
    private static void heapSort(int[] arr1) {
        if(arr1 == null || arr1.length < 2){
            return;
        }
        // O(N*logN)
        for(int i = 0;i < arr1.length;i++){
            heapInsert(arr1,i);
        }
        // O(N)
        for(int i = arr1.length - 1;i >= 0;i--){
            heapify(arr1,i,arr1.length);
        }
        int heapSize = arr1.length;
        swap(arr1,0,--heapSize);
        // O(N*logN)
        while (heapSize > 0){
            heapify(arr1,0,heapSize);
            swap(arr1,0,--heapSize);
        }
    }
    //数值交换
    private static void swap(int[] arr1, int i, int j) {
        int temp = arr1[i];
        arr1[i] = arr1[j];
        arr1[j] = temp;
    }
    // arr[index]位置的数，能否往下沉
    private static void heapify(int[] arr1,int index, int heapSize) {
        int left = 2 * index + 1;// 左孩子的下标
        while (left < heapSize){// 下方还有孩子的时候
            /**
             *  两个孩子中，谁的值大，把下标给largest
             * 1）只有左孩子，left -> largest
             * 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
             * 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
             */
            int maxSize = left + 1 < heapSize && arr1[left]< arr1[left + 1] ? left + 1 : left;
            // 父和较大的孩子之间，谁的值大，把下标给largest
            maxSize = arr1[index] < arr1[maxSize] ? maxSize : index;
            if(maxSize == index){
                break;
            }
            swap(arr1,maxSize,index);
            index = maxSize;
            left = 2 * index + 1;
        }
    }
    // arr[index]刚来的数，往上浮
    private static void heapInsert(int[] arr1,int index) {
        while (arr1[index] > arr1[(index - 1) / 2]){
            swap(arr1,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    //JDK默认排序方法
    private static void comparator(int[] arr2) {
        Arrays.sort(arr2);
    }
    //数组复制
    private static int[] copyArray(int[] arr1) {
        if (arr1 == null  ){
            return null;
        }
        int[] arr2 = new int[arr1.length];
        for(int i = 0;i < arr1.length;i++){
            arr2[i] = arr1[i];
        }
        return arr2;
    }
    //对数器生成数组
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1)  * Math.random())];
        for(int i = 0;i < arr.length;i++){
            arr[i] = (int)((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
}

核心方法为：

// 堆排序额外空间复杂度O(1)
    private static void heapSort(int[] arr1) {
        if(arr1 == null || arr1.length < 2){
            return;
        }
        // O(N*logN)
        for(int i = 0;i < arr1.length;i++){
            heapInsert(arr1,i);
        }
        // O(N)
        for(int i = arr1.length - 1;i >= 0;i--){
            heapify(arr1,i,arr1.length);
        }
        int heapSize = arr1.length;
        swap(arr1,0,--heapSize);
        // O(N*logN)
        while (heapSize > 0){
            heapify(arr1,0,heapSize);
            swap(arr1,0,--heapSize);
        }
    }