数据结构--迭代归并

怼烎@ 2022-07-30 14:30 215阅读 0赞

归并最初的使用在与两个有序表的合并，从而引出对待排序数列的排序。两个有序表的合并在于合并之后，合并的表仍然有序。比如：

有序表(1)：1 3 4 4 6

有序表(2)：2 3 3 5 8

最后归并的的有序表为：1 2 3 3 4 4 5 6 8

当然，实现两个有序表的实现是比较简单容易的，为了不仅仅实现两张有序表的归并，而是为了用于之后归并排序的使用，这里用一个数组存储两张有序表，从0到m-1代表的是有序表1的范围，从m到n-1是有序表2的范围，对于上面的例子来说，m的值为5，n的值为10。

实现的方式如下：

template<class T>
    void Merge(T * initList,T *mergedList,const int left,const int m,const int right)
    {
        int nMergeInd,nInitIndex_1,nInitIndex_2;
        for(nMergeInd=left,nInitIndex_1=left,nInitIndex_2=m;nInitIndex_1<m && nInitIndex_2<right;nMergeInd++)
        {
            if(initList[nInitIndex_1]<=initList[nInitIndex_2])
            {
                mergedList[nMergeInd]=initList[nInitIndex_1];
                nInitIndex_1++;
            }
            else
            {
                mergedList[nMergeInd]=initList[nInitIndex_2];
                nInitIndex_2++;
            }
        }
        copy(initList+nInitIndex_1,initList+m,mergedList+nMergeInd);
        copy(initList+nInitIndex_2,initList+right,mergedList+nMergeInd);
    
    }

说明：

*   从\[left:m-1\]范围是待合并序列1，从\[m:right-1\]是待合并序列2的范围
 *  left代表的是待排序序列的左边界，right代表的是待排序序列的右边界。实际上，right与left的差值是待排序序列的总长度。
 *  最后两句copy的原因是由于存在待合并序列1已经和待合并序列2比较完成，待合并序列1或者2已经全部合并至mergeList中，但是待合并序列1或者2没有遍历完，仍然存在部分元素没有合并至mergeList，但是可以肯定的是剩下的元素一定不小于已经能合并到mergeList的元素，因此只需要将剩下的元素复制到mergeList的尾后即可。
 *  注意copy的用法是，第一个参数代表需要复制序列元素的第一个元素的地址，第二个参数代表需要复制序列元素的最后一个元素的地址的下一个地址。第三个元素时复制到的目标序列的起始位置。

实现两张有序表的归并后，现在就需要结合到对于一个无序的序列的排序了。从之前的插入排序的想法，插入排序最开始的切入点是讲一个元素插入到有序的数列中，最后得到的序列仍然有序，在应用到排序算法时，是通过对序列a\[0:n-1\]不断进行插入操作，即a\[n\]插入到a\[0:n-1\]序列中，n的范围是1到n-1，最后得到的序列是有序的。那么在这里，同样可以采取这样的方法。

首先对待排序表进行分组，第一次排序时时两两归并，最后得到的每个分组包含两个元素，每组元素时有序的。然后再对新的分组再进行归并，得到一个分组是包含四个元素的，这四个元素同样是有序的，迭代这个过程，直到把所有的元素归并完成排序。

实现一次迭代的过程示意图：

![20160419131156859][]

实现代码：

template<class T>
    void MergeSortForOnce(T *sort_list, T *resulstList, const int nNum, const int groupScale)
    {
    	//首先这里实现的是迭代递归
    	//首先做到的是对待筛选序列实现两两分组
    
    	int nIndex;
    	for (nIndex = 0; nIndex<nNum - 2 * groupScale; nIndex += 2 * groupScale)
    	{
    		Merge(sort_list, resulstList, nIndex, nIndex + groupScale, nIndex + 2 * groupScale);
    	}
    
    	if (nIndex + groupScale - 1<nNum)
    		Merge(sort_list, resulstList, nIndex, nIndex + groupScale, nNum);
    	else
    		copy(sort_list + nIndex, sort_list + nNum, resulstList + nIndex);
    }

最终实现迭代排序：

/**
    	Index:|-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|-8-|
    	value:  1   5   6   4   8   9   11  10  8
    	第一次：groupScale=1;
    	合并后：调用Merge  --->    Index:|-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|-8-|
    	                          value:  1   5   4   6   8   9   10  11  8
    	第二次：groupScale=2;
    	合并后：调用Merge  --->    Index:|-0--1-|-2--3-|-4--5-|-6--7-|-8-|
    							  value:  1  4   5  6   8  9   10 11  8
    	*/
    
    template<class T>
    void MergeSort(T *sort_list, int nNum)
    {
    	int scale;
    	T *tempList;
    	tempList = new T[nNum];
    	for (scale = 1; scale<nNum; scale *= 2)
    	{
    		MergeSortForOnce(sort_list, tempList, nNum, scale);
    		scale *= 2;
    		MergeSortForOnce(tempList, sort_list, nNum, scale);
    
    	}
    	delete tempList;
    }

