堆排序

有关 “堆” 知识的详解可以看这里——【堆】
其他经典比较类算法>排序算法可以看这里——【六大比较类算法>排序算法】

1. 建堆

在之前我们了解了堆，我们都知道大顶堆和小顶堆的特点：

• 小顶堆：任意节点的值 ≤ 其子节点的值。
• 大顶堆：任意节点的值 ≥ 其子节点的值。

而大顶堆的根节点是整棵树中最大的数，小顶堆的根节点是整棵树中最小的数。我们就可以根据这一点来进行排序的操作。

首先既然是堆排序，那么这个数组就得先是一个堆。现在我们随机给一个数组 {27，28， 65， 25， 15， 34， 19， 49， 18， 37 }。它是无序的且不满足堆的特点。

这个时候我们就可以利用向下调整算法来对这个数组进行建堆的操作：（以建小堆为例）

// 数组建堆算法
for (int i = (n - 1 - 1) / 2; i >= 0; --i){
	AdjustDown(arr, n, i);
}

2. 排序

建好堆后，这个时候这个数组已经变成了一个小顶堆。此时最小的数在最上面，已经被选出来了。现在我们可以将这个数与最后一个数，也就是最后一个叶子节点做交换，并且之后不把这个最小的数看作是堆内的数据（不删除），再对剩下的 $n-1$ 个数做向下调整再次构建一个小顶堆，选出次小的数，放在末尾。这样循环操作，我们就可以得到一个排好序的降序的数组。

下面是动图演示：

注意：构建小顶堆最后排出来的是降序的数组，如果想要升序的数组，则需要构建大顶堆。

// 向下调整法
// 建小堆
void AdjustDown(HPDataType* a, int n, int root){
    int parent = root;
    int child = 2 * parent + 1;
    while(child < n){
        // 防止没有右孩子       左右孩子比较
        if(child + 1 < n && a[child] > a[child + 1]){
            child++;  // 如果左孩子大，那就要选右孩子，因此++
        }
        // 父节点与小的那个孩子比较，如果父节点大，则交换
        if(a[parent] > a[child]){
            int temp = a[parent];
            a[parent] = a[child];
            a[child] = temp;
            parent = child;  // 更新下标
            child = 2 * parent + 1;  // 找到新的孩子然后继续比较
        }
        else{
            break;
        }
    }
}

// 堆排序（排逆序）
void HeapSort(int* a, int n){
	// 建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i){	
        // 建小堆和建大堆的向下调整函数内部判断条件略有不同
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	// 把最大的换到最后一个位置，不把最后一个数看作堆里的
	// 每次选出剩下数中最大的
	// 从后往前放
	while (end > 0){
		int tem = a[end];
		a[end] = a[0];
		a[0] = tem;
		// 选出次大的数
		AdjustDown(a, end, 0);
		--end;
	}
}

3. 算法分析

在上一篇文章我们分析过建堆的时间复杂度为 $O(N)$。

而向下调整算法的时间复杂度为 $O(lo{g}_{2}N)$。

所以堆排序的时间复杂度为 $O(Nlo{g}_{2}N)$。
空间复杂度为 $O(1)$

4. 总结对比

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n\log n)$ ~ $O(n^2)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$ ~ $O(n)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定