[数据结构与算法]C语言归并排序算法

今天我要和大家分享的是一个排序算法——归并算法。

如果说快速排序是让一个数组分成很多小集体进行排序，那么归并排序就是让很多有序的小集体合成一个有序数组。

思路：

如果是升序，对于每一个数字来说其本身是有序的，最初让两个只有一个元素的数组arr1,arr2的元素进行比较，较小者放入第三个数组arr3的第一个元素的位置，然后另一个数组的元素放在arr3。然后让两个有一个以上的合并后数组的首元素进行比较较小者让在第三个数组首元素的位置，再向下进行比较，直到两个数组的元素全部进入第三个数组，然后一直重复，直到合并成最终的大数组。

要想利用小集合合成大数组前提是有小集合，所以先让数组分成许多小数组。

void merge_sort_divide(int* arr, int* temp, int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		merge_sort_divide(arr, temp, start, mid);
		merge_sort_divide(arr, temp, mid + 1, end);
		merge(arr, temp, start, mid + 1, end);
	}
}

最后合并

void merge(int* arr, int* temp, int arr1start, int arr2start, int arr2end)
{
	int p1 = arr1start, p2 = arr2start, p3 = p1, arr1end = p2 - 1;

	//主循环
	while (p1 <= arr1end && p2 <= arr2end)
	{
		if (arr[p1] < arr[p2]) temp[p3++] = arr[p1++];
		else temp[p3++] = arr[p2++];
	}

	//一个数组排序完成后，剩下的移动过去即可
	while (p1 <= arr1end) temp[p3++] = arr[p1++];
	while (p2 <= arr2end) temp[p3++] = arr[p2++];

	//将所有数据移回原来数组
	for (int i = arr1start; i <= arr2end; i++) arr[i] = temp[i];
}

全部代码

test.c：

#include"sort.h"

int main(void)
{
	int arr[LEN] = { 0 };
	int i = 0;
	srand((unsigned int)time(NULL));
    
    //生成随机数进行检验  也可以自己输入数据
	for (i = 0; i < LEN; i++)
	{
		arr[i] = rand() % 100;
	}
	printf("数组排序前:\n");
	print_arrray(arr, LEN);

	merge_sort(arr, LEN);

	printf("数组排序后:\n");
	print_arrray(arr, LEN);

	return 0;
}

sort.h：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>

#define LEN 10//随机数的个数

void print_arrray(int* arr, int len);


void merge_sort(int* arr, int len);

void merge_sort_divide(int* arr, int* temp, int start, int end);

void merge(int* arr, int* temp, int arr1star, int arr2start, int arr2end);

sort_function.c：

#include"sort.h"

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


//将两个有序数组合并为一个
void merge(int* arr, int* temp, int arr1start, int arr2start, int arr2end)
{
	int p1 = arr1start, p2 = arr2start, p3 = p1, arr1end = p2 - 1;

	//主循环
	while (p1 <= arr1end && p2 <= arr2end)
	{
		if (arr[p1] < arr[p2]) temp[p3++] = arr[p1++];
		else temp[p3++] = arr[p2++];
	}

	//一个数组排序完成后，剩下的移动过去即可
	while (p1 <= arr1end) temp[p3++] = arr[p1++];
	while (p2 <= arr2end) temp[p3++] = arr[p2++];

	//将所有数据移回原来数组
	for (int i = arr1start; i <= arr2end; i++) arr[i] = temp[i];
}

void merge_sort_divide(int* arr, int* temp, int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		merge_sort_divide(arr, temp, start, mid);
		merge_sort_divide(arr, temp, mid + 1, end);
		merge(arr, temp, start, mid + 1, end);
	}//分成许多小的数组最后执行合并
}


void merge_sort(int* arr, int len)
{
	int* temp = malloc(sizeof(int) * len);
	merge_sort_divide(arr, temp, 0, len - 1);
	free(temp);
}

运行结果：

?

牛客网 初学者编程118题小乐乐与序列_牛客题霸_牛客网

?我的初代思路：极其听话地先去重再排序。

初代代码：

#include<stdio.h>
 
