[补充]归并排序(非递归)以及归并排序的更高效算法——自然归并排序

递归版归并排序

---

 

　　我们在 CLRS 中已经学会了归并排序的递归写法：

#include<iostream>
using namespace std;
const int SIZE = 100;
int arr[SIZE];
//排序数组arr[fir:end]
void mergeSort(int fir,int end){
//当子序列就只有一个元素的时候就弹出
if(fir==end)return;

//分治
int mid = (fir+end)/2;
    mergeSort(fir,mid);
    mergeSort(mid+1,end);

//合并
int tempArr[SIZE];
int fir1=fir,fir2=mid+1;
for(int i=fir;i<=end;i++){
if(fir1>mid)
            tempArr[i]=arr[fir2++];
else if(fir2>end)
            tempArr[i]=arr[fir1++];
else if(arr[fir1]>arr[fir2])
            tempArr[i]=arr[fir2++];
else 
            tempArr[i]=arr[fir1++];
    }
for(int i=fir;i<=end;i++)
        arr[i]=tempArr[i];

}
int main(){
//测试
int n;cin>>n;
for(int i=0;i<n;i++)cin>>arr[i];
    mergeSort(0,n-1);
for(int i=0;i<n;i++)cout<<arr[i]<<" ";
    cout<<endl;
return 0;
}

　　merge 函数如下：

void merge(int fir,int end,int mid){
//合并
int tempArr[SIZE];
int fir1=fir,fir2=mid+1;
for(int i=fir;i<=end;i++){
if(fir1>mid)//前半段扫描完毕
            tempArr[i]=arr[fir2++];
else if(fir2>end)//后半段扫描完毕
            tempArr[i]=arr[fir1++];
//两端如果都没有扫描完毕的话
//就选择较小的值插在临时数组的后端
else if(arr[fir1]>arr[fir2])
            tempArr[i]=arr[fir2++];
else 
            tempArr[i]=arr[fir1++];
    }
//将排好的临时数组拷贝到原数组中，返回
for(int i=fir;i<=end;i++)
        arr[i]=tempArr[i];
}

　　mergeSort 函数如下：

void mergeSort(int fir,int end){
//当子序列就只有一个元素的时候就弹出
if(fir==end)return;

//分治，现分为两个子段，
int mid = (fir+end)/2;
    mergeSort(fir,mid);//对左半段递归排序
    mergeSort(mid+1,end);//对右半段递归排序

//合并
    merge();

}

 

　　但是，递归的常数因素通常都会考虑，转化成非递归版算法通常都是更优的解法，所以我们来实现一下非递归版

 

非递归版归并排序

---

 

　　实现的原理和递归版刚好相反，递归解法是将有序串一分为二直到每个串只有一个元素，然后再排序合并。而非递归版是默认有 n 个长度为 1 子串，然后将相邻的两个串两两排序并合并，直到合并成一个长度为 n 的子串。比如刚开始有 n 个子串，下一步是相邻的两个串两两排序并合并，构成 n/2 个长度为 2 的子串，然后再排序合并，形成 n/4 个长度为 4 的子串....直到生成一个长度为 n 的子串。

void mergeSort2(int n){
int s=2,i;
while(s<=n){
        i=0;
while(i+s<=n){
            merge(i,i+s-1,i+s/2-1);
            i+=s;
        }
//处理末尾残余部分
        merge(i,n-1,i+s/2-1);
        s*=2;
    }
//最后再从头到尾处理一遍
    merge(0,n-1,s/2-1);
}

 

自然归并排序

---

 

　　通常，子串在排序之前就已经有序，我们需要记录下已经有序的子串的数量以及其各自的头尾位置，在排序时无需再对这些子串进行排序，直接合并即可。

　　实现记录有序子串函数是 pass() 函数，其中的 rec 用于记录有序子串的头尾位置，pass 函数返回有序串的个数。

// 自然归并是归并排序的一个变形，效率更高一些，可以在归并排序非递归实现的基础上进行修改
//对于已经一个已经给定数组a,通常存在多个长度大于1的已经自然排好的子数组段
//因此用一次对数组a的线性扫描就可以找出所有这些排好序的子数组段
//然后再对这些子数组段俩俩合并
//代码的实现如下：
#include<iostream>
using namespace std;
const int SIZE = 100;
int arr[SIZE];
int rec[SIZE];//记录每个子串的起始坐标
//排序数组arr[fir:end]
//合并操作的子函数
void merge(int fir,int end,int mid);
//扫描得到子串的子函数
int pass(int n);
//自然合并函数
void mergeSort3(int n);
/********************************************************************/

void mergeSort3(int n){
int num=pass(n);
while(num!=2){
//num=2说明已经排好序了
//每循环一次，进行一次pass()操作
for(int i=0;i<num;i+=2)
//坐标解释可参加P23页的图示
            merge(rec[i],rec[i+2]-1,rec[i+1]-1);
        num=pass(n);
    }
}
void merge(int fir,int end,int mid){
//合并
int tempArr[SIZE];
int fir1=fir,fir2=mid+1;
for(int i=fir;i<=end;i++){
if(fir1>mid)
            tempArr[i]=arr[fir2++];
else if(fir2>end)
            tempArr[i]=arr[fir1++];
else if(arr[fir1]>arr[fir2])
            tempArr[i]=arr[fir2++];
else 
            tempArr[i]=arr[fir1++];
    }
for(int i=fir;i<=end;i++)
        arr[i]=tempArr[i];
}
int  pass(int n){
int num=0;
int biger=arr[0];
    rec[num++]=0;
for(int i=1;i<n;i++){
if(arr[i]>=biger)biger=arr[i];
else {
            rec[num++]=i;
            biger=arr[i];
        }
    }
//给rec[]加一个尾巴，方便排序
    rec[num++]=n;
return num;
}
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++)cin>>arr[i];
//测试mergeSort函数
/**/mergeSort3(n);
for(int i=0;i<n;i++)cout<<arr[i]<<" ";
        cout<<endl;

//测试pass函数
/*int num = pass(n);
        for(int i=0;i<num;i++)cout<<rec[i]<<" ";
        cout<<endl;*/
    }
return 0;
}

 

参考

---

 

　　归并排序(递归实现+非递归实现+自然合并排序)