算法|归并排序
2021/7/6 20:37:26
本文主要是介绍算法|归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
完成阅读您将会了解归并排序的:
- 算法思想
- 实现步骤
- 实践范例(C++/Rust)
1. 算法思想
归并排序(Merge Sort)由 John von Neumann 在1945年创造,最早描述在 Knuth, Donald 于1998年撰写的 “The Art of Computer Programming” [1]一书中。归并排序是分治思想(Divide & Conquer)的典型应用,每次将排序任务派发给下层二分子序列,并将完成子序列进行归并(Merge),如图1[2]。由于二分子序列的排序过程是独立的,可以并行(Parallelly)排序。
归并排序的时间复杂度为\(\Theta(n\lg n)\),空间复杂度为\(\Theta(n)\)。归并排序是稳定的排序算法,关于排序稳定的介绍参见快速排序。
2. 实现步骤
排序:
- 二分当前序列,递归排序两个子序列;
- 归并两个子序列.
归并:过程示意如图2[2:1]
- 申请容纳待合并子序列的空间;
- 为子序列各自分配头指针;
- 比较两个头指针指向的元素,并将符合比较要求的元素添加到新空间;
- 更新各自头指针,并继续比较至其中一个子序列遍历到尾;
- 如有剩下的子序列,将其直接添加至新空间。
2. 实践范例(C++/Rust)
问题描述:
为无序数组A做单调不减排序。
输入:无序数组A
输出:有序数组A
解答思路:
运用归并排序算法对A进行排序。
伪代码1:归并排序A
变量说明:A \(\rightarrow\)待排序序列;\(B_1 \rightarrow\)A左半部分;\(B_2 \rightarrow\)A右半部分
伪代码2:归并子序列\(B_1\)与\(B_2\)
变量说明:同伪代码1
C++解答:
void _merge(auto A1, auto s1, auto A2, auto s2, auto A)noexcept { auto iter = A; while (s1 && s2) *iter++ = *A1 < *A2 ? (--s1, *A1++) : (--s2, *A2++); std::memcpy(iter, s1 ? A1 : A2, (s1 ? s1 : s2) * sizeof(A[0])); } template <class T> void merge_sort(T *A, auto s)noexcept { if (s == 2 && *A > A[1]) std::swap(*A, A[1]); else if (s > 2) { auto s1 = s >> 1, s2 = s - s1; T A1[s1], A2[s2]; std::memcpy(A1, A, s1 * sizeof(T)); std::memcpy(A2, A + s1, s2 * sizeof(T)); merge_sort(A1, s1); merge_sort(A2, s2); _merge(A1, s1, A2, s2, A); } }
Rust解答:
fn _merge<T: Clone + std::cmp::PartialOrd>(A1: &Vec<T>, A2: &Vec<T>, A: &mut Vec<T>) { let (mut p1, mut p2, mut i, s1, s2) = (0, 0, 0, A1.len(), A2.len()); while p1 < s1 && p2 < s2 { if A1[p1] < A2[p2] { A[i] = A1[p1].clone(); p1 += 1; } else { A[i] = A2[p2].clone(); p2 += 1; } i += 1; } let (mut p, B, s) = if p1 < A1.len() { (p1, A1, A1.len()) } else { (p2, A2, A2.len()) }; while p < s { A[i] = B[p].clone(); p += 1; i += 1; } } pub fn merge_sort<T: Clone + std::cmp::PartialOrd>(A: &mut Vec<T>) { let s = A.len(); if s == 2 && A[0] > A[1] { A.swap(0, 1); } else if s > 2 { let mut A1 = A[..s >> 1].to_vec().clone(); let mut A2 = A[s >> 1..].to_vec().clone(); merge_sort(&mut A1); merge_sort(&mut A2); _merge(&A1, &A2, A); } }
2. 自我测试
伪代码实践:
- 归并排序递归版受栈内存限制,无法直接应用在大规模数据上,请将归并排序改写成迭代版。
LeetCode选荐:
- Sort List
测试参考解答
让每一天足够精致,期待与您的再次相遇! ^_^
Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0. ↩︎
图片引自Wikipedia,在此鸣谢。 ↩︎ ↩︎
这篇关于算法|归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求