算法|堆排序
2021/7/6 20:37:24
本文主要是介绍算法|堆排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
完成阅读您将会了解堆排序的:
- 算法思想
- 实现步骤
- 实践范例(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
让每一天足够精致,期待与您的再次相遇! ^_^
Williams JW. Algorithm 232: heapsort. Commun. ACM. 1964;7:347-8. ↩︎
图片引自Wikipedia,在此鸣谢。 ↩︎
这篇关于算法|堆排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现