堆排序

原理

• 首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质
• 再将堆顶的元素，作为次大值，与数组倒数第二维元素交换，并维持残余堆的性质

• 以此类推，进行n-1次操作后，数组完成了排序

  性质

• 稳定性：和选择排序一样交换位置，故不稳定

• 时间复杂度：均为

代码

public void heap_sort(int[] a) {
    //堆化
    for (int i = (a.length - 1 - 1) / 2; i >= 0; i--) {
        sift_down(a, i, a.length - 1);
    }
    //交换元素，再对刚刚交换的元素进行堆化
    for (int i = a.length - 1; i > 0; i--) {
        int tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        sift_down(a, 0, i - 1);
    }
}
void sift_down(int[] arr, int start, int end) {
    int parent = start;
    int child = parent * 2 + 1;
    while (child <= end) {
        if (child + 1 <= end && arr[child] < arr[child + 1]) {
            child++;
        }
        if (arr[parent] >= arr[child]) {
            return;
        } else {
            int tmp = arr[parent];
            arr[parent] = arr[child];
            arr[child] = tmp;
            parent = child;
            child = parent * 2 + 1;
        }
    }
}