当前位置: 首页 > ops >正文

归并排序递归法和非递归法的简单简单介绍

基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有 序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序核心步骤:先将数组分组,往下分直到分为1个数据,然后开始合并,两两合并,合并的时候先比较两组数据中的数据的大小,按顺序依次合并到临时数组temp中,然后再将合并到temp数组中有序的数据覆盖到原数组中。

#include <stdio.h>
// 归并排序
// 时间复杂度O(N*logN)
// 空间复杂度O(N)
void _MergeSort(int* arr, int left, int right, int* temp)
{if (left >= right)return;// 递归划分区间,直到区间内只有一个数据后开始归并int mid = (left + right) / 2;// [left,mid] [mid+1,right]_MergeSort(arr, left, mid, temp);_MergeSort(arr, mid+1, right, temp);// 归并[left,mid] [mid+1,right]有序,归并到temp了int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段没结束,具体那一段不知道,只有一个循环可以进入while(begin1<=end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 将归并后在temp的数据拷贝回原数组for (int i = left;i <= right; i++){arr[i] = temp[i];}
}// 归并排序
void MergeSort(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);// 传入闭区间【0,n-1】_MergeSort(arr, 0, n - 1, temp);free(temp);
}void TestMergeSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}void TestMergeSortNonR()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSortNonR(arr,sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{//TestInsertSort();//TestShellSort();//TestSelectSort();//TestBubbleSort();//TestHeapSort();//TestQuickSort();TestMergeSort();TestMergeSortNonR();return 0;
}

函数的递归实现图:

非递归法

从上面的递归图可以看出,合并的时候是2个数据开始合并,也就是区间【0,0】和【1,1】合并,【2,2】和【3,3】合并;然后【0,1】和【2,3】合并到这里时是两个数据两个数据之间合并,依次类推。那么非递归方法,需要控制好合并的下标即可。

// 归并排序--非递归方法
void MergeArry(int* arr, int begin1, int end1, int begin2, int end2, int* temp)
{int left = begin1, right = end2;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段没结束,具体那一段不知道while (begin1 <= end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 将归并后在temp的数据拷贝回原数组for (int i = left;i <= right; i++){arr[i] = temp[i];}
}void MergeSortNonR(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);int gap = 1;  // 控制几个数据的合并排序while (gap < n){for (int i = 0;i < n;i += 2 * gap){// 归并+排序的区间(数组长度不是2的次方数时第二组可能会越界访问)// [i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i, end1 = i + gap - 1;    // 第一组int begin2 = i + gap, end2 = i + 2 * gap - 1;  // 第二组// 1、合并时只有第一组if (begin2 >= n)break;// 2、合并时第二组只有部分数据,需要修正边界if (end2 >= n)end2 = n - 1; // 只有一个数值的时候,直接让end2=最后一个数值就行了MergeArry(arr, begin1, end1, begin2, end2, temp);}Printarry(arr, n);gap *= 2;}free(temp);
}

实现图:

结论:

归并排序是一种基于分治思想的有效排序算法,其核心是通过递归将数组不断二分直至单个元素,然后按顺序合并有序子序列。算法分为递归和非递归两种实现方式:递归法通过_MergeSort函数划分区间并调用自身,然后将有序子序列合并到临时数组后回写;非递归法使用MergeSortNonR函数,通过gap变量控制合并步长,逐步扩大有序区间。两种方法都使用MergeArry函数进行具体合并操作,时间复杂度均为O(N*logN),空间复杂度为O(N)。代码示例展示了完整的实现过程,包括边界处理和数据拷贝等关键步骤。

http://www.xdnf.cn/news/15299.html

相关文章:

  • 运放压摆率?正弦波怎么输出了三角波?
  • 数据结构 单链表(2)--单链表的实现
  • 打破并发瓶颈:虚拟线程实现详解与传统线程模型的性能对比
  • 二叉树算法详解和C++代码示例
  • C++封装、多态、继承
  • RFCOMM协议详解:串口仿真与TCP/IP协议栈移植技术——面试高频考点与真题解析
  • 在Intel Mac的PyCharm中设置‘add bin folder to the path‘的解决方案
  • 【Scratch】从入门到放弃(六):指令大全-扩展类
  • iOS高级开发工程师面试——关于优化
  • 在AI应用中Prompt撰写重要却难掌握,‘理解模型与行业知识是关键’:提升迫在眉睫
  • 关于数据库的慢查询
  • C/C++数据结构之多维数组
  • MyBatis04-MyBatis小技巧
  • QT 多线程 管理串口
  • Node.js特训专栏-实战进阶:16. RBAC权限模型设计
  • 沃尔玛 卡号查询 滑块 分析
  • 深度学习图像分类数据集—角膜溃疡识别分类
  • TensorFlow深度学习实战(24)——变分自编码器详解与实现
  • spring-ai-alibaba 1.0.0.2 学习(十六)——多模态
  • IP 地址与网络基础全面解析
  • ARC 02 runner scale set chart:对接集群与 Github Action 服务器
  • 在 OCI 生成式 AI 上搭一个「指定地区拉面店 MCP Server」——从 0 到 1 实战记录
  • 基于SpringBoot3集成Kafka集群
  • CSS个人笔记分享【仅供学习交流】
  • Utils系列之内存池(MultiSizePool)
  • 电商系统未来三年趋势:体验升级、技术赋能与模式重构
  • 关于ISO 26262的Single-Point Fault/Residual Fault/Latent Fault/Dual-Point Fault的整理
  • Android 响应式编程完整指南:StateFlow、SharedFlow、LiveData 详解
  • Docker 基于 Cgroups 实现资源限制详解【实战+源码】
  • CAU数据挖掘第四章 分类问题