归并排序C/C++代码实现

￡神魔★判官ぃ 2023-02-24 07:58 65阅读 0赞

## 举例： ##

归井排序(MergingSort)就是将两个或两个以上的**有序表**合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归井

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

## 算法属性： ##

时间复杂度为O(nlog2(n))。  
空间复杂度为O(n)  
稳定排序。  
归并多用于外部排序。

## 代码如下： ##

#include<stdio.h>
    
    #define MAXSIZE 20
    typedef int KeyType;
    typedef int InfoType;
    //记录类型
    typedef struct {
        
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    //顺序表类型
    typedef struct {
        
    	RedType r[MAXSIZE + 1];  //r[0]闲置或作哨兵
    	int length;	  			 //顺序表长度
    }SqList;
    
    
    //归并排序
    
    //相邻的两个有序子序列归并
    void Merge(RedType R[], RedType T[], int low, int mid, int high)
    {
        
    	//将有序R[low...mid]和R[mid+1...high]归并为有序表T[low...high]
    	int i = low, j = mid + 1, k = low;			//分别指向三个数组的第一个记录
    	while (i <= mid && j <= high)
    	{
        
    		if (R[i].key <= R[j].key)				// 把小的记录存进T[]
    		{
        
    			T[k] = R[i];
    			i++;
    		}
    		else
    		{
        
    			T[k] = R[j];
    			j++;
    		}
    		k++;
    	}
    
    	//把剩余的复制到T[]中
    	while (i <= mid)
    	{
        
    
    		T[k] = R[i];
    		i++;
    		k++;
    	}
    	while (j <= high)
    	{
        
    		T[k] = R[j];
    		j++;
    		k++;
    	}
    }
    
    //R[low...high]归并排序后放入T[low...high]中
    //第一次调用时R[]为L.r[],T[]也为L.r[]， 递归时R[]为L.r[],T[]为S[]
    void MSort(RedType R[], RedType T[], int low, int high)
    {
        
    	int mid;
    	RedType S[MAXSIZE];					//创建一个空数组用来存放结果
    	if (low == high)
    	{
        
    		T[low] = R[low];
    	}
    	else
    	{
        
    		mid = (low + high) / 2;
    		MSort(R, S, low, mid);			//把结果放入S[low...mid]中
    		MSort(R, S, mid + 1, high);		//把结果放入S[mid+1...high]中
    		Merge(S, T, low, mid, high);
    	}
    }
    //L.r[low...high]归并排序后覆盖到L.r[low...high]中
    void MergeSort(SqList &L)
    {
        
    	MSort(L.r, L.r, 1, L.length);
    }
    
    
    //打印排序结果
    void println(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		printf("%d, ", L.r[i].key);
    	}
    	printf("\n");
    }
    
    
    int main()
    {
        
    	SqList L;
    	L.r[1].key = 49;
    	L.r[2].key = 38;
    	L.r[3].key = 65;
    	L.r[4].key = 97;
    	L.r[5].key = 76;
    	L.r[6].key = 13;
    	L.r[7].key = 27;
    	L.r[8].key = 49;
    	L.length = 8;
    
    	MergeSort(L);
    	println(L);
    }

## 运行结果： ##

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

[20200708154952326.png]: /images/20230209/6d9a5bdb3eab479abd428c8eecae04df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: /images/20230209/279775b141584fd88525dab9b7d7f445.png