113-对二路归并排序算法的实现和分析

Myth丶恋晨 2022-12-30 03:46 158阅读 0赞

## 二路归并排序算法 ##

将相邻的两个段(本身已经是有序的)的数据合并到一块，合并完成后整个段依旧有序  
初始时，认为单个数据就是有序的一个段

首先书写需要用到的辅助函数

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]

l1:第一个段的第一个元素下标  
h1:第一个段的最后一个元素下标  
l2:第二个段的第一个元素下标  
h2:第二个段的最后一个元素下标

**实现二路归并算法**

void Meger(int *arr,int len,int section_size,int *brr)
    {
        
    	int l1=0;
    	int h1=l1+section_size-1;
    	int l2=h1+1;
    	int h2=l2+section_size<len?l2+section_size-1:len-1;
    	
    	int brr_index=0;
    	
    	//有两个归并段
    	while(l2<len)
    	{
        
    		//两个归并段中都有数据时
    		while(l1<=h1&&l2<=h2)
    		{
        
    			if(arr[l1]<arr[l2])
    			{
        
    				brr[brr_index++]=arr[l1++];
    			}
    			else
    			{
        
    				brr[brr_index++]=arr[l2++];
    		    } 
    		}
    		//剩下一个归并段有数据
    		while(l1<=h1)
    		{
        
    			brr[brr_index++]=arr[l1++];
    		}
    		while(l2<=h2)
    		{
        
    			brr[brr_index++]=arr[l2++];
    		}
    		l1=h2+1;
    		h1=l1+section_size-1;
    		l2=h1+1;
    		h2=l2+section_size<len?l2+section_size-1:len-1;
    	}
    	//仅剩下一个归并段
    	while(l1<len)
    	{
        
    		brr[brr_index++]=arr[l1++];
    	}
    	//将brr的数据全部导入到arr中
    	for(int i=0;i<len;++i)
    	{
        
    		arr[i]=brr[i];
    	} 
    }
    	  
    void MegerSort(int *arr,int len)
    {
        
    	int *brr=(int *)malloc(sizeof(arr[0])*len);
    	assert(brr!=NULL);
    	for(int i=1;i<len;i*=2)
    	{
        
    		Meger(arr,len,i,brr);
    	}
    	free(brr);
    }

**最后完成主函数**

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	MegerSort(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

**运行结果**  
![在这里插入图片描述][20201223223823525.png_pic_center]  
**二路归并算法分析**  
时间复杂度 O(nlogn)  
空间复杂度 O(n)  
稳定性： 稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a929ead4dbd94b4d924fce59fdba75f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/f3c14a1ca47d44219a7cedbd75f2afc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/5150f1a408ae49d39380c8875eb47637.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/0d9e7d3b939b4b868633fd47a38b9371.png
[20201223223823525.png_pic_center]: /images/20221120/9eb4e58b04f84f478e36e7f851d7f29b.png