堆排序(Heapsort) gaunthan Posted on Aug 7 2016 ? Sorting ? ? Algorithm ? ## 思想 堆是一种特殊的数据结构,它可以在常数时间内获取结构中的最优值,随后以对数时间维护最优结构。我们可以执行 n 次这样的操作,这样就可以以 $O(nlogn)$ 时间进行排序。基于这种想法的排序算法叫做**堆排序**(heap sort):先建立 n 个元素的二叉堆(花费 $O(n)$ 时间),然后执行 n 次 `DeleteMin` 操作(每次删除最小操作花费 $O(logn)$) ,因此总的运行时间是 $O(nlogn)$。 上面算法的主要问题在于使用了一个附加的数组,以存放输出结果,因此存储需求增加了一倍。然而这是可以避免的:在每次 DeleteMin 之后,堆缩小了1。因此,位于堆中最后的单元可以用来存放刚刚删去的元素。使用这种策略,在最后一次 DeleteMin 后,该数组将以递减的顺序包含这些元素。如果想要这些元素以递增的顺序排列,那么可以改变序的特性使堆成为一个最大堆。 总的来说,堆排序以 $O(nlogn)$ 时间复杂度,$O(1)$ 空间复杂度完成排序。注意堆排序是不稳定排序算法。 ## 实现 假设输入是一个数组 a、与其元素个数 N,则使用堆排序对输入进行升序处理的实现如下: 1. 构建一个最大堆 2. 将堆中的最后元素与第一个元素交换,缩减堆的大小并进行下滤 3. 执行 n - 1 次第二步操作 代码如下: ```c #define Parent(i) ((i) >> 1) #define LeftChild(i) ((i) << 1) #define RightChild(i) (((i) << 1) + 1) /* 最大堆下滤操作 */ static void PercDown(ElementType a[], int i, int n) { int child; ElementType tmp; for (tmp = a[i]; LeftChild(i) < n; i = child) { child = LeftChild(i); if (child != n - 1 && a[child + 1] > a[child]) child++; if (tmp < a[child]) a[i] = a[child]; else break; } a[i] = tmp; } /* 最大堆排序算法 */ void HeapSort(ElementType a[], int n) { int i; for (i = n / 2; i >= 0; --i) // build heap PercDown(a, i, n); for (i = n - 1; i > 0; --i) { // deleteMax Swap(&a[0], &a[i]); PercDown(a, 0, i); // 注意执行该下滤操作时,堆大小为i } } ``` ## References - MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010. - ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013. 赏 Wechat Pay Alipay 计数排序(Counting sort) 插入排序(Insertion sort)