IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 归并排序算法(merge sort) -> 正文阅读

[数据结构与算法]归并排序算法(merge sort)

前言:

归并排序算法,是10大经典排序算法之一,后续会更新其他的算法,本博客的全部代码以及图片实例都来里于b站,排序算法:归并排序【图解+代码】_哔哩哔哩_bilibili,但是本人已经理解了代码的所有内容,下面是我根据up主的视频自己的思考过程。我也看了其他人的代码,但是感觉这个up主的代码更能锻炼我最近所学的东西,由于时间复杂度和空间复杂度还没有深入接触,本文暂时先不写,后续会更新。

目录

? ? ? ? ?1:全部代码

2:归并排序的思想

3:递归算法的基本思路与关键

4:图解(详细去看上面b站的链接)

5:代码分析


1:全部代码

#include<stdio.h>
#include<stdlib.h>
void my_printf(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
//合并
void merge(int arr[], int tempArr[], int mid, int left, int right) {
	//标记左区域第一个未排序的元素
	int l_pos = left;
	//标记右区域第一个未排序的元素
	int r_pos = mid + 1;
	//辅助数组元素下标,只需从最左面开始即可
	int pos = left;
	//合并
	while (l_pos <= mid && r_pos <= right) {
		if (arr[l_pos] < arr[r_pos])
			tempArr[pos++] = arr[l_pos++];
		else
			tempArr[pos++] = arr[r_pos++];
	}

	//合并左区域剩余元素
	while (l_pos <= mid) {
		tempArr[pos++] = arr[l_pos++];
	}
	//合并右区域剩余元素
	while (r_pos <= right) {
		tempArr[pos++] = arr[r_pos++];
	}
	//将辅助数组中合并后的元素覆盖给原数组中
	/*while (left <= right) {
		arr[left] = tempArr[left];
		left++;
	}*/
	for (int i = 0; i <= right; i++) {
		arr[i] = tempArr[i];
	}
}
//归并排序之递归拆分
void msort( int arr[], int tempArr[],  int left, int right) {
	if (left < right) {

		int mid = left + (right - left) / 2;
		//将左区域递归拆分
		msort(arr, tempArr, left, mid);
		//将右区域递归拆分
		msort(arr, tempArr, mid + 1, right);
		//将左右合并
		merge(arr, tempArr, mid, left, right);
	}
}


//归并排序的入口
void merge_sort(int arr[], int n) {
	//构造辅助数组
	int* tempArr = (int*)malloc(n * sizeof(int));
	if (tempArr) {
		int left = 0, right = n - 1;
		msort(arr, tempArr,  left,right);
		//释放辅助数组
		free(tempArr);
	}
	else {
		printf("error,failed to creat a space!!!");
	}

}
int main() {
	int arr[] = { 9,5,2,7,12,4,3,1,11 };
	int n = 9;
	my_printf(arr, n);
	merge_sort(arr, n);
	my_printf(arr, n);
	return 0;
}

2:归并排序的思想

归并排序运用了,分治和递归的思想,通常来说,能分治一定能递归,但是能递归不一定能分治,但是这种说法并不准确,分治是一种算法,递归是具体的代码实现,所以像这样说会更好,分治算法一般用递归实现

这个博客里面讲的很好(37条消息) 分治算法详解_K神丶的专栏-CSDN博客

递归和分治都具有这样的特征:将一个大问题分解成若干个规模较小的相同问题

能否用分治的关键是,子问题的解是否可以合并成原问题的解

3:递归算法的基本思路与关键

1:需要一个新数组来存放已经排好的原数组里面的元素,这个数组可以用malloc函数开辟,新数组是在合并的时候才发挥作用

2:划分的时候需要折半递归,在这步中的关键是折半时候边界的问题

3:合并是这个算法的关键,在合并的过程中,需要比较左半区域和右半区域每个元素的大小,将较小的元素放入新数组中,但是总会有一个元素被剩下来(这个在代码分析中说),将剩下的元素放进新数组里。

4:图解(详细去看上面b站的链接)

?

5:代码分析

int main() {
	int arr[] = { 9,5,2,7,12,4,3,1,11 };
	int n = 9;
	my_printf(arr, n);
	merge_sort(arr, n);
	my_printf(arr, n);
	return 0;
}

这个是,打印数组元素的函数,都能看懂,这样写是因为可以少写一次打印函数的代码

void my_printf(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

下面就是主函数里面的第二个函数,这个函数的作用是开辟一个和原数组相同大小的空间,在msort函数调用结束后,释放掉用malloc函数开辟的空间(使用malloc函数要引用#include<stdlib.h>这个头文件或者其他的头文件)if语句的作用是判断开辟空间是否成功

在给msort函数传参的时候要将原数组,新数组,左下标,右下标,都传进去,(新数组要在合并过程中才能被用到),因为在接下来的折半递归中会用到下标

//归并排序的入口
void merge_sort(int arr[], int n) {
	//构造辅助数组
	int* tempArr = (int*)malloc(n * sizeof(int));
	if (tempArr) {
		int left = 0, right = n - 1;
		msort(arr, tempArr,  left,right);
		//释放辅助数组
		free(tempArr);
	}
	else {
		printf("error,failed to creat a space!!!");
	}

}

?这个就是折半递归函数的具体实现过程,用递归来实现,而递归最重要的就是结束条件,而结束条件就是left>=right

大于的时候,这个数组不存在

left=right时候,左下标和右下标指向同一个元素,证明数组里就一个元素,所以不能用这个函数

而left<right,代表这数组里面至少有两个元素,可以进行折半查找

在第一次折半递归的时候,左下标是left=0,右下标是right=n-1;

第二次的时候,左边区域的左下标是left=0,右下标是right=mid;(mid(中间元素下标)是向下取整的得到的,这个元素归左区域,所以右下标是mid)右边区域左下标是left=mid+1,右下标是right

......以此类推直到不满足递归条件

函数merge是对已经拆分好的元素进行重新排序,我们需要把原数组和新数组,还有左右下标以及中间下标传进去,因为左右区域的第一个元素的下标需要用left,mid表示,而右下标代表着循环停止的条件(看下一个函数)

//归并排序之递归拆分
void msort( int arr[], int tempArr[],  int left, int right) {
	if (left < right) {

		int mid = left + (right - left) / 2;
		//将左区域递归拆分
		msort(arr, tempArr, left, mid);
		//将右区域递归拆分
		msort(arr, tempArr, mid + 1, right);
		//将左右合并
		merge(arr, tempArr, mid, left, right);
	}
}

?合并是归并排序算法的核心,而合并的关键在于,左区域和右区域的元素那个先放在新数组里

首先我们需要左区域第一个未排序元素的下标,右区域第一个未排序元素的下标,以及新数组第一个元素的下标

这些都定义好后,我们需要将左右区域的元素按照一定的顺序放到新数组里面,因此要判断谁先放进去,而每放一个新元素新数组的下标就要+1,而左右区域拿走元素的那个区域的下标也要+1,因此会出现循环体里面的代码。将上述的内容用代码实现放进一个while循环里面,而循环继续的条件是左区域或者右区域都要有元素,因为两边要比较嘛,所以在左右区域最总会剩下一个元素在原来的数组里,假设剩下的是右边的最后一个元素,此时他的下标是right,因为上一个右区域的元素放进新数组里后数组下标++了,将第一个while循环里面右边的条件构成一个新的条件,组成一个while循环,并将剩余的元素放进新数组里面。

注意后面的两个while只能有一个能够执行

最后就是将已经在新数组里面排好序的元素放进原先的数组里面

//合并
void merge(int arr[], int tempArr[], int mid, int left, int right) {
	//标记左区域第一个未排序的元素
	int l_pos = left;
	//标记右区域第一个未排序的元素
	int r_pos = mid + 1;
	//辅助数组元素下标,只需从最左面开始即可
	int pos = left;
	//合并
	while (l_pos <= mid && r_pos <= right) {
		if (arr[l_pos] < arr[r_pos])
			tempArr[pos++] = arr[l_pos++];
		else
			tempArr[pos++] = arr[r_pos++];
	}

	//合并左区域剩余元素
	while (l_pos <= mid) {
		tempArr[pos++] = arr[l_pos++];
	}
	//合并右区域剩余元素
	while (r_pos <= right) {
		tempArr[pos++] = arr[r_pos++];
	}
	//将辅助数组中合并后的元素覆盖给原数组中
	/*while (left <= right) {
		arr[left] = tempArr[left];
		left++;
	}*/
	for (int i = 0; i <= right; i++) {
		arr[i] = tempArr[i];
	}
}

这就是归并排序算法的具体实现过程

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-24 11:44:57  更:2021-07-24 11:47:02 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 13:10:44-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码