入门算法：堆排序

上手难度：★★★

算法复杂度：O (nlgn)

排序思想：

对堆结构比较了解的话就很好理解
利用大顶堆的性质，将最大的顶点元素换到最后一个位置，然后数组长度减1，再将剩余的堆重新构建一个大顶堆，然后又将最大的顶点元素换到最后一个位置，此时的最后一个位置实际上是倒数第二个位置，依次往复，一边缩小数组的长度，一边将最大的顶点元素倒序放到合适的位置即可实现排序

代码实现：

public class HeapSort {

    public static int[] heapSort(int[] arr){

        int len = arr.length;

        buildMaxHeap(arr, len);

        //倒序遍历
        for (int i = len - 1; i > 0; i--) {
            //倒序将值换到第一个位置
            swap(arr, 0, i);
            //控制接下来要交换的数组长度
            len--;
            //再将剩余的元素构建一个新的大顶堆，依次往复，最终得到一个从小到大的顺序数组
            heapify(arr, 0, len);
        }
        return arr;
    }

    /**
     * 构建一个大顶堆
     */
    private static void buildMaxHeap(int[] arr, int len) {
        //从倒数第一个父节点开始
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    /**
     * 大顶堆的序号是从0开始的，不然left就是等于2*i了
     * 这个方法的目的是把大值换到i的位置
     */
    private static void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        //当存在左孩子并且左孩子大于父节点时，父节点的索引置为左孩子的索引
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        //当存在右孩子并且右孩子大于父节点时，父节点的索引置为右孩子的索引
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        //当父节点的索引值被替换了，就交换值，交换的结果是大值被换到父节点了，并且针对小值继续向下尝试交换
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        heapSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}

优点：思路较容易理解