- 算法设计与分析
- 家
- 算法基础知识
- DAA - 简介
- DAA - 算法分析
- DAA-分析方法
- 渐近符号和先验分析
- 时间复杂度
- 马斯特定理
- DAA - 空间复杂性
- 分而治之
- DAA-分而治之
- DAA - 最大最小问题
- DAA-归并排序
- DAA-二分查找
- 施特拉森矩阵乘法
- 唐叶算法
- 河内塔
- 贪心算法
- DAA-贪婪法
- 旅行商问题
- Prim 的最小生成树
- 克鲁斯卡尔的最小生成树
- Dijkstra 的最短路径算法
- 地图着色算法
- DAA-分数背包
- DAA - 带截止日期的作业排序
- DAA - 最佳合并模式
- 动态规划
- DAA-动态规划
- 矩阵链乘法
- 弗洛伊德·沃歇尔算法
- DAA - 0-1 背包
- 最长公共子序列
- 旅行商问题| 动态规划
- 随机算法
- 随机算法
- 随机快速排序
- 卡格的最低削减
- 费舍尔-耶茨洗牌
- 近似算法
- 近似算法
- 顶点覆盖问题
- 设置封面问题
- 旅行推销员近似算法
- 排序技巧
- DAA-快速排序
- DAA-冒泡排序
- DAA——插入排序
- DAA-选择排序
- DAA——希尔排序
- DAA-堆排序
- DAA——桶排序
- DAA——计数排序
- DAA - 基数排序
- 搜索技巧
- 搜索技术介绍
- DAA - 线性搜索
- DAA-二分查找
- DAA - 插值搜索
- DAA - 跳转搜索
- DAA - 指数搜索
- DAA - 斐波那契搜索
- DAA - 子列表搜索
- DAA-哈希表
- 图论
- DAA-最短路径
- DAA - 多级图
- 最优成本二叉搜索树
- 堆算法
- DAA-二叉堆
- DAA-插入法
- DAA-Heapify 方法
- DAA-提取方法
- 复杂性理论
- 确定性计算与非确定性计算
- DAA-最大派系
- DAA - 顶点覆盖
- DAA - P 级和 NP 级
- DAA-库克定理
- NP 硬课程和 NP 完全课程
- DAA - 爬山算法
- DAA 有用资源
- DAA - 快速指南
- DAA - 有用的资源
- DAA - 讨论
设计与分析-归并排序
归并排序是一种基于分治技术的排序技术。最坏情况的时间复杂度为 Ο(n log n),它是最常用和最接近的算法之一。
归并排序首先将数组分成相等的两半,然后以排序的方式将它们组合起来。
归并排序如何工作?
为了理解合并排序,我们采用一个未排序的数组,如下所示 -
我们知道,合并排序首先将整个数组迭代地分成相等的两半,除非达到Atomics值。我们在这里看到一个包含 8 个项目的数组被分成两个大小为 4 的数组。
这不会改变原始项目中的出现顺序。现在我们将这两个数组分成两半。
我们进一步划分这些数组,我们获得了无法再划分的Atomics值。
现在,我们以与分解它们完全相同的方式将它们组合起来。请注意这些列表的颜色代码。
我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中。我们看到 14 和 33 处于排序位置。我们比较 27 和 10,在 2 个值的目标列表中,我们首先放置 10,然后是 27。我们更改 19 和 35 的顺序,而 42 和 44 则按顺序放置。
在组合阶段的下一次迭代中,我们比较两个数据值的列表,并将它们合并到找到的数据值列表中,并将所有数据值按排序顺序排列。
最终合并后,列表已排序并被视为最终解决方案。
归并排序算法
归并排序不断地将列表分成相等的两半,直到无法再划分为止。根据定义,如果列表中只有一个元素,则认为它已排序。然后,合并排序合并较小的排序列表,同时保持新列表的排序。
步骤 1 - 如果列表中只有一个元素,则认为它已经排序,因此返回。
步骤 2 - 将列表递归地分为两半,直到无法再划分为止。
步骤 3 - 按排序顺序将较小的列表合并到新列表中。
伪代码
我们现在将看到合并排序函数的伪代码。正如我们的算法指出的两个主要功能 - 分割和合并。
合并排序与递归一起工作,我们将以同样的方式看到我们的实现。
procedure mergesort( var a as array ) if ( n == 1 ) return a var l1 as array = a[0] ... a[n/2] var l2 as array = a[n/2+1] ... a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) end procedure procedure merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure
例子
在下面的示例中,我们逐步展示了归并排序算法。首先,将每个迭代数组分为两个子数组,直到子数组只包含一个元素。当这些子数组无法进一步划分时,则进行合并操作。
分析
让我们考虑一下,归并排序的运行时间为T(n)。因此,
$$\mathrm{T\left ( n \right )=\left\{\begin{matrix} c & if\, n\leq 1 \\ 2\, xT\left ( \frac{n}{2} \ right )+dxn &otherwise \\ \end{matrix}\right.}\:其中 c\: 和\: d\: 是常量$$
因此,利用这个递推关系,
$$T\left ( n \right )=2^{i}\, T\left ( n/2^{i} \right )+i\cdot d\cdot n$$
$$As,\:\: i=log\: n,\: T\left ( n \right )=2^{log\, n}T\left ( n/2^{log\, n} \right )+log\, n\cdot d\cdot n$$
$$=c\cdot n+d\cdot n\cdot log\: n$$
$$因此,\: \: T\left ( n \right ) = O(n\: log\: n )。$$
例子
以下是此操作在各种编程语言中的实现 -
#include <stdio.h> #define max 10 int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 }; int b[10]; void merging(int low, int mid, int high){ int l1, l2, i; for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) { if(a[l1] <= a[l2]) b[i] = a[l1++]; else b[i] = a[l2++]; } while(l1 <= mid) b[i++] = a[l1++]; while(l2 <= high) b[i++] = a[l2++]; for(i = low; i <= high; i++) a[i] = b[i]; } void sort(int low, int high){ int mid; if(low < high) { mid = (low + high) / 2; sort(low, mid); sort(mid+1, high); merging(low, mid, high); } else { return; } } int main(){ int i; printf("Array before sorting\n"); for(i = 0; i <= max; i++) printf("%d ", a[i]); sort(0, max); printf("\nArray after sorting\n"); for(i = 0; i <= max; i++) printf("%d ", a[i]); }
输出
Array before sorting 10 14 19 26 27 31 33 35 42 44 0 Array after sorting 0 10 14 19 26 27 31 33 35 42 44
#include <iostream> using namespace std; #define max 10 int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 }; int b[10]; void merging(int low, int mid, int high){ int l1, l2, i; for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) { if(a[l1] <= a[l2]) b[i] = a[l1++]; else b[i] = a[l2++]; } while(l1 <= mid) b[i++] = a[l1++]; while(l2 <= high) b[i++] = a[l2++]; for(i = low; i <= high; i++) a[i] = b[i]; } void sort(int low, int high){ int mid; if(low < high) { mid = (low + high) / 2; sort(low, mid); sort(mid+1, high); merging(low, mid, high); } else { return; } } int main(){ int i; cout << "Array before sorting\n"; for(i = 0; i <= max; i++) cout<<a[i]<<" "; sort(0, max); cout<< "\nArray after sorting\n"; for(i = 0; i <= max; i++) cout<<a[i]<<" "; }
输出
Array before sorting 10 14 19 26 27 31 33 35 42 44 0 Array after sorting 0 10 14 19 26 27 31 33 35 42 44
public class Merge_Sort { static int a[] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 }; static int b[] = new int[a.length]; static void merging(int low, int mid, int high) { int l1, l2, i; for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) { if(a[l1] <= a[l2]) b[i] = a[l1++]; else b[i] = a[l2++]; } while(l1 <= mid) b[i++] = a[l1++]; while(l2 <= high) b[i++] = a[l2++]; for(i = low; i <= high; i++) a[i] = b[i]; } static void sort(int low, int high) { int mid; if(low < high) { mid = (low + high) / 2; sort(low, mid); sort(mid+1, high); merging(low, mid, high); } else { return; } } public static void main(String args[]) { int i; int n = a.length; System.out.println("Array before sorting"); for(i = 0; i < n; i++) System.out.print(a[i] + " "); sort(0, n-1); System.out.println("\nArray after sorting"); for(i = 0; i < n; i++) System.out.print(a[i]+" "); } }
输出
Array before sorting 10 14 19 26 27 31 33 35 42 44 0 Array after sorting 0 10 14 19 26 27 31 33 35 42 44
def merge_sort(a, n): if n > 1: m = n // 2 #divide the list in two sub lists l1 = a[:m] n1 = len(l1) l2 = a[m:] n2 = len(l2) #recursively calling the function for sub lists merge_sort(l1, n1) merge_sort(l2, n2) i = j = k = 0 while i < n1 and j < n2: if l1[i] <= l2[j]: a[k] = l1[i] i = i + 1 else: a[k] = l2[j] j = j + 1 k = k + 1 while i < n1: a[k] = l1[i] i = i + 1 k = k + 1 while j < n2: a[k]=l2[j] j = j + 1 k = k + 1 a = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0] n = len(a) print("Array before Sorting") print(a) merge_sort(a, n) print("Array after Sorting") print(a)
输出
Array before Sorting [10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0] Array after Sorting [0, 10, 14, 19, 26, 27, 31, 33, 35, 42, 44]