C语言数据结构——归并排序

太过爱你忘了你带给我的痛 2023-10-06 18:02 15阅读 0赞

定义排序算法的数据元素的数据结构如下：

typedef struct
    {
        
    	KeyType key;
    }DataType;

## 归并排序主要是二路归并排序 ##

> 基本思想是：  
> 可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，  
> 首先做两两归并，得到 n / 2 个长度为 2 的有序子序列 ；  
> 再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]

### 一次二路归并排序算法如下： ###

void Merge(DataType a[], int n, DataType swap[], int k)
    //k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中
    {
        
    	int m = 0, u1,l2,i,j,u2;
    	int l1 = 0;				//第一个有序子数组下界为0
    	while( l1+k <= n-1 )
    	{
        
    		l2 = l1 + k;			//计算第二个有序子数组下界
    		u1 = l2 - 1;			//计算第一个有序子数组上界
    		u2 = (l2+k-1 <= n-1)? l2+k-1: n-1;       //计算第二个有序子数组上界
    		//两个有序子数组合并
    		for(i = l1, j = l2; i <= u1 && j <= u2; m++)	
    		{
        
    			if(a[i].key <= a[j].key)
    			{
        
    				swap[m] = a[i];
    				i++;
    			}
    			else
    			{
        
    				swap[m]=a[j];
    				j++;
    			}
    		}
    		    //子数组2已归并完，将子数组1中剩余的元素存放到数组swap中
    		while(i <= u1)
    		{
        
    			swap[m] = a[i];
    			m++;
    			i++;
    		}
    		while(j <= u2)
    		{
        
    			swap[m] = a[j];
    			m++;
    			j++;
    		}
    		l1=u2+1;
    	}//将原始数组中只够一组的数据元素顺序存放到数组swap中
    	for(i=l1;i<n;i++,m++)
    		swap[m]=a[i];
    }
    
    Void MergeSort(DataType a[ ], int n)
    {
        
    	int i, k=1;
    	DataType *swap;
    	swap=(DataType*i) malloc(sizeof(DataType)*n)
    	while(k<n)
    	{
        
    		Merge(a,n,swap,k);
    		for(i=0;i<n;i++)
    		{
        
    			a[i]=swap[i];
    		}
    		k=2*k;
    	}
    	free(swap);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210622151328674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70