文章目录
前言
一、什么是归并排序？
二、涉及到的函数及功能
1、计算程序运行时间
2、生成随机数
3、定义动态数组
4、有关Linux多线程的函数
三、串行与并行（多线程）归并排序的代码实现
1、实现串行归并排序
2、实现并行（多线程）归并排序
总结
前言
本文主要记录了C语言归并排序串、并行的两种实现方式，是本人历经为时俩天半的心得体会（手动滑稽），希望可以给未来完成程序实践课的学弟学妹提供一些帮助。
一、什么是归并排序？
先谈谈本人对于递归排序的认识吧，本人所认为的递归排序就是将一个无序的数组无限平分，直到最后一次平分后的数组内只剩一个元素，此时我们就可以认为这时的数组是有序的。把数组无限分割直至数组内剩一个元素的步骤就是递归中的递，这时我们就需要比较数组前后两部元素的大小进行排序合并，这个步骤是合并数组，然后再通过递归的函数将排好序的数组归还到原数组，进而输出，实现归并排序。
二、涉及到的函数及功能
由于这次程序实践要求程序实现的功能较多，所以先来介绍一下其中主要的函数和功能
1、计算程序运行时间
这里使用的是头文件time.h中的time函数，代码示例如下：
time_t begin_time,end_time;begin_time=time(NULL);##################执行程序主体##################end_time=time(NULL);printf("%lfs", difftime(end_time,begin_time));
2、生成随机数
srand((unsigned )time(NULL));//使用srand()函数使产生的随机数与时间关联，避免出现伪随机数的情况for(int i=0;i<n;i++){arr[i]=1+rand()%(10000);//使用rand（）生成随机数}for (int i = 0; i < n; i++){printf("%d\t",arr[i]);//两个for循环实现循环生成数组并输出}
3、定义动态数组
由于实践要求，要定义长度为10^6的数组，int是定义不了这么长的数组的，这里我们就用到了malloc（）函数。
int *tmp = (int *) malloc(sizeof(int) * n);//定义一个长度为n的整型数组free(tmp);//释放malloc（）函数使用过的内存空间
4、有关Linux多线程的函数
#include<pthread.h>//使用多线程需要引入pthread.h头文件pthread_t thread;//先进行线程声明，声明一个名为thread的线程pthread_create(&thread,NULL,Merge_Sort,arg);//创建线程pthread_join(thread,NULL);//线程等待，等待线程运行pthread_exit(0);//线程结束，结束线程
关于多线程本人了解并不深入，可以参考其他博主关于多线程的详细讲解。
三、串行与并行（多线程）归并排序的代码实现
1、实现串行归并排序
#include<stdio.h>#include<time.h>#include<stdlib.h>//malloc（）函数的头文件，也可以单独使用malloc.h头文件void Merge_Sort(int arr[],int start,int end);//声明递归函数void Merge(int arr[],int start,int mid,int end);//声明合并函数void Input_print();//声明一个分担主函数功能的函数，避免主函数过于冗长int n;int main(){time_t begin_time,end_time;begin_time=time(NULL);Input_print();end_time=time(NULL);printf("%lfs", difftime(end_time,begin_time));//输出程序运行时间，并输出单位return 0;}void Input_print(){int* arr=(int*) malloc(20000000*sizeof(int ));printf("Please enter the length of the array:\n");scanf("%d",&n);printf("Randomly generate random %d numbers in the array:\n",n);srand((unsigned )time(NULL));for(int i=0;i<n;i++){arr[i]=1+rand()%(1000000);}for (int i = 0; i < n; i++){printf("%d\t",arr[i]);}printf("\n");Merge_Sort(arr,0,n-1);for(int i=0;i<n;i++)//循环输出排序后数组中的元素printf("%4d\n",arr[i]);printf("\n");free(arr);}void Merge_Sort(int arr[],int start,int end){if(end-start!=0)//设定执行条件避免无限循环{int mid=(start+end)/2;printf("start:%d,end:%d\n",start,end);//这里是一项实践任务，完成对平分后数组角标的输出Merge_Sort(arr,start,mid);Merge_Sort(arr,mid+1,end);Merge(arr,start,mid,end);}elseprintf("start:%d,end:%d\n",start,end);//这里是一项实践任务，完成对平分后数组角标的输出}void Merge(int arr[],int start,int mid,int end) {int *tmp = (int *) malloc(sizeof(int) * n);//定义一个临时数组int i, j, k;i = start;j = mid + 1;k = start;while (i <= mid && j <= end)//while循环进行数组合并，把同一级的数组中的元素轮流进行比较，哪个小，哪个就放入数组tmp[]{if (arr[i] < arr[j]){tmp[k] = arr[i];i++;k++;} else {tmp[k] = arr[j];k++;j++;}}while (i <= mid) {//把剩余的数挨个放到数组中去tmp[k] = arr[i];k++;i++;}while (j <= end) {//把剩余的数挨个放到数组中去tmp[k] = arr[j];k++;j++;}for (int m = start; m <= end; m++)//for循环将数组tmp赋值到arr中arr[m] = tmp[m];free(tmp);}
2、实现并行（多线程）归并排序
值得注意的是这里用到的多线程归并排序只能在Linux系统下运行
#include<stdio.h>#include<time.h>#include<stdlib.h>#include<pthread.h>void Merge(int arr[],int start,int mid,int end);void Input_print();void* Merge_Sort(void* arg);//注意线程函数的命名格式void Merge_sort(int start,int end);int n;int *x;//定义一个指针int main(){time_t begin_time,end_time;begin_time=time(NULL);Input_print();end_time=time(NULL);printf("%lfs", difftime(end_time,begin_time));return 0;}void Input_print(){int arr[100000];printf("Please enter the length of the array:\n");scanf("%d",&n);printf("Randomly generate random %d numbers in the array:\n",n);srand((unsigned )time(NULL));for(int i=0;i<n;i++){arr[i]=1+rand()%(10000);}for (int i = 0; i < n; i++){printf("%d\t",arr[i]);}printf("\n");x = arr;//指针指向arrint arg[2];arg[0] = 0;arg[1] = n;pthread_t thread;//声明一个主线程pthread_create(&thread,NULL,Merge_Sort,arg);//创建线程pthread_join(thread,NULL);//线程等待Merge_sort(0,n-1);printf("The sorted arry is:\n" );for(int i=1;i<=n;i++)printf("%4d\n",arr[i]);pthread_exit(0);//线程结束}/*void Merge_sort(int start,int end){if(end-start!=0){int mid=(start+end)/2;printf("start:%d,end:%d\n",start,end);Merge_sort(start,mid);Merge_sort(mid+1,end);}elseprintf("start:%d,end:%d\n",start,end);}*///本块代码是专门实现输出平分时数组前后元素角标的，不需要请省略void* Merge_Sort(void* arg){int *argu = (int*)arg;//强制转化arg类型为整型，并把值赋给argueint start = argu[0];int end = argu[1];if(start<end){int *arr = x;//定义一个指针，把x赋值给arrpthread_t thread1;pthread_t thread2;//声明两个线程int arg1[2];int arg2[2];int mid = (start + end) / 2;arg1[0] = start;arg1[1] = mid;arg2[0] = mid + 1;arg2[1] = end;pthread_create(&thread1,NULL,Merge_Sort,arg1);pthread_create(&thread2,NULL,Merge_Sort,arg2);//创建线程pthread_join(thread1,NULL);pthread_join(thread2,NULL);//线程等待Merge(arr,start,mid,end);pthread_exit(0);//线程结束}return NULL;}void Merge(int arr[],int start,int mid,int end){int *tmp = (int *) malloc(sizeof(int) * n);int i, j, k;i = start;j = mid + 1;k = start;while (i <= mid && j <= end) {if (arr[i] < arr[j]) {tmp[k] = arr[i];i++;k++;} else {tmp[k] = arr[j];k++;j++;}}while (i <= mid) {tmp[k] = arr[i];k++;i++;}while (j <= end) {tmp[k] = arr[j];k++;j++;}for (int m = start; m <= end; m++)arr[m] = tmp[m];free(tmp);}
总结
以上就是关于归并排序的内容，本文仅仅简单介绍了归并排序，本人对归并排序的理解也有很多的不足之处，若有什么不足欢迎大家留言指正。（完结撒花）
