归并排序(递归和非递归)

ゝ一纸荒年。 2024-03-24 17:10 63阅读 0赞

#### 归并排序 ####

*  一.递归
 *  二.非递归
 *   *  1.基础
     *  2.改进

## 一.递归 ##

> **归并实际上就是把一个数组每次二分，分别排序每个子数组再将有序的子数组进行合并。（归并排序需要一个额外的数组来存放每个子数组，并在排序结束后将其拷贝到原数组）。**

![在这里插入图片描述][c6ed8c7abf1f4112a05545139a5ebe2c.png]

#include<stdio.h>
    #include<string.h>
    #include<time.h>
    #include<stdlib.h>
    
    void _MergeSort(int* a, int begin, int end, int* tmp)
    {
        
    	if (begin >= end)
    		return;
    
    	int mid = (begin+end) / 2;
    	_MergeSort(a, begin, mid,tmp);
    	_MergeSort(a, mid + 1, end,tmp);
    
    	int begin1 = begin, begin2 = mid + 1;
    	int end1 = mid, end2 = end;
    	int i = begin;
    	while (begin1 <= end1 && begin2 <= end2)
    	{
        
    		if (a[begin1] < a[begin2])
    		{
        
    			tmp[i++] = a[begin1++];
    		}
    		else
    		{
        
    			tmp[i++] = a[begin2++];
    		}
    	}
    	while (begin1 <= end1)
    	{
        
    		tmp[i++] = a[begin1++];
    	}
    	while (begin2 <= end2)
    	{
        
    		tmp[i++] = a[begin2++];
    	}
    	memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));
    
    }
    
    void MergeSort(int* a, int n)
    {
        
    	int* tmp = (int*)malloc(sizeof(int) * n);
    	if (tmp == NULL)
    	{
        
    		perror("malloc fail");
    		return;
    	}
    	_MergeSort(a,0,n-1,tmp);
    
    	free(tmp);
    }
    
    int main()
    {
        
    	int a[20000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 20000; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	MergeSort(a,20000);
    	int st = 0;
    	for (int i = 0; i < 19998; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i], a[i + 1], i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    	return 0;
    }

## 二.非递归 ##

### 1.基础 ###

> **归并是不断划分数组，直到每个数组里只有一个元素，那么我们就可以根据这个特性来进行非递归改造。**

> **我们两个小组合并为一个大组进行循环每组里的元素个数为2\*gap，例如我们从gap=1开始（模拟归并最后一层），那么下标为0和下标为1的就为一个大组，将这组里的两个元素归并（排序），赋值到tmp数组里，再将tmp拷贝到数组a里。**

![在这里插入图片描述][1c99ce7ad4ba49c7bb7d7a7d45e9e71d.png]

> **当然这只能对2，4，8…这些特殊2的指数倍个数的数组起作用（不然会发生越界），接下来就是处理边界问题。**

### 2.改进 ###

> **begin1是一大组里前面那个小组的开始位置，end1是该小组的结束位置。同理begin2是一大组里后面那个小组的开始位置，end2是该小组的结束位置。**

![在这里插入图片描述][6ec13c2a1f3841b59d86483b0171e07b.png]

![在这里插入图片描述][105171965e9e4d2088d9fc863221f708.png]

![在这里插入图片描述][0bae9383dd8e426580dd33f445efeedb.png]

#include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    #include<string.h>
    
    void MergeSort(int* a, int n)
    {
        
    	int* tmp = (int*)malloc(sizeof(int) * n);
    	if (tmp == NULL)
    	{
        
    		perror("malloc fail\n");
    		return;
    	}
    
    	int gap = 1;
    	while (gap < n)
    	{
        
    		for (int i = 0; i < n; i += 2 * gap)
    		{
        
    			int begin1 = i, end1 = begin1 + gap-1;
    			int begin2 = i+gap, end2 = begin2 + gap-1;
    			int j = begin1;
    
    			//修正
    			//第一二种情况(ps:因为begin=i，所以不可能越界)
    			if (end1 >= n || begin2 >= n)
    			{
        
    				break;//如果是这种情况就说明第二个小组完全越界，没必要进行归并了，直接跳出
    			}
    			if (end2 >= n)//第三种情况
    			{
        
    				end2 = n - 1;
    				//这说明第二组有一部分没越界，那么我们只需要拷贝这一部分
    			}
    			while (begin1 <= end1 && begin2 <= end2)
    			{
        
    				if (a[begin1] < a[begin2])
    					tmp[j++] = a[begin1++];
    				else
    					tmp[j++] = a[begin2++];
    			}
    			while (begin1 <= end1) tmp[j++] = a[begin1++];
    			while (begin2 <= end2) tmp[j++] = a[begin2++];
    			memcpy(a + i, tmp + i, sizeof(int) *(end2-i+1));//因为如果是第三种情况，那么第二组只能拷贝一部分
    		}
    		gap *= 2;
    	}
    }
    
    
    int main()
    {
        
    	int a[20000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 20000; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	MergeSort(a, 20000);
    	/*for (int i = 0; i < 4; i++)
    		printf("%d ", a[i]);*/
    	int st = 0;
    	for (int i = 0; i < 19998; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i], a[i + 1], i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    	return 0;
    }

[c6ed8c7abf1f4112a05545139a5ebe2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ae67c2fd72424ace88ec5befddcf810b.png
[1c99ce7ad4ba49c7bb7d7a7d45e9e71d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6317b78f24ca42e49b8ba79f3068f195.png
[6ec13c2a1f3841b59d86483b0171e07b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/52f5e0cdc2de4cdfa520b6db33116551.png
[105171965e9e4d2088d9fc863221f708.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/dd854bc127b04ddb9b88144e5fa1ab1d.png
[0bae9383dd8e426580dd33f445efeedb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bac8402c38744170a5e359f437dc8cb2.png