复习数据结构：排序算法（四）——归并排序

一时失言乱红尘 2022-08-07 01:53 169阅读 0赞

基本思想：基于分治法，即把待排序的数组序列，分为若干个子序列，对每个子序列排序，然后再把所有有序的子序列合并为一个整体有序的序列。分析可知，如果拿任何一个元素作为子序列，那么所有子序列就已经是有序的，而归并排序的关键就在于如何合并，也就是“归并”。

归并排序是外排序，稳定排序，时间复杂度是O(nlogn).

![Center][]

详细说归并排序的过程：1个元素的表总是有序的。所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

代码如下：

非递归实现：（经过调试，该程序有bug，后续修正！）

#include<iostream>
    using namespace std; 
    
    void Merge(int* r, int* rf, int i, int m, int n)
    {
    	int j, k; 
    	for(j = m+1, k = i; i <= m && j <= n; k++)  // i记录第一个子序列标记，j记录第二个子序列标记，k记录合并后序列标记
    	{
    		if(r[j] < r[i])  //  存入较小者
    			rf[k] = r[j++]; 
    		else
    			rf[k] = r[i++]; 
    	}
    	while(i <= m)  // 如果不等长，就会出现这种情况
    		rf[k++] = r[i++]; 
    	while(j <= n)
    		rf[k++] = r[j++]; 
    
    	for(int ii = 0; ii < n+1; ii++)
    		cout<<rf[ii]<<' '; 
    	cout<<endl; 
    }
    
    void MergeSort(int* r, int* rf, int length)
    {
    	int len = 1; 
    	int* q = r; 
    	//int* tmp; 
    	while(len < length)
    	{
    		int s = len; 
    		len = 2*s; // 等长的两个子序列,长度相同
    		int i = 0; 
    		bool flag = true; 
    		while(i + len <= length)  // 等长的两个子序列合并
    		{
    			cout<<"等长"<<i<<'-'<<i+s-1<<'-'<<i+len-1<<endl; 
    			Merge(q, rf, i, i+s-1, i+len-1);  // 注意起始位置的标记
    			i += len;  // 下一次合并的起始
    			flag = false; 
    		}
    		if(i + s <= length)  // 不等长两个子序列合并
    		{
    			cout<<"不等长"<<i<<'-'<<i+s-1<<'-'<< length-1<<endl; 
    			Merge(q, rf, i, i+s-1, length-1);  // 注意最后的结束标记位置
    		}
    		
    		cout<<"flag="<<flag<<endl; 
    		if(!flag)
    			swap(q, rf);  // 交换指针，该次合并的结果作为下次合并的起始
    	}
    }
    
    int main()
    {
    	int a[10] = {11,1,5,7,2,4,9,6,10};  // ,9,6,10,8
    	int b[10]; 
    	MergeSort(a, b, 9); 
    
    	for(int i = 0; i< 9; i++)
    		cout<<b[i]<<' '; 
    	cout<<endl; 
    
    	return 0; 
    
    }

递归实现：

void MSort(ElemType *r, ElemType *rf,int s, int t)  
    {   
        ElemType *rf2;  
        if(s==t) r[s] = rf[s];  
        else  
        {   
            int m=(s+t)/2;          /*平分*p 表*/  
            MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
            MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
            Merge(rf2, rf, s, m,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
        }  
    }  
    void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
    {   /*对顺序表*p 作归并排序*/  
        MSort(r, rf,0, n-1);  
    }

参考：

http://blog.csdn.net/xiazdong/article/details/8462393

http://blog.csdn.net/hguisu/article/details/7776068

http://blog.csdn.net/jetjetlinuxsystem/article/details/6589093

[Center]: /images/20220805/0a0bab48e1ee4df0a9e1914a5bec8414.png