07.堆排序

目录介绍

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。

2.排序过程

1.先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
2.再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
3.由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
4.直到无序区只有一个元素为止。
image

3.代码实现

代码如下所示

static void max_heap(int[] num, int start, int end) {
    int dad = start;
    int son = dad * 2 + 1;

    while (son < end) {
        if (son + 1 < end && num[son] < num[son + 1])
            son++;

        if (num[dad] > num[son])
            return;
        else {
            num[dad] ^= num[son];
            num[son] ^= num[dad];
            num[dad] ^= num[son];
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

static void heap_sort(int[] num) {
    for (int i = num.length / 2 - 1; i >= 0; --i) {
        max_heap(num, i, num.length);
    }

    for (int i = num.length - 1; i >= 0; --i) {
        num[i] ^= num[0];
        num[0] ^= num[i];
        num[i] ^= num[0];

        max_heap(num, 0, i);
    }
}