java堆排序

算法思想: 将数组构建成无须堆，再计算最大/最小堆顶，然后交换堆顶与堆尾的值，以数组[0, length - 2]的值重复上述步骤。这篇博文的图解讲的比较好，大家可以看一看；

算法实现：
下面是本人写的拙劣代码，图省事，迭代过程中会创建新数组，所以有不少空间开销，但适合理解算法思想，精简代码可以参照百度百科；

import com.google.common.collect.Lists;

import java.util.List;

import static java.util.stream.Collectors.joining;

public class Test {

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 4, 1, 0, 8, 6, 7, 9, 10, 11};
        List<Integer> list = heapSort(arr);
        String string = list.stream().map(x -> x.toString()).collect(joining(","));
        System.out.println(string);
    }

    public static List<Integer> heapSort(int[] arr) {
        List<Integer> result = Lists.newArrayList();
        adjustHeap(arr, result);
        return result;
    }

    public static void adjustHeap(int[] arr, List<Integer> result) {
        int len = arr.length;
        /**
         * 遍历非叶子节点
         */
        for (int i = len / 2 -1; i >= 0; i--) {
            if (arr[i] < arr[2 * i + 1]) {
                swap(arr, i, 2 * i + 1);
            }
            if (((2 * i + 2) < len) && (arr[i] < arr[2 * i + 2])) {
                swap(arr, i, 2 * i + 2);
            }
        }
        result.add(arr[0]);
        swap(arr, 0, arr.length - 1);
        if (arr.length > 1) {
            int[] temp = new int[arr.length - 1];
            System.arraycopy(arr, 0, temp, 0, arr.length - 1);
            adjustHeap(temp, result);
        } else {
            return;
        }
    }



    /**
     * 交换下标a与b对应位置的值
     *
     * @param arr   目标数组
     * @param a     下标a
     * @param b     下标b
     */
    public static void swap(int[] arr, int a, int b) {
        int value = arr[a];
        arr[a] = arr[b];
        arr[b] = value;
    }
}