分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)

简介: 分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)

目录


分治法

算法思想

时间效率分析

合并排序


正文


分治法


算法思想


    分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关,但它的确是当之无愧的:很多非常有效的算法实际上就是这个通用算法的特殊实现。其实,分治法是按照以下方案工作的。


       (1)将一个问题划分为同一类型的若干子问题,子问题最好规模相同。

       (2)对这些子问题求解(一般使用递归方法,但在问题规模足够小时,有时也会利用另一个算法)。

       (3)有必要的话,合并这些子问题的解,以得到原始问题的答案。


       分治法的流程可以参见下图,该图描述的是将一个问题划分为两个较小子问题的例子,也是最常见的情况(至少那些设计运行在单CPU机器上的分治算法是这样的)。

555.png


时间效率分析


       在分治法最典型的运用中,问题规模为n的实例被划分为两个规模为n/2的实例。更一般的情况下,一个规模为n的实例可以划分为b个规模为n/b的实例,其中α个实例需要求解(这里,a和b是常量,a≥1,b>1)。为了简化分析,我们假设n是b的幂,对于算法的运行时间T(n),我们有下列递推式:


T(n) =aT(n / b)+ f(n)

     其中,f(n)是一个函数,表示将问题分解为小问题和将结果合并起来所消耗的时间(对于求和的例子来说,a = b = 2,f(n)= 1)。上述递推式被称为通用分治递推式(generaldivide-and-conquer recurrence)。显然,T(n)的增长次数取决于常量a和b的值以及函数f(n)的增长次数。在分析许多分治算法的效率时,可以应用下列定理来大大简化我们的工作。


       主定理        如果在递推式(5.1)中 f(n)e e(n*),其中d≥0,那么

666.gif


合并排序


       合并排序是成功应用分治技术的一个完美例子。对于一个需要排序的数组A[0..n -1],合并排序把它一分为二:A[0..[n / 2| - 1]和A[ [n / 2 ]..n-1],并对每个子数组递归排序,然后把这两个排好序的子数组合并为一个有序数组。

       下图演示的是用合并排序算法对数列8,3,2,9,7,1,5,4进行排序的操作过程。


   代码实现:

#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    /* 创建临时数组 */
    int L[n1], R[n2];
    /* 复制数据到临时数组 arrays L[] 和 R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    /* 归并临时数组到 arr[l..r]*/
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = l; // 初始归并子数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    /* 复制 L[] 的保留元素 */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    /* 复制 R[] 的保留元素 */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
/* l 为左侧索引,r 为右侧索引 */
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 求中间位置,防止 (l+r) 的和超过 int 类型最大值
        int m = l+(r-l)/2;
        // 递归排序左半部分
        mergeSort(arr, l, m);
        // 递归排序右半部分
        mergeSort(arr, m+1, r);
        // 合并
        merge(arr, l, m, r);
    }
}
相关文章
|
4月前
|
存储 算法 安全
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
126 8
|
4月前
|
存储 监控 算法
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
83 4
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
115 2
|
13天前
|
传感器 并行计算 算法
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
|
4月前
|
存储 监控 算法
内网监控桌面与 PHP 哈希算法:从数据追踪到行为审计的技术解析
本文探讨了内网监控桌面系统的技术需求与数据结构选型,重点分析了哈希算法在企业内网安全管理中的应用。通过PHP语言实现的SHA-256算法,可有效支持软件准入控制、数据传输审计及操作日志存证等功能。文章还介绍了性能优化策略(如分块哈希计算和并行处理)与安全增强措施(如盐值强化和动态更新),并展望了哈希算法在图像处理、网络流量分析等领域的扩展应用。最终强调了构建完整内网安全闭环的重要性,为企业数字资产保护提供技术支撑。
121 2
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
102 4
|
5月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
92 0
|
13天前
|
机器学习/深度学习 算法 新能源
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
|
14天前
|
算法 机器人 定位技术
基于机器视觉和Dijkstra算法的平面建筑群地图路线规划matlab仿真
本程序基于机器视觉与Dijkstra算法,实现平面建筑群地图的路径规划。通过MATLAB 2022A读取地图图像,识别障碍物并进行路径搜索,支持鼠标选择起点与终点,最终显示最优路径及长度,适用于智能导航与机器人路径规划场景。
|
15天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的XGBoost时间序列预测算法matlab仿真
本程序基于Matlab 2024b实现,结合粒子群优化(PSO)与XGBoost算法,用于时间序列预测。通过PSO优化XGBoost超参数,提升预测精度。程序包含完整注释与操作视频,运行后生成预测效果图及性能评估指标RMSE。

热门文章

最新文章

推荐镜像

更多
  • DNS