算法技术手册（原书第2 版）

排序算法

｜

65

排序算法

ڼ1֫

ڼ2֫ ڼ3֫

ڼ4֫

ڼ5֫

图 4-5：样例堆 a 有 16 个不同元素的样例堆 b 这些元素的标签 c 存储在数组中的堆

可以看到，结果堆中的大数最终都会被“抬升”（也就是说，它们会和左侧较小的元素

进行交换）。图

4-6

中的灰色方格描述了

heapify

中交换的元素对——它们总共有

13

对——相比图

4-3

中插入排序中总的元素交换次数，这个数字要远远小得多。

在处理大小为

n

的数组

A

时，

堆排序

将其切分成两个互异的子数组，即

A

[0,

m

)

和

A

[

m

,

n

)

，

它们分别代表一个大小为

m

的堆和一个具有

n

－

m

个元素的有序子数组。随着

i

从

n

－

1

迭代到

1

，

堆排序

通过交换堆中的最大元素（在

A

[0]

位置

)

和

A

[

i

]

，使得有序子数组

A

[

i

,

n

)

的大小不断增长。之后，堆排序会执行

heapify

来将

A

[0,

i

)

重新改造成一个合法堆。结

果得到的非空子数组

A

[

i

,

n

)

将为有序数组，因为堆

A

[0,

i

)

中最大的元素保证小于等于这

个有序子数组

A

[

i

,

n

)

中的任何一个元素。

4.4.1 使用环境

堆排序

不是稳定排序。虽然

堆排序

避免了很多导致

快速排序

性能退化的令人讨厌的（大

都是令人尴尬的！）情况，但在平均情况下，

快速排序

还是要比

堆排序

表现得更好。

4.4.2 解决方案

例

4-4

给出了堆排序的

C

语言实现。

66

｜

第

4

章

图 4-6：在一个初始有序的数组上执行 buildHeap 操作

例

4-4

：堆排序的

C

语言实现

static void heapify (void **ar, int(*cmp)(const ...