Sắp xếp vun đống
本页面将简要介绍堆排序．
定义
堆排序（英语：Heapsort）是指利用 二叉堆 这种数据结构所设计的一种排序算法．堆排序的适用数据结构为数组．
过程
堆排序的本质是建立在堆上的选择排序．
排序
首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；
之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；
以此类推，在第 \(n-1\) 次操作后，整个数组就完成了排序．
在数组上建立二叉堆
从根节点开始，依次将每一层的节点排列在数组里．
于是有数组中下标为 i 的节点，对应的父结点、左子结点和右子结点如下：
iParent ( i ) = ( i - 1 ) / 2 ;
iLeftChild ( i ) = 2 * i + 1 ;
iRightChild ( i ) = 2 * i + 2 ;
性质
稳定性
同选择排序一样，由于其中交换位置的操作，所以是不稳定的排序算法．
时间复杂度
堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 \(O(n\log n)\) ．
空间复杂度
由于可以在输入数组上建立堆，所以这是一个原地算法．
实现
C++ Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 void sift_down ( int arr [], int start , int end ) {
// 计算父结点和子结点的下标
int parent = start ;
int child = parent * 2 + 1 ;
while ( child <= end ) { // 子结点下标在范围内才做比较
// 先比较两个子结点大小，选择最大的
if ( child + 1 <= end && arr [ child ] < arr [ child + 1 ]) child ++ ;
// 如果父结点比子结点大，代表调整完毕，直接跳出函数
if ( arr [ parent ] >= arr [ child ])
return ;
else { // 否则交换父子内容，子结点再和孙结点比较
swap ( arr [ parent ], arr [ child ]);
parent = child ;
child = parent * 2 + 1 ;
}
}
}
void heap_sort ( int arr [], int len ) {
// 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
for ( int i = ( len - 1 - 1 ) / 2 ; i >= 0 ; i -- ) sift_down ( arr , i , len - 1 );
// 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
for ( int i = len - 1 ; i > 0 ; i -- ) {
swap ( arr [ 0 ], arr [ i ]);
sift_down ( arr , 0 , i - 1 );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 def sift_down ( arr , start , end ):
# 计算父结点和子结点的下标
parent = int ( start )
child = int ( parent * 2 + 1 )
while child <= end : # 子结点下标在范围内才做比较
# 先比较两个子结点大小，选择最大的
if child + 1 <= end and arr [ child ] < arr [ child + 1 ]:
child += 1
# 如果父结点比子结点大，代表调整完毕，直接跳出函数
if arr [ parent ] >= arr [ child ]:
return
else : # 否则交换父子内容，子结点再和孙结点比较
arr [ parent ], arr [ child ] = arr [ child ], arr [ parent ]
parent = child
child = int ( parent * 2 + 1 )
def heap_sort ( arr , len ):
# 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
i = ( len - 1 - 1 ) / 2
while i >= 0 :
sift_down ( arr , i , len - 1 )
i -= 1
# 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
i = len - 1
while i > 0 :
arr [ 0 ], arr [ i ] = arr [ i ], arr [ 0 ]
sift_down ( arr , 0 , i - 1 )
i -= 1
外部链接
Update history Edit this page on GitHub! OI-wiki CC BY-SA 4.0 and SATA