文章目录

前言

一、什么是归并排序？

二、涉及到的函数及功能

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 
3、定义动态数组 
由于实践要求，要定义长度为10^6的数组，int是定义不了这么长的数组的，这里我们就用到了malloc（）函数。
 
int *tmp = (int *) malloc(sizeof(int) * n);//定义一个长度为n的整型数组

free(tmp);//释放malloc（）函数使用过的内存空间
 
 4、有关Linux多线程的函数 
#include//使用多线程需要引入pthread.h头文件

    pthread_t thread;//先进行线程声明，声明一个名为thread的线程

    pthread_create(&thread,NULL,Merge_Sort,arg);//创建线程

    pthread_join(thread,NULL);//线程等待，等待线程运行
    
    pthread_exit(0);//线程结束，结束线程
 
关于多线程本人了解并不深入，可以参考其他博主关于多线程的详细讲解。 
 
三、串行与并行（多线程）归并排序的代码实现 
1、实现串行归并排序 
#include
#include
#include//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 
2、实现并行（多线程）归并排序 
 值得注意的是这里用到的多线程归并排序只能在Linux系统下运行
 
#include
#include
#include
#include


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 
 

 总结 
以上就是关于归并排序的内容，本文仅仅简单介绍了归并排序，本人对归并排序的理解也有很多的不足之处，若有什么不足欢迎大家留言指正。（完结撒花）