堆排序Java实现

堆概念：

是一种完全二叉树结构，分为大根堆和小根堆，每一个非叶子节点都大于（大根堆是大于，小根堆事小于）它的两个子节点。

堆排序：步骤分为三步：

1 ：初始化大根堆（小根堆也可以，本篇以大根堆为例）

2：交换堆顶最大值和数组最后一位，

3：交换位置后的堆进行大根堆调整

4：循环进行2步骤，交换堆顶和数组倒数第二位，第三位等等直到第一位。。。

时间复杂度分析：

初始化堆排序结构时间复杂度需要 N * logN

每一次交换后维护新的大根堆复杂度是logN，进行N次遍历交换，所以总的时间复杂度：N * logN

代码如下

import java.util.Arrays;

public class Test {

    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[7];
        arr[0] = 10;
        arr[1] = 11;
        arr[2] = 12;
        arr[3] = 5;
        arr[4] = 52;
        arr[5] = 1;
        arr[6] = 100;
        System.out.println("before");
        System.out.println(Arrays.toString(arr));

        initBuildHeap(arr, 0, arr.length - 1);
        System.out.println("init");
        System.out.println(Arrays.toString(arr));
        System.out.println("rebuild");
        for (int i = arr.length - 1; i >= 1; i--) {
            swap(arr, i, 0);
            rebuild(arr, 0, i - 1);
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("after");
        System.out.println(Arrays.toString(arr));
    }

    private static void initBuildHeap(int[] num, int index, int end) {

        if (num == null || index > end) {
            return;
        }
        boolean flag = true;
        for (int i = end; i >= index; i--) {
            int parent = (i - 1) / 2;
            if (num[i] > num[parent]) {
                swap(num, i, parent);
                flag = false;
            }
        }
        if (!flag) {
            initBuildHeap(num, index, end);
        }
    }

    public static void rebuild(int[] arr, int begin, int end) {
        if (arr == null || arr.length == 0 || begin >= end) {
            return;
        }
        int left = begin * 2 + 1;
        int right = begin * 2 + 2;
        if (left <= end && arr[begin] < arr[left]) {
            swap(arr, begin, left);
            rebuild(arr, left, end);
        }
        if (right <= end && arr[begin] < arr[right]) {
            swap(arr, begin, right);
            rebuild(arr, right, end);
        }
    }
}

打印结果

before
[10, 11, 12, 5, 52, 1, 100]
init
[100, 52, 12, 5, 11, 1, 10]
rebuild
[52, 10, 12, 5, 11, 1, 100]
[12, 1, 10, 5, 11, 52, 100]
[11, 1, 10, 5, 12, 52, 100]
[10, 1, 5, 11, 12, 52, 100]
[5, 1, 10, 11, 12, 52, 100]
[1, 5, 10, 11, 12, 52, 100]
after
[1, 5, 10, 11, 12, 52, 100]