堆排序

今天看到一篇面经，算法题是手写堆排序，《算法》放在书架已经有一段时间了，想试试能不能写出来，然而并没有，所以记录一下

自顶到底构造堆

这是一道 lintcode上面的题目堆化

构造一个堆只需要从左到右遍历数组，每次只要保证所遍历到的位子能满足堆的条件

public class Solution {
    /*
     * @param A: Given an integer array
     * @return: nothing
     */
    public void heapify(int[] A) {
        
        for (int i = 0; i < A.length; i++) {
            swim(A, i);
        } 
    }
    // 上浮
    private void swim(int[] A, int i) {
        while(i > 0 && A[i] < A[(i-1) / 2]) {
            swap(A, i, (i-1) / 2);
            i = (i-1) / 2;
        }
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

自底到顶构造堆

而堆排序采用的是自底到顶构造堆，每次把第一个元素和最后一个元素交换，交换之后把第一个元素下沉，同时堆数组减一，下面是代码

public class Heap {

    private static void heapSort(int[] array) {
        int len = array.length - 1;
        for (int i = (len - 1) / 2; i >= 0; i--) {
            sink(array, i, len);
        }
        printArr(array);
        while (len >= 0) {
            swap(array, 0, len);
            sink(array, 0, --len);
        }
    }

    private static void sink(int[] array, int i, int len) {
        while (i * 2 + 1 <= len) {
            int j = i * 2 + 1;
            if (j + 1 <= len && array[j+1] > array[j]) j++;
            if (array[i] > array[j]) break;
            swap(array, i, j);
            i = j;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] array = {2, 3, 1, 6, 4, 5, 2, 1};
        heapSort(array);
        printArr(array);
    }

    private static void printArr(int[] array) {
        Arrays.stream(array).forEach(a -> System.out.print(a + " "));
        System.out.println();
    }
}