大根堆排序

原理

假设待排序目标为数组arr，可将其视为一个完全二叉树。在大根堆排序中，根节点为最大值，我们循环将根取出，并减少大根堆的长度和调整堆使之堆维持大根堆，直至取出堆中全部节点数据。因为我们每次都是取出大根堆的最大值，故取出数据便有序了。

完全二叉树父节点和叶子节点的索引关系：
已知叶子节点索引index,则父节点索引 (index-1)/2
已知父节点索引index,则左叶子节点索引2*index+1,右叶子节点索引2*index+2

步骤

    创建大根堆

         从零开始遍历数组，将当前节点视为叶子节点，并于其父节点比较，大于则与父节点交换          值，并将父节点视为叶子节点，重复比较操作，直至根节点；小于则结束本次遍历。

    /**
     * 向堆中插入元素,并维持大根堆
     * 原理：数组末尾插入的新元素和其父元素对比，大则交换位置
     * @param arr 存储堆元素的数组
     * @param index 插入位置
     */
    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;
        }
    }

    /**
     * 交换2个位置的值
     * @param arr 目标数组
     * @param i 位置1
     * @param j 位置2
     */
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    堆排序

        排序是通过循环将大根堆的根交换至堆尾，每次循环将堆长减1，并调整剩余堆使之维持大根      堆。

    /**
     * 堆排序
     * @param arr 存储堆元素的数组
     */
    public static void heapSort(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
        // 1.创建大根堆
        for (int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }

        System.out.println("创建时的大根堆："+Arrays.toString(arr));

        // 开始排序
        int heapSize = arr.length;
        // 2.先交换一次堆顶的元素和堆的最后一个元素，再令大根堆长度减1
        swap(arr,0,--heapSize);
        // 3.重复交换和调整过程，每次将最大值放置大根堆尾，再使堆长度减1，再调整堆使之保持大根堆，最终使堆从不小到大排列
        while (heapSize>0){
            // 调整0～heapSize的元素保持大根堆
            heapify(arr,0, heapSize);
            // 交换
            swap(arr,0,--heapSize);
        }

        System.out.println("堆排序完成后的堆："+Arrays.toString(arr));
    }

    /**
     * 调整堆：每次堆顶和堆尾交换后，堆长度减1，重新调整堆，使之保持大根堆
     * @param arr 目标数组
     * @param index 根节点
     * @param heapSize 堆长
     */
    public static void heapify(int[] arr, int index, int heapSize){
        // 左叶子节点
        int leftIndex = 2*index + 1;
        // 0~heapSize-1是大根堆，当左叶子节点位置小于大根堆的长度，则进行调整；否则index就是叶子节点，退出循环。
        while (leftIndex < heapSize){
            // 寻找左叶子节点和右叶子节点的最大值，当右叶子节点存在且大于左叶子节点，largestIndex才为右叶子节点，否则为左叶子节点
            int largestIndex = leftIndex+1<heapSize&&arr[leftIndex+1]>arr[leftIndex]?leftIndex+1:leftIndex;

            // 左右叶子节点最大值和index节点比较值的大小，来判断是否进行交换
            largestIndex = arr[largestIndex] >arr[index]?largestIndex:index;
            // 若当前节点大于左右叶子节点的话，就无需交换了
            if (largestIndex == index){
                break;
            }

            swap(arr, largestIndex, index);

            // 交换后当前位置跳到叶子节点，重复以上动作，直至结束。
            index = largestIndex;
            leftIndex = 2*index+1;
        }
    }

总结

建堆时间复杂度：O(n)

排序时间复杂度：O(nlog2n)

时间复杂度 = O(n)+O(nlog2n)=O(nlog2n)

空间复杂度：O(1)