归并排序的递归与非递归实现

2024-06-10 15:52

本文主要是介绍归并排序的递归与非递归实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归实现

归并排序有点类似于二叉树的后序遍历,是一种基于分治思想的排序算法。具体过程如下:

但要注意,在归并时要额外开辟一个与原数组同等大小的空间用来存储每次归并排序后的值,然后再拷贝到原数组中。

代码实现:

#include<stdlib.h>
#include<string.h>// 归并排序递归实现
void _MergeSort(int* a, int* tmp, int left, int right)
{//当区间只有一个值或没有值时,返回if (left >= right){return;}int mid = (left + right) / 2;//递归左右区间_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid + 1, right);//归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//将数据拷贝到原数组中memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}void MergeSort(int* a, int n)
{//开辟与a同等大小的空间int* tmp = (int*)malloc(sizeof(int) * n);//实现归并的函数_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

非递归实现

在实现快排时,我们用栈来实现非递归,但归并排序时,我们用栈来实现似乎有些麻烦。快排在递归到底时,就已经数组排为有序,但层序遍历不行,层序遍历在递归至最底层时才开始排序,如果要用栈来实现,就需要用两个栈来存储,且过程很麻烦。

因此,在这里我们采用循环的方式来实现层序遍历的非递归。先来看具体过程:

根据上图我们可以得到代码:(但这个代码只能实现2的次方倍的数组个数的排序,其它的会出现数组越界的问题)

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{//开辟与a同等大小的空间int* tmp = (int*)malloc(sizeof(int) * n);//归并int gap = 1;//gap为归并的每组数据的个数while (gap < n){//i控制每次归并的起始位置的下标for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//将数据拷贝到原数组中memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap = 2 * gap;}free(tmp);tmp = NULL;
}

要想实现数组归并排序的非递归,我们还要再继续解决数组越界的问题。

先来看越界情况的分析:

代码实现:

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{//开辟与a同等大小的空间int* tmp = (int*)malloc(sizeof(int) * n);//归并int gap = 1;//gap为归并的每组数据的个数while (gap < n){//i控制每次归并的起始位置的下标for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;//结束循环if (begin2 >= n){break;}//修正end2if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//将数据拷贝到原数组中memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap = 2 * gap;}free(tmp);tmp = NULL;
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>void Print(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}// 归并排序递归实现
void _MergeSort(int* a, int* tmp, int left, int right)
{//当区间只有一个值或没有值时,返回if (left >= right){return;}int mid = (left + right) / 2;//递归左右区间_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid + 1, right);//归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//将数据拷贝到原数组中memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}void MergeSort(int* a, int n)
{//开辟与a同等大小的空间int* tmp = (int*)malloc(sizeof(int) * n);//实现归并的函数_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{//开辟与a同等大小的空间int* tmp = (int*)malloc(sizeof(int) * n);//归并int gap = 1;//gap为归并的每组数据的个数while (gap < n){//i控制每次归并的起始位置的下标for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;//结束循环if (begin2 >= n){break;}//修正end2if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//将数据拷贝到原数组中memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap = 2 * gap;}free(tmp);tmp = NULL;
}int main()
{int arr[] = { 6,5,7,9,2,0,3,1,8,4,10 };int len = sizeof(arr) / sizeof(int);MergeSortNonR(arr, len);Print(arr, len);return 0;
}

这篇关于归并排序的递归与非递归实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1048603

相关文章

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》:本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色(红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解

PostgreSQL中MVCC 机制的实现

《PostgreSQL中MVCC机制的实现》本文主要介绍了PostgreSQL中MVCC机制的实现,通过多版本数据存储、快照隔离和事务ID管理实现高并发读写,具有一定的参考价值,感兴趣的可以了解一下... 目录一 MVCC 基本原理python1.1 MVCC 核心概念1.2 与传统锁机制对比二 Postg

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容:获取整页文本与指定区域内容获取页面上的所有文本内容获取

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal