完成阅读您将会了解归并排序的:
归并排序(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:1]
问题描述:
为无序数组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); } }
伪代码实践:
LeetCode选荐:
测试参考解答
让每一天足够精致,期待与您的再次相遇! ^_^
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,在此鸣谢。 ↩︎ ↩︎