堆排序（Heap Sort） O(nlog2(n)) 不稳定

介绍

堆排序是选择排序的一种，利用堆这种数据结构进行排序的一种算法。堆近似完全二叉树，分为大根堆和小根堆，子节点永远小于或者大于父节点的值。

特性

• 左孩子 idx：2*i+1
• 右孩子 idx：2*i+2
• 父节点 idx：（i-1）/2
• 最后一个非叶子节点 idx：（n/2）-1

证：
对于最后一个左孩子节点的index：

1. idx = n-1 => 父节点idx：(n-1-1)/2 = (n/2)-1
2. idx = n-2 => 父节点idx：(n-2-1)/2 = (n/2)-1

算法描述

• 第一步先将无序数组构建成大根堆
• 将堆顶元素，也就是index=0的元素和无序数列的最后一个元素进行交换。
• 交换以后，此时堆顶可能违反了堆的性质，因此需要把当前的无序堆调整为新堆。
• 调整以后，重复步骤2-4，直到无序数列的个数为1，有序数列的个数为n-1，此时序列有序

稳定性

不稳定，因为在进行堆的构建的时候，相同数值的相对位置有可能发生了改变。

动图展示

首次构建堆

heapSort1.gif

堆排序过程

headSort2.gif

代码实现

public class HeapSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28, 29};
        print(arrays);
        int[] res = heapSort(arrays);
        print(res);
    }

    /**
     * 27   6   27  42  23  15  38  50  35  14  40  28  29
     * 42   40  38  35  15  29  27  6   27  14  23  28  50
     * 40   35  38  28  15  29  27  6   27  14  23  42  50
     * 38   35  29  28  15  23  27  6   27  14  40  42  50
     * 35   28  29  14  15  23  27  6   27  38  40  42  50
     * 29   28  27  14  15  23  27  6   35  38  40  42  50
     * 28   14  27  6   15  23  27  29  35  38  40  42  50
     * 27   14  27  6   15  23  28  29  35  38  40  42  50
     * 27   14  23  6   15  27  28  29  35  38  40  42  50
     * 23   14  15  6   27  27  28  29  35  38  40  42  50
     * 14   6   15  23  27  27  28  29  35  38  40  42  50
     * 15   6   14  23  27  27  28  29  35  38  40  42  50
     * 6    15  14  23  27  27  28  29  35  38  40  42  50
     * 6    15  14  23  27  27  28  29  35  38  40  42  50
     */
    private static int[] heapSort(int[] arr) {
        //首次构建大根堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }

        for (int len = arr.length - 1; len > 0; len--) {
            swap(arr, 0, len);
            //这里因为之前已经构建过一次堆了，大部分节点数据符合堆性质，只需要对所有非叶子节点进行堆结构的调整
            maxHeapify(arr, 0, len / 2 + 1);
            print(arr);
        }
        return arr;
    }

    private static void maxHeapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int maxIdx = i;
        if (left < len && arr[left] > arr[maxIdx]) {
            maxIdx = left;
        }
        if (right < len && arr[right] > arr[maxIdx]) {
            maxIdx = right;
        }
        if (i != maxIdx) {
            swap(arr, i, maxIdx);
            maxHeapify(arr, maxIdx, len);
        }
    }

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

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}