数据结构算法笔记#5.3:排序(3)

堆排序和树形选择排序（锦标赛排序）都是运用了二叉树的思想，将时间复杂度压到 O(nlogn) 。

堆排序

堆

在介绍堆排序之前，我先介绍一下堆。堆分为 小顶堆 和 大顶堆 ，一个小顶堆需要满足以下条件：

是一棵 完全二叉树
每个结点的值一定小于它的两个子结点

而大顶堆则与之相对，是一棵每个结点的值都大于它两个子结点的完全二叉树。

很显然，一个小顶堆的根结点一定是整个堆的最小值，而大顶堆的根结点一定是最大值。

要获得升序序列，我们需要构造一个 大顶堆 ；降序序列则相反。（先记着，学完后就知道为什么了）

堆排序

我们如果将堆按顺序存在数组里（索引从0开始），那么对于结点 arr[i] ，其子结点就分别为 arr[2*i+1] 和 arr[2*i+2] （自己画个图推导一下就知道了）。

友情提醒

对于某些数据结构教材，数组的第0位是不存放数据的，索引从1开始，这时子结点就应该是 arr[2*i] 和 arr[2*i+1]

对于一个杂乱的数组，我们要将其构造为大顶堆，第一次当然要自下而上针对所有结点调整一次：针对每个结点，将其与子结点中较大的进行判断，若比其本身小，自然符合规定不必更改；若子结点有大于它的值，那就对其进行交换，将最大值置于父结点位，当前结点置于子结点位，同时由于当前结点下沉了一层，其当前子结点有可能会大于它，所以我们要顺着这条路继续向下调整，直到叶结点。

完成一次调整后，这时的根结点就是整个序列中的最大值，此时我们只需将他与整个序列的最后一个结点交换位置即可将最大值归位。然后开始下一次调整，但这时我们要注意两个细节：首先是调整的过程中需要避开最后那些已经归位的值，不然就白排了；其次是不再需要调整所有结点，而只需要顺着根结点向下调整一次就够了，没被影响到的结点不必考虑。

不断重复以上过程n次，就能得到完整的升序序列，由于二叉树的特性，每次调整的时间复杂度为 O(logn) ，整个堆排序的时间复杂度即为 O(nlogn) 。

//堆排序 O(nlogn)
template <class Type>
void HeapSort(Type arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) HeapAdjust(i, n, arr);  //自下而上调整堆,构造大顶堆
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);   //堆顶元素放到最后
        HeapAdjust(0, i, arr);  //此时调整堆就只需要在[0,i-1]的范围
    }
}
template <class Type>
void HeapAdjust(int st, int ed, Type arr[]) {  //在[st,ed-1]的范围调整堆
    Type temp = arr[st];
    for (int i = st * 2 + 1; i < ed; i = i * 2 + 1) {
        if (i + 1 < ed && arr[i] < arr[i + 1]) i++;
        if (temp > arr[i]) break;  //父大于两个子,不用调整
        arr[st] = arr[i];          //否则将父设为子结点中较大的,并顺着大子向下调整
        st = i;
    }
    arr[st] = temp;  //将temp放回最终的位置
}

//前置函数
template <class Type>
void swap(Type& a, Type& b) {
    Type temp = a;
    a = b;
    b = temp;
}