归并排序的思想与实现（递归与迭代）

怼烎@ 2022-12-06 15:55 187阅读 0赞

## 归并排序的思想 ##

核心思想：归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

如图：对于有序的两个数组我们可以很容易的进行有序合并，那么我们基于分治的思想， 我们将无序的数组进行分割， 直到分成一个元素，重新进行合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center]

1.  稳定性  
    　归并排序是一种稳定的排序。
2.  存储结构要求  
    　可用顺序存储结构。也易于在链表上实现。
3.  时间复杂度  
    　对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
4.  空间复杂度  
    　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

## 实现 ##

**递归实现**

void mergearray(int a[],int first,int mid,int last,int temp[])	//将两个有序数组合并排序 
    {
        
    	int i=first,j=mid+1;
    	int m=mid,n=last;
    	int k=0;
    	while(i<=m&&j<=n)
    	{
        
    		if(a[i]<a[j])
    			temp[k++]=a[i++];
    		else
    			temp[k++]=a[j++];
    	}
    	while(i<=m)
    		temp[k++]=a[i++];
    	while(j<=n)
    		temp[k++]=a[j++];
    	for(i=0;i<k;i++)
    		a[first+i]=temp[i];
    }
     
    void mergesort(int a[],int first,int last,int temp[])	//将两个任意数组合并排序 
    {
        
    	if(first<last)
    	{
        
    		int mid=(first+last)/2;
    		mergesort(a,first,mid,temp);	//左边有序 
    		mergesort(a,mid+1,last,temp);	//右边有序 
    		mergearray(a,first,mid,last,temp);	//再将两个有序数组合并 
    	}
    }

**迭代实现**

// 区间[head1, head2-1]和[head2, tail2]都是排好序的，现在需要合并
    void mergeSortHelper(vector<int>& v, int head1, int head2, int tail2) {
        
        int tail1 = head2 - 1, index = 0, len = tail2 - head1 + 1, start = head1;
        vector<int> tmp(len);
        while (head1 <= tail1 || head2 <= tail2) {
        
            if (head1 > tail1)
                tmp[index++] = v[head2++];
            else if (head2 > tail2)
                tmp[index++] = v[head1++];
            else {
        
                if (v[head1] <= v[head2])
                    tmp[index++] = v[head1++];
                else
                    tmp[index++] = v[head2++];
            }
        }
        
        for (int i = 0; i < len; ++i)
            v[start+i] = tmp[i];
    }
     
    void mergeSort(vector<int>& v) {
        
        int len = v.size();
        // 倍进枚举步长1,2,4,……
        for (int step = 1; step <= len; step <<= 1) {
        
            int offset = step + step;
            for (int index = 0; index < len; index += offset)
                mergeSortHelper(v, index, min(index+step, len-1), min(index+offset-1, len-1));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f2c0d764a3f34eda801e9ead9352636c.png