算法 - 堆排序

import java.util.Random;

public class HeapSort<T extends Comparable> {

    public void sort(T[] arr) {
        printArr(arr, " => 初始数组");
        for (int i = arr.length - 1; i > 0; i--) {
            buildHeap(arr, 0, i);
            printArr(arr, " => 构建大根堆");
            swap(arr, 0, i);
            printSign(0, i);
        }
    }

    private void buildHeap(T[] arr, int rootIndex, int end) {
        int leftChildIndex = rootIndex * 2 + 1;
        if (leftChildIndex > end) {
            return;
        }
        if (arr[rootIndex].compareTo(arr[leftChildIndex]) < 0) {
            swap(arr, rootIndex, leftChildIndex);
            backCheck(arr, rootIndex);
        }
        buildHeap(arr, leftChildIndex, end);
        int rightChildIndex = rootIndex * 2 + 2;
        if (rightChildIndex > end) {
            return;
        }
        if (arr[rootIndex].compareTo(arr[rightChildIndex]) < 0) {
            swap(arr, rootIndex, rightChildIndex);
            backCheck(arr, rootIndex);
        }
        buildHeap(arr, rightChildIndex, end);
    }

    private void backCheck(T[] arr, int rootIndex) {
        if (rootIndex == 0) {
            return;
        }
        int fatherIndex = (rootIndex - 1) / 2;
        if (arr[fatherIndex].compareTo(arr[rootIndex]) < 0) {
            swap(arr, fatherIndex, rootIndex);
        }
        backCheck(arr, fatherIndex);
    }

    private void swap(T[] arr, int a, int b) {
        T temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    private void printSign(int a, int b) {
        String[] arr = new String[]{" "," "," "," "," "," "," "," "," "," "," "};
        arr[a] = "^";
        arr[b] = "^";
        for (String n : arr) {
            System.out.print(n);
        }
        System.out.println(" => 交换");
    }

    public void printArr(T[] arr, String message) {
        for (T n : arr) {
            System.out.print(n);
        }
        System.out.print(message);
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 11;
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new Random().nextInt(10);
        }
        HeapSort hs = new HeapSort();
        hs.sort(arr);
    }

    /**
     * 92134594608 => 初始数组
     * 98946152304 => 构建大根堆
     * ^         ^ => 交换
     * 96844152309 => 构建大根堆
     * ^        ^  => 交换
     * 84634150299 => 构建大根堆
     * ^       ^   => 交换
     * 64523140899 => 构建大根堆
     * ^      ^    => 交换
     * 53402146899 => 构建大根堆
     * ^     ^     => 交换
     * 43402156899 => 构建大根堆
     * ^    ^      => 交换
     * 42301456899 => 构建大根堆
     * ^   ^       => 交换
     * 31204456899 => 构建大根堆
     * ^  ^        => 交换
     * 20134456899 => 构建大根堆
     * ^ ^         => 交换
     * 10234456899 => 构建大根堆
     * ^^          => 交换
     *
     * => 遍历次数：log(n) + log(n-1) + log(n-2) + ... + log(1)
     * => 时间复杂度：O(nlogn)
     * => 稳定性：不稳定
     */

}