说明：

*  scale控制的是每个归并排序前，两个待归并的有序表的大小，对于一个长度为n的待排序序列，需要进行的迭代次数应该是\[log2n\];
 *   在for循环中，可能就出现scale可能出现大于n/2的情况，但是这并不影响排序，因为在MergeSortForOnce函数中，当nNum-2\*groupScale<0，此时就应该会直 接判断if语句，在函数MergeSortForOnce中，判断if语句，或者与已经排好的序列和剩余的元素进行归并，或者进行复制，但是最后sort\_list一定是有序的。
 *   终点在于理解MergeSort中的for语句以及MergeSortForOnce函数中的if和else语句。

最后贴出完整的实现：

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    template<class T>
    void Merge(T * initList, T *mergedList, const int left, const int m, const int right)
    {
    	int nMergeInd, nInitIndex_1, nInitIndex_2;
    	for (nMergeInd = left, nInitIndex_1 = left, nInitIndex_2 = m; nInitIndex_1<m && nInitIndex_2<right; nMergeInd++)
    	{
    		if (initList[nInitIndex_1] <= initList[nInitIndex_2])
    		{
    			mergedList[nMergeInd] = initList[nInitIndex_1];
    			nInitIndex_1++;
    		}
    		else
    		{
    			mergedList[nMergeInd] = initList[nInitIndex_2];
    			nInitIndex_2++;
    		}
    	}
    	copy(initList + nInitIndex_1, initList + m, mergedList + nMergeInd);
    	copy(initList + nInitIndex_2, initList + right, mergedList + nMergeInd);
    
    }
    template<class T>
    void MergeSortForOnce(T *sort_list, T *resulstList, const int nNum, const int groupScale)
    {
    	//首先这里实现的是迭代递归
    	//首先做到的是对待筛选序列实现两两分组
    
    	int nIndex;
    	for (nIndex = 0; nIndex<nNum - 2 * groupScale; nIndex += 2 * groupScale)
    	{
    		Merge(sort_list, resulstList, nIndex, nIndex + groupScale, nIndex + 2 * groupScale);
    	}
    
    	if (nIndex + groupScale - 1<nNum)
    		Merge(sort_list, resulstList, nIndex, nIndex + groupScale, nNum);
    	else
    		copy(sort_list + nIndex, sort_list + nNum, resulstList + nIndex);
    }
    
    	/**
    	Index:|-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|-8-|
    	value:  1   5   6   4   8   9   11  10  8
    	第一次：groupScale=1;
    	合并后：调用Merge  --->    Index:|-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|-8-|
    	                          value:  1   5   4   6   8   9   10  11  8
    	第二次：groupScale=2;
    	合并后：调用Merge  --->    Index:|-0--1-|-2--3-|-4--5-|-6--7-|-8-|
    							  value:  1  4   5  6   8  9   10 11  8
    	*/
    
    template<class T>
    void MergeSort(T *sort_list, int nNum)
    {
    	int scale;
    	T *tempList;
    	tempList = new T[nNum];
    	for (scale = 1; scale<nNum; scale *= 2)
    	{
    		MergeSortForOnce(sort_list, tempList, nNum, scale);
    		scale *= 2;
    		MergeSortForOnce(tempList, sort_list, nNum, scale);
    
    	}
    	delete tempList;
    }
    int main()
    {
    	srand(unsigned(time(NULL)));
    	int nNum = rand() % 50;
    	int *initList;
    	initList = new int[nNum];
    
    	for (int i = 0; i<nNum; i++)
    	{
    		initList[i] = rand() % 20;
    	}
    
    	for (int i = 0; i<nNum; i++)
    	{
    		cout << initList[i] << " ";
    	}
    	cout << endl;
    
    	MergeSort(initList, nNum);
    	for (int i = 0; i<nNum; i++)
    	{
    		cout << initList[i] << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

PS:这里可能会包关于C4996的一个错误，导致编译无法进行下去，这个时候需要在项目（Project）--->属性（Propertities)--->C/C++--->Preprocessor（预处理器）--->Preprocessor Definition（预处理器定义）---Edit中，添加\_SCL\_SECURE\_NO\_WARNINGS这个就可以了。

![20160419133111120][]

[20160419131156859]: /images/20220724/02c32ad2b480465ebc282fff7d2d3535.png
[20160419133111120]: /images/20220724/b82c87c651804a7daa3fdb377016e977.png