遞歸算法
将待排元素分成大小大緻相同的兩個子集合,分别對這兩個集合進行排序,最終将排好序的子集合合并。
#include<iostream>
#include<cstdio>
void Merge(int s[],int t[],int b,int m,int e){//将s[b...m]與s[m+1...e]合并
int i=b;//i->前一個塊
int j=m+1;//j->後一個塊
int k=0;//k->t數組
while(i<=m&&j<=e){
if(s[i]<=s[j])t[k++]=s[i++];
else t[k++]=s[j++];
}
while(i<=m){
t[k++]=s[i++];
}
while(j<=e){
t[k++]=s[j++];
}
for(int i=0;i<k;i++){ //每次都把序數組t的值賦回給s,這樣s對于區間[b,e]也是有序的
s[b+i]=t[i];
}
}
void MSort(int s[],int t[],int b,int e){
if(b<e){
int m;
m=(b+e)/2;
MSort(s,t,b,m);
MSort(s,t,m+1,e);
Merge(s,t,b,m,e);
}
}
int main(){
int a[10]={2,5,1,3,4,9,7,8,6,0};
int temp[10];
MSort(a,temp,0,9);
for(int i=0;i<10;i++){
printf("%d ",a[i]);
}
printf("\n");
}
非遞歸算法
有三個函數:
(1)Merge函數,用于合并兩個有序子段。這個函數主要是用于将a數組中[l,m]區間和[m+1,r]區間的數有序的合并到b數組的[l,r]區間。這裡不同于遞歸方法裡的Merge函數,b數組從l開始到r結束是有序的并且不用在Merge函數尾部将b數組的有序部分指派給a數組(原因下面提到)。
(2)MergePass函數,這個函數的功能對于長為n數組進行歸并,兩個兩個地合并長度為s的子段,當然我們的數組長度不可能每次正好滿足“以s為子段長度時正好能兩兩合并,一個不多一個不少”。是以我們要對特殊情況進行判斷:
while(i<=n-2*s){//剩下不超過2s長度的元素
Merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
在剩下的元素不能組成兩個子段的時候分情況讨論:
a.當剩下元素可以湊成一個長為s子段,Merge(x,y,i,i+s-1,n-1);
b.當剩下元素連一個長為s的字段都湊不成時,我們直接将其略過(不排序)
(3)MergeSort函數,這個數組首先設一個臨時數組b,與要歸并的子段長度s,s初始為1,在s<n的前提下,我們每次調用MergePass函數,使得a數組中,以s為子段長度,每個子段内部都有序地排列,這次排好的序列展現在b數組上,a數組此時沒變!然後将s+=s;可以開始兩兩合并之前長為s的子段啦!這次把b再合并到a上,是以一趟下來,最後a是“有序的”,這也是Merge函數裡不用把數組b再賦給a的原因了,省了一趟指派!
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
void Merge(int a[],int b[],int l,int m,int r){
int i=l,j=m+1,k=l;
while(i<=m&&j<=r){
if(a[i]<a[j])b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=m)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
}
void MergePass(int x[],int y[],int s,int n){
int i=0;
while(i<=n-2*s){//剩下超過2*s長度的元素
Merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
//剩下不超過2s長度的元素
if(i+s<n)Merge(x,y,i,i+s-1,n-1);//剩下的長度小于2*s大于s
else{//剩下的長度小于s
for(int j=i;j<=n-1;j++){
y[j]=x[j];
}
}
}
void MergeSort(int a[],int n){
int b[10];
int s=1;
while(s<n){
MergePass(a,b,s,n);//把a合并到b中
s+=s;
MergePass(b,a,s,n);//把b合并到a中
s+=s;
}
}
int main(){
int a[10]={2,5,1,3,4,9,7,8,6,0};
int n=10;
MergeSort(a,n);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
自然合并排序
自然合并排序:對于初始給定的數組,通常存在多個長度大于1的已自然排好序的子數組段.例如,若數組a中元素為{4,8,3,7,1,5,6,2},則自然排好序的子數組段有{4,8},{3,7},{1,5,6},{2}.用一次對數組a的線性掃描就足以找出所有這些排好序的子數組段.然後将相鄰的排好序的子數組段兩兩合并,構成更大的排好序的子數組段({3,4,7,8},{1,2,5,6}).繼續合并相鄰排好序的子數組段,直至整個數組已排好序.
是以我們可以設變量flag表示序列中有幾段已經排好序的子段。
設數組t[flag]表示每個有序子段的第一個元素所在的位置。
代碼如下:
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int t[10],flag=0;
void Merge(int a[],int b[],int l,int m,int r){
int i=l,j=m+1,k=l;
while(i<=m&&j<=r){
if(a[i]<a[j])b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=m)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
}
void getPos(int a[],int t[],int n){
t[flag++]=0;
for(int i=0;i<n-1;i++){
if(a[i+1]<a[i])t[flag++]=i+1;
}
for(int i=0;i<flag;i++)printf("%d ",t[i]);
printf("\n");
}
void MergePass(int x[],int y[],int s,int n){
int i=0;//i表示第幾段
while(i<=flag-2*s){
int r=((i+2*s)<flag)?t[i+2*s]:n;
Merge(x,y,t[i],t[i+s]-1,r-1);//把兩個長度為s的段合并在一起
i=i+2*s;
}
if(i+s<flag)Merge(x,y,t[i],t[i+s]-1,n-1);
else{
for(int j=t[i];j<=n-1;j++){
y[j]=x[j];
}
}
}
void MergeSort(int a[],int n){
int b[10];
int s=1;
while(s<flag){//最多flag段
MergePass(a,b,s,n);//把a合并到b中
s+=s;
MergePass(b,a,s,n);//把b合并到a中
s+=s;
}
}
int main(){
int a[10]={2,1,5,3,4,9,7,8,0,6};
int n=10;
getPos(a,t,n);
MergeSort(a,n);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
(第一行輸出的是t數組,标記每個有序段的起始位置
第二行輸出的是排好序的數組)