java语言堆排序（Heap Sort）详解

╰半夏微凉° 2022-10-17 00:39 91阅读 0赞

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

①、基本思想：堆排序（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，则整个排序过程完成。  
③、动图演示：  
 ![93824bbcbb3c16dbfd58a0e64d2c7c3c.png][]

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

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);
            }
        }

此示例详细分享了堆排序的原理，里面也有对数器的核心代码，均为通用性，实用性很高。

[93824bbcbb3c16dbfd58a0e64d2c7c3c.png]: /images/20221014/18390f459da24813bb72eae298f481b7.png