完成阅读您将会了解堆排序的:
- 算法思想
- 实现步骤
- 实践范例(C++/Rust)
1. 算法思想
堆排序(Heap Sort)是数据结构堆的一个具体应用,由 J. W. J. Williams 在1964年发表的堆排序[1]提出。关于堆的介绍请前往数据结构堆查看。
在堆的基础上,每次取出堆顶,再维护剩余堆的性质即可完成堆排序,如图1[2]。堆排序时间复杂度为\(\Theta(n\lg n)\),空间复杂度\(\Theta(1)\)。堆排序是原址排序(In-place Sort),但它是不稳定的排序算法。关于排序的稳定性,请前往快速排序查看。
2. 实现步骤
- 待排序序列构建为堆;
- 交换堆顶与堆尾;
- 更新堆大小;
- 从堆顶开始堆化;
- 重复以上过程直至堆大小为1。
3. 实践范例(C++/Rust)
问题描述:
为无序数组A做单调不减排序。
输入:无序数组A
输出:有序数组A
解答思路:
运用对堆排序算法对A进行原址排序。
伪代码1:堆化
变量说明:H\(\rightarrow\)堆数组;i\(\rightarrow\)堆化始发下标;left\(\rightarrow\)左子节点下标;right\(\rightarrow\) 右子节点下标
伪代码2:堆排序
变量说明:A\(\rightarrow\)待排序序列
C++解答:
void _heapfy(auto H, auto i, auto heap_size) noexcept {
auto right = i + 1 << 1, left = right - 1;
while (left < heap_size) {
auto largest = H[i] < H[left] ? left : i;
largest = right < heap_size && H[largest] < H[right] ? right : largest;
if (largest == i)
break;
std::swap(H[i], H[largest]);
i = largest;
right = i + 1 << 1;
left = right - 1;
}
}
void heap_sort(auto A, auto s) noexcept {
auto i = s >> 1;
while (i)
_heapfy(A, --i, s);
while (s > 1) {
std::swap(*A, A[--s]);
_heapfy(A, 0, s);
}
}
Rust解答:
fn _heapfy<T: std::cmp::PartialOrd>(H: &mut [T], mut i: usize, mut size: usize) {
let mut right = i + 1 << 1;
let mut left = right - 1;
while left < size {
let mut largest = if H[i] < H[left] { left } else { i };
largest = if right < size && H[largest] < H[right] { right } else { largest };
if largest == i { break; }
H.swap(i, largest);
i = largest;
right = i + 1 << 1;
left = right - 1;
}
}
pub fn heap_sort<T:std::cmp::PartialOrd>(A:&mut [T]){
let mut s=A.len();
let mut i=s>>1;
while i>0 {
i-=1;
_heapfy(A, i, s);
}
while s>1{
s-=1;
A.swap(0,s);
_heapfy(A,0,s);
}
}
4. 自我测试
伪代码实践:
N/A
LeetCode选荐:
N/A
让每一天足够精致,期待与您的再次相遇! ^_^