int main(void)
{
    int arr[60] = { 0 };
    int n = 0;
    int i = 0;
    int j = 0;
    int k = 0;
    int count = 0;
    int flag = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    for (i = 0; i < n - count; i++)
    {
        for (k = i + 1; k < n - count; k++)
        {
            flag = 0;
            for (j = k; j < n - count; j++)
            {
                if(arr[j] == arr[i])
                {
                    flag = 1;
                    count++;
                    k = j - 1;
                    break;
                }
            }
            for (j; j < n - count; j++)
            {
                arr[j] = arr[j + 1];
            }
        }
    }
     
    //for (i = 0; i < n - count; i++)
    //{
        //printf("%d ", arr[i]);
    //}
    int p = 0;
    int min = 0;
    for (i = 0; i < n - count; i++)
    {
        p = i;
        min = arr[i];
        for (j = i + 1; j < n - count; j++)
        {
            if(arr[j] < min)
            {
                p = j;
                min = arr[j];
            }
        }
        if(p != i)
        {
            int t = arr[i];
            arr[i] = arr[p];
            arr[p] = t;
        }
    }
     
    for (i = 0; i < n - count; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

?数据太少了

然后改进：

改成了5000个数据

然后出现了这个

?

这是n的值

我就只能在堆上要这么多数据，并且学习了一个算法——快速排序，结果超时了，超过一秒程序直接暂停。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
void W(int* p, int left, int right)//先去重
{
    int flag = 0;
    flag = *(p + left);
    int t = right;
    //int ret = right - left;
    while (left < right)
    {
        if (*(p + right) < flag)
        {
            *(p + left) = *(p + right);
            left++;
            while (left < right)
            {
                if (*(p + left) > flag)
                {
                    *(p + right) = *(p + left);
                    right--;
                    break;
                }
                else
                {
                    left++;
                }
            }
        }
        else
        {
            right--;
        }
    }
     
    *(p + left) = flag;
 
    if (left > 1)
    {
        W(p, 0, left - 1);
    }
    if (right < t - 1)
    {
        W(p, right + 1, t);
    }
}
 
int main(void)
{
    //int arr[10000] = { 0 };
    //int* p = (int*)calloc(80000, sizeof(int));
    int* p = (int*)malloc(80000*sizeof(int));
    if (p != NULL)
    {
        int n = 0;
        int i = 0;
        int j = 0;
        int k = 0;
        int count = 0;
        int flag = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", p + i);
        }
        for (i = 0; i < n - count - 1; i++)
        {
            for (k = i + 1; k < n - count; k++)
            {
                flag = 0;
                for (j = k; j < n - count; j++)
                {
                    if (*(p + j) == *(p + i))
                    {
                        flag = 1;
                        count++;
                        k = j - 1;
                        break;
                    }
                }
                for (j; j < n - count; j++)
                {
                    *(p + j) = *(p + j + 1);
                }
            }
        }
 
        //for (i = 0; i < n - count; i++)
        //{
            //printf("%d ", arr[i]);
        //}
         
        W(p, 0, n - 1);
         
        for (i = 0; i < n - count; i++)
        {
            printf("%d ", *(p + i));
        }
        printf("\n");
    }
    free(p);
    p = NULL;
    return 0;
}

改进顺序，先排序后去重，在去重的同时打印：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
void W(int* p, int left, int right)
{
    int flag = 0;
    flag = *(p + left);
    int t = right;
    while (left < right)
    {
        if (*(p + right) < flag)
        {
            *(p + left) = *(p + right);
            left++;
            while (left < right)
            {
                if (*(p + left) > flag)
                {
                    *(p + right) = *(p + left);
                    right--;
                    break;
                }
                else
                {
                    left++;
                }
            }
        }
        else
        {
            right--;
        }
    }
     
    *(p + left) = flag;
 
    if (left > 1)
    {
        W(p, 0, left - 1);
    }
    if (right < t - 1)
    {
        W(p, right + 1, t);
    }
}
 
int main(void)
{
    int* p = (int*)malloc(72641*sizeof(int));
    //int* q = (int*)malloc(70000*sizeof(int));
    if (p != NULL)
    {
        int n = 0;
        int i = 0;
        int k = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", p + i);
        }
        W(p, 0, n - 1);
         
        for (i = 0; i < n - 1; i++)
        {
            if(*(p + i) != *(p + i + 1))
            {
                printf("%d ", *(p + i));
            }
        }
        printf("%d ", *(p + n - 1));
    }
    free(p);
    p = NULL;
    return 0;
}

?还是超时

然后用归并排序解决问题：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
//将两个有序数组合并为一个
void merge(int* arr, int* temp, int arr1start, int arr2start, int arr2end)
{
    int p1 = arr1start, p2 = arr2start, p3 = p1, arr1end = p2 - 1;
 
    //主循环
    while (p1 <= arr1end && p2 <= arr2end)
    {
        if (arr[p1] < arr[p2]) temp[p3++] = arr[p1++];
        else temp[p3++] = arr[p2++];
    }
 
    //一个数组排序完成后，剩下的移动过去即可
    while (p1 <= arr1end) temp[p3++] = arr[p1++];
    while (p2 <= arr2end) temp[p3++] = arr[p2++];
 
    //将所有数据移回原来数组
    for (int i = arr1start; i <= arr2end; i++) arr[i] = temp[i];
}
 
void merge_sort_divide(int* arr, int* temp, int start, int end)
{
    if (start < end)
    {
        int mid = (start + end) / 2;
        merge_sort_divide(arr, temp, start, mid);
        merge_sort_divide(arr, temp, mid + 1, end);
        merge(arr, temp, start, mid + 1, end);
    }
}
 
 
void merge_sort(int* arr, int len)
{
    int* temp = malloc(sizeof(int) * len);
    merge_sort_divide(arr, temp, 0, len - 1);
    free(temp);
}
int main(void)
{
    int* p = (int*)malloc(100000*sizeof(int));
    if (p != NULL)
    {
        int n = 0;
        int i = 0;
        int a = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", p + i);
        }
        merge_sort(p, n);
         
        for (i = 0; i < n - 1; i++)
        {
            if(*(p + i) != *(p + i + 1))
            {
                printf("%d ", *(p + i));
            }
        }
        printf("%d ", *(p + n - 1));
    }
    free(p);
    p = NULL;
    return 0;
}

最后说明一下为什么我从堆上要了10万个数，因为它真的用了

?经历了22次试错，因为自测都能通过，真正测试的10组中最后4组都是大数

?难题就要慢慢解决，写出来真的很有成就感，虽然那些大佬一眼就看出来了，但是我一个小鸟做出来感觉已经不错了，我会一直努力的。

?

?

?好吧，这几天没有太努力，让这张图片激励一下我吧！