C语言归并排序算法
用归并排序法对一组数据由小到大进行排序,数据分别为 695、458、362、789、12、 15、163、23、2、986。
(2) 自定义函数 merge_sort(),实现归并排序。
(3) 程序代码如下:
(1) 将 n 个记录看成是 n 个长度为 1 的有序子表。
(2) 将两两相邻时有序无表进行归并。
(3) 重复执行步骤 (2) 直到归并成一个长度为 n 的有序表。
实现过程:
(1) 自定义函数 merge(),实现一次归并排序。(2) 自定义函数 merge_sort(),实现归并排序。
(3) 程序代码如下:
#include <stdio.h> int merge(int r[],int s[],int x1,int x2,int x3) //自定义实现一次归并样序的函数 { int i,j,k; i=x1; //第一部分的开始位置 j=x2+1; //第二部分的开始位置 k=x1; while((i<=x2)&&(j<=x3)) //当i和j都在两个要合并的部分中时 if(r[i]<=r[j]) //筛选两部分中较小的元素放到数组s中 { s[k] = r[i]; i++; k++; } else { s[k]=r[j]; j++; k++; } while(i<=x2) //将x1〜x2范围内未比较的数顺次加到数组r中 s[k++]=r[i++]; while(j<=x3) //将x2+l〜x3范围内未比较的数顺次加到数组r中 s[k++]=r[j++]; return 0; } int merge_sort(int r[],int s[],int m,int n) { int p; int t[20]; if(m==n) s[m]=r[m]; else { p=(m+n)/2; merge_sort(r,t,m,p); //递归调用merge_soit()函数将r[m]〜r[p]归并成有序的t[m]〜t[p] merge_sort(r,t,p+1,n); //递归一调用merge_sort()函数将r[p+l]〜r[n]归并成有序的t[p+l]〜t[n] merge(t,s,m,p,n); //调用函数将前两部分归并到s[m]〜s[n】*/ } return 0; } int main() { int a[11]; int i; printf("请输入10个数:\n"); for(i=1;i<=10;i++) scanf("%d",&a[i]); //从键盘中输入10个数 merge_sort(a,a,1,10); //调用merge_sort()函数进行归并排序 printf("排序后的顺序是:\n"); for(i=1;i<=10;i++) printf("%5d",a[i]); //输出排序后的数据 printf("\n"); return 0; }
运行结果:
请输入10个数:
695 458 362 789 12 15 163 23 2 986
排序后的顺序是:
2 12 15 23 163 362 458 695 789 986
技术要点:
归并是将两个或多个存序记录序列合并成一个有序序列。归并方法有多种,一次对两个有序记录序列进行归并,称为路归并排序,也有三路归并排序及多路归并排序。本实例是二路归并排序,基本方法如下:(1) 将 n 个记录看成是 n 个长度为 1 的有序子表。
(2) 将两两相邻时有序无表进行归并。
(3) 重复执行步骤 (2) 直到归并成一个长度为 n 的有序表。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频