堆排序（java）

将待排序序列构造成一个大顶堆，此时序列的最大值就是堆顶元素，将它和数组的末尾元素交换，再将剩余的n-1个元素构造成大顶堆,如此反复便能得到一个有序序列。时间复杂度为O(nlogn)，是不稳定的排序算法。

代码

void heapSort(int[] arr){
    // 先将数组aar构造成一个大顶堆
    for (int i = arr.length / 2; i >= 0; i--) {
        headAdjust(arr, i, arr.length - 1);
    }

    for (int i = arr.length - 1; i >= 1; i--) {
        swap(arr, 0,  i);  // 将对顶数字和数组最后一个数字交换，
        headAdjust(arr, 0,  i - 1); // 将数组的0~i-1个数字重新调整为大顶堆
    }

}
// 已知arr[start~end]中的数字除了arr[start]之外均符合大顶堆的定义
// 调整arr[start]数字，使得arr[start~end]成为一个大顶堆
void headAdjust(int[] arr, int start, int end){
    int tmp = arr[start];
    int j;
    for (j = start * 2 + 1; j <= end; j = j * 2 + 1) {
        if ((j + 1) < end && arr[j] < arr[j + 1]) {
            j ++;
        }
        if (tmp > arr[j]) {
            break;
        }
        arr[start] = arr[j];
        start = j;
    }
    arr[start] = tmp;
}