常用排序算法-归并排序

秒速五厘米 2023-10-17 12:57 8阅读 0赞

## 1. 归并排序简介 ##

归并排序是分治法运用的一个有效算法，大致分为两个部分，第一个是将一个无序表不断的二分，对得到的子部分继续二分，直到细分至每一个子部分都只有一个元素；第二个部分便是由最小的子部分开始，逐步向上进行归并，具体来说就是实现两个有序数组的合并。下图引用自百度百科：

![Center][]

可以看出，通过将无序数组不断的细分至只有一个元素，再向上进行有序数组的合并，每次合并得到的有序数组再次进行下一轮合并，最终也就得到了一个完整的有序数组。

## 2. 归并排序基本流程 ##

1. 对数组进行递归二分，向下一直分到每个子数组只有一个元素；

2. 从最小的二分的数组开始进行合并，逐步向上合并至一个完整数组。

## 3. 归并排序实现 ##

template <class T>
    void mySeqList<T>::MergeArray(T seqList[], int first, int mid, int last, T temp[])//就是一个简单的实现两个“有序”数组合并的函数，每次从两个数组中的首个
    {                                                                                 //元素中取一个最小的放到临时数组中，再把这个取出来的再原数组中删除(当
    	int i = first;                                                            //然说是删除，其实就是不管了~），然后继续比较最后合并成一个数组
    	int j = last;
    	int m = mid;
    	int n = mid+1;
    	int k = 0;
    
    	while (i<=m&&n<=last)
    	{
    		if (seqList[i]<seqList[n])
    		{
    			temp[k++] = seqList[i++];
    		}
    		else
    		{
    			temp[k++] = seqList[n++];
    		}
    	}
    	while (i<=m)//当其中一个数组的元素已经全部放入临时数组中后，把另一个数组的元素依次放入即可，下同
    	{
    		temp[k++] = seqList[i++];
    	}
    	while (n<=last)
    	{
    		temp[k++] = seqList[n++];
    	}
    	for (int i=0; i<k; ++i)//把临时数组的元素重新赋给目标数组，注意目标数组的起始序号
    	{
    		seqList[first+i] = temp[i];
    	}
    
    	return;
    }
    
    template <class T>//对数组进行向下递归二分
    void mySeqList<T>::MergeSort(T seqList[], int first, int last, T temp[])
    {
    	if (first<last)//最小的条件是还能分到一个数组含一个元素
    	{
    		int mid = (first+last)/2;
    		MergeSort(seqList, first, mid, temp);//对分到的左半数组进行细分
    		MergeSort(seqList, mid+1, last, temp);//对分到的右半数组进行细分
    		MergeArray(seqList, first, mid, last, temp);//对细分的数组进行合并，是从下向上的合并，也就是从最小的逐步合成最大的
    	}
    
    	return;
    }

## 4. 应该注意的问题 ##

1. 代码不熟悉、不理解就默写，默写几遍就好了，以后学不懂的算法就强行默写好了~；

2. 归并排序和快速排序有些相似，但是一个是向上逐次合并成一个有序数组，后者则是向下分阵营的时候，分到最下面就合并成功了，应该多思考一下两者的相似、不同以及具体思想。

[Center]: https://img-blog.csdn.net/20170507230447069?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveWhhbl9zaGVu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center