C语言递归实现归并排序详解
归并排序递归实现还是比较难理解的，感觉涉及递归一般理解起来都会比较有难度吧，但是看了b站视频，然后照着打下来，然后自己写了点注释，就发现不知不觉都大概懂了。
这里的归并讲的是升序排序
归并排序思路大概就是：先划分数组，将数组划分为左右半区，分成的左右半区，各自再划分左右半区，一直划分，直到最后左右半区的元素都为一个时，开始合并，因为都划分为一个元素了，那么此时两个元素的排序就非常简单了，只需要比较大小就可以排序了，那么回溯上去会发现每组都是两两有序了，那么直接再依次比较两组之间的排头元素即可，取较小的赋值给临时数组，然后排头元素就变成后一个元素，一直这么比较，直到两组数据有一组为空时，只需要将另一组不为空的接在临时数组后面即可，因为此时不为空的剩下的元素是有序的且都比此时有序的临时数组大，接完之后临时数组就变成有序的数组了，那么再将临时数组的元素复制到实际数组中去，最后释放临时数组空间，输出实际数组，归并排序结束，输出的元素也是排好序的元素了。
这样干讲一定很抽象
这是b站视频里的图，十分生动形象了吧。
代码如下（除了视频里的注释，还加了点自己的注释）
#include<bits/stdc++.h>
using namespace std;
void print_arr(int arr[], int n){
for(int i=0; i<n; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
//合并
void merge(int arr[], int tempArr[], int left, int mid, 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++];//赋值后pos+1，l_pos+1为下一次做准备
else //右半区第一个剩余元素更小
tempArr[pos++] = arr[r_pos++];
}
//当右半区元素合并完后左半区还有元素剩余，此时右半区有序且都比左半区元素大
//那么直接将剩余的右半区元素接上即可
//合并左半区剩余的元素
while(l_pos <= mid)tempArr[pos++] = arr[l_pos++];
//同理
//合并右半区剩余的元素
while(r_pos <= right)tempArr[pos++] = arr[r_pos++];
//把临时数组中合并后的元素复制回原来的数组
//tempArr此时已有序，只需利用left,right即排完序后的左右半区复制回arr数组即可
while(left <= right){
arr[left] = tempArr[left];
left++;
}
}
//归并排序
void msort(int arr[], int tempArr[], int left, int right){
//如果只有一个元素，那么就不需要继续划分
//由 mid = (left + right) / 2得，当只剩最后一个数时 mid会和left和right相等
//即传入后的left和right会相等
if(left < right){ //left和right不相等，不止一个元素，需要继续划分
//找中间点
int mid = (left + right) / 2;
//递归划分左半区
msort(arr, tempArr, left, mid);
//递归划分右半区
msort(arr, tempArr, mid+1, right);
//当数组划分完毕时开始进行合并
//合并已经排序的部分
//left为左半区左边界
//right为右半区右边界
//mid为划分左右半区的分界（也是左半区的右边界）
merge(arr, tempArr, left, mid, right);
}
}
//归并入口
void merge_sort(int arr[], int n){
//分配一个辅助的数组，内存大小为 数组数*数据类型占位
int* tempArr = (int*)malloc(n * sizeof(int));
if(tempArr){
//tempArr为临时数组, arr为需要排序的数组
//排序下标为0至n-1，n为数组大小
msort(arr, tempArr, 0, n-1);
free(tempArr);//释放内存空间
}
else{
printf("meet error");
}
}
int main(){
int arr[] = {9, 5, 2, 7, 12, 4, 3, 1, 11};
int n = 9;
//打印原来的数组
print_arr(arr, n);
//归并排序
merge_sort(arr, n);
//打印排完序的数组
print_arr(arr, n);
return 0;
}
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容!
相关推荐
-
C语言分治法实现归并排序
本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表. 排序过程如图: 代码如下: #include "stdio.h" #define MAX 100 int is1[MAX],is2[MAX];//原数组is1,临时空间数组is2 void merge(int low,int mid,int
-
一篇文章带你了解C语言函数递归
目录 什么是递归? 递归的两个必要条件 递归实例 实例1(按照顺序打印一个数的整形值) 画图讲解 完整代码 实例2 (使用函数在不创建变量的情况下求字符串长度) 画图讲解 程序运行结果 完整代码 递归与迭代 实例1 (求n的阶乘) 方法一(使用递归) 方法二(使用迭代) 实例2 (求解斐波那契数列) 方法一 (递归求解) 方法二(迭代求解) 总结 什么是递归? 递归(recursion):程序调用自身的一种编程技巧. 如何理解函数递归: 1.从调用自身层面:函数递归就是函数自己调用自己. 2.从
-
C语言开发之归并排序详解及实例
C语言归并排序 即将两个都升序(或降序)排列的数据序列合并成一个仍按原序排列的序列. 上代码: #include <stdio.h> #include <stdlib.h> #define m 6 #define n 4 int main() { int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22}; int i,j,k,c[m+n]; int l ; i=j=k=0; printf("a数组的元素:\n"); for
-
C语言的递归函数详解
目录 函数递归 什么是递归? 递归的俩个必要条件 代码引例1 栈溢出(Stack Overflow) 合理使用递归 代码引例3 代码引例4 解释要合理使用递归 总结 函数递归 程序调用自身的编程技巧称为递归 recursion) 函数自己调用自己就是递归 你也可以理解成是一种嵌套结构,但递归分为俩部分,第一是“递”,进入嵌套结构.第二是”归“,最终会一步一步返回.第一次接触递归都会很懵,慢慢理解这个过程就明白了. 什么是递归? 递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或
-
C语言中递归和排列组合详解
目录 排列组合三大问题: 1.打印n个数的全排列 2.打印n个数中任意m个数的全排列 3.打印n个数中任意m个数的组合 完整代码如下: 总结 排列组合三大问题: 1.打印n个数的全排列2.打印n个数中任意m个数的全排列3.打印n个数中任意m个数的组合 1.打印n个数的全排列 这个题实际上是可以直接用STL中的next_permutation()函数,代码如下: #include<bits/stdc++.h> using namespace std; int main(){ int data[4
-
C语言 实现归并排序算法
C语言 实现归并排序算法 归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾
-
C语言递归实现归并排序详解
归并排序递归实现还是比较难理解的,感觉涉及递归一般理解起来都会比较有难度吧,但是看了b站视频,然后照着打下来,然后自己写了点注释,就发现不知不觉都大概懂了. 这里的归并讲的是升序排序 归并排序思路大概就是:先划分数组,将数组划分为左右半区,分成的左右半区,各自再划分左右半区,一直划分,直到最后左右半区的元素都为一个时,开始合并,因为都划分为一个元素了,那么此时两个元素的排序就非常简单了,只需要比较大小就可以排序了,那么回溯上去会发现每组都是两两有序了,那么直接再依次比较两组之间的排头元素即可,取
-
基于Java语言的递归运算例题详解
目录 一.实例演示:递归求N的阶乘 二. 递归调用练习 递归求1+2+3+……10的和 顺序打印一个数字的每一位 返回一个数组成本身的数字之和 求解汉诺塔问题 求斐波那契数列第N项 递归定义:一个方法在执行过程中调用自身, 就称为 "递归". 递归的必要条件: 1. 将原问题划分成其子问题,注意:子问题必须要与原问题的解法相同. 2. 递归出口. 一.实例演示:递归求N的阶乘 public class fac { public static int factorial(int x){
-
java 算法之归并排序详解及实现代码
java 算法之归并排序详解 一.思想 归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来: 二.概念 归并:将两个有序的数组归并成一个更大的有序数组: 三.特点 优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比: 缺点:需要额外的空间和N成正比: 四.实现方法 将两个不同的有序数组归并到第三个数组中: 先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间: 五.代码 /** * 归并排序 * * @author
-
C语言数据结构 快速排序实例详解
C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart
-
C语言之快速排序案例详解
快速排序:是对冒泡排序算法的一种改进. 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 例如有一个数字序列: 5 0 1 6 8 2 3 4 9 7 对其进行快速排序变为:0 1 2 3 4 5 6 7 8 9 思路如下:首先将要排序的序列的首个数字5定位比较数,这是一个参考对象! 然后的方法很简单:分别从序列的两端进行比较.先
-
C语言数据结构之二叉树详解
目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵
-
C语言二叉树的概念结构详解
目录 1.树的概念及结构(了解) 1.1树的概念: 1.2树的表示法: 2.二叉树的概念及结构 2.1二叉树的概念 2.2特殊的二叉树 2.2二叉树的性质 2.3二叉树的顺序存储 2.4二叉树的链式存储 3.二叉树链式结构的实现 3.1二叉树的前中后序遍历 3.2求二叉树的节点个数 3.3求二叉树的叶子节点个数 3.4销毁二叉树 1.树的概念及结构(了解) 1.1树的概念: 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树
-
基于JS脚本语言的基础语法详解
JS脚本语言的基础语法:输出语法 alert("警告!"); confirm("确定吗?"); prompt("请输入密码");为弱类型语言: 开始时要嵌入JS代码:<script type="text/javascript"></script>: 关于写程序是需注意的基本语法: 1.所有的字符全都是英文半角的: 2.大部分情况下每条语句结束后要加分号: 3.每一块代码结束后加换行:4.程序前呼
-
Linux 下C语言连接mysql实例详解
Linux 下C语言连接mysql实例详解 第一步: 安装mysql, 参考:http://www.jb51.net/article/39190.htm 第二步: 安装mysql.h函数库 sudo apt-get install libmysqlclient-dev 执行之后就可以看到/usr/include/MySQL目录了 然后开始我们的链接. 首先看我的数据库 mysql> show databases; +--------------------+ | Database | +----