堆排序(学习数据结构算法之必修堆排序)

堆排序（Heapsort）是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，平均时间复杂度为Ο(nlogn)。

堆排序的流程是先将目标序列建立成一个最大堆，然后将堆顶的最大值放在序列的末尾，并且忽略已经排好序的部分，重复此过程得到最终的排序结果。

堆排序实现

Java语言实现堆排序：

public static void heapsort(int[] arr){    int n = arr.length;    // 构建堆（初始状态看成是一个无序的完全二叉树）    for (int i = n / 2 - 1; i >= 0; i--)        adjustHeap(arr, i, n);    // 将堆顶元素与末尾元素交换，最大的元素沉到数组末端    for (int i = n - 1; i > 0; i--)    {        swap(arr, 0, i);        adjustHeap(arr, 0, i);    }}private static void adjustHeap(int[] arr, int i, int length){    int temp = arr[i];    // i结点的左子结点下标    for (int k = i * 2   1; k < length; k = k * 2   1)    {        // 如果左子结点小于右子结点，k指向右子结点        if (k   1 < length