c 和 Python 實現歸併排序（遞歸，非遞歸）

C:

#include <iostream>

using namespace std;

#define MAXSIZE 9

typedef struct

{

int r[MAXSIZE+1];

int length;

}SqList;

//遞歸實現歸併排序

void Merge(int SR[],int TR[],int i ,int m ,int n)

{

int j,k,l;

for(j=m+1,k=i;i<=m && j<=n;k++) //兩個序列，i第一個序列起點，j=m+1第二個序列起點

{

if (SR[i]<SR[j])

TR[k]=SR[i++]; //第一個序列的第一個比第二個序列的第一個小，所以賦值然後i+,取第一個序列的下一個

else

TR[k]=SR[j++];

}

if(i<=m)

{

for (l=0;l<=m-i;l++)

TR[k+l]=SR[i+l];

}

if(j<=n)

{

for (l=0;l<=n-j;l++)

TR[k+l]=SR[j+l];

}

}

void MSort(int SR[],int TR1[],int s,int t )

{

int m;

int TR2[MAXSIZE+1];

if (s==t)

{

TR1[s]=SR[s];

}

else

{

m=(s+t)/2;

MSort(SR,TR2,s,m);

MSort(SR,TR2,m+1,t);

Merge(TR2,TR1,s,m,t); //傳三個參數目的 起點，分離點 ，終點

}

}

void MergeSort(SqList *L)

{

MSort(L->r,L->r,1,L->length);

}

//非遞歸實現歸併排序

void MergePass(int SR[],int TR[],int s ,int n)

{

int i =1;

int j;

while(i<n-2*s+1)

{

Merge(SR,TR,i,i+s-1,i+2*s-1);

i=i+2*s;

}

if(i<n-s+1)

Merge(SR,TR,i,i+s-1,n);

else

for(j=i;j<=n;j++)

TR[j]=SR[j];

}

void MergeSort2(SqList *L)

{

int* TR= (int*)malloc(L->length*sizeof(int));

int k=1;

while(k<L->length)

{

MergePass(L->r,TR,k,L->length);

k=2*k;

MergePass(TR,L->r,k,L->length);

k=2*k;

}

}

int main()

{

SqList* L = ( SqList* ) malloc( sizeof( SqList ) );//分配內存，初始化

L ->length=9;

for(int i=1;i<=L->length;i++)

{

cin>>L ->r[i];

}

for(int i=1;i<=L->length;i++)

{

cout<<L ->r[i];

}

MergeSort(L);

//MergeSort2(L);

for(int i=1;i<=L->length;i++)

{

cout<<L ->r[i];

}

}

Python：

L3=[0,50,10,90,30,70,40,80,60,20]

def Merge(SR,TR,i,m,n):

j=m+1

k=i

while (i<=m and j<=n):

if(SR[i]<SR[j]):

TR[k]=SR[i]

i=i+1

else:

TR[k]=SR[j]

j=j+1

k=k+1

if i<=m:

for l in range(0,m-i+1):

TR[k+l]=SR[i+l]

if j<=n:

for l in range(0,n-j+1):

TR[k+l]=SR[j+l]

#遞歸

def MSort(SR,TR1,s,t):

TR2=[0,0,0,0,0,0,0,0,0,0]

if(s==t):

TR1[s]=SR[s]

else:

m=(s+t)//2

MSort(SR,TR2,s,m)

MSort(SR,TR2,m+1,t)

Merge(TR2,TR1,s,m,t)

def MergeSort(L):

MSort(L,L,1,(len(L)-1))

#非遞歸

def MergePass(SR,TR,s,n):

i=1

while(i<=n-2*s+1):

Merge(SR,TR,i,i+s-1,i+2*s-1)

i=i+2*s

if i<(n-s+1):

Merge(SR,TR,i,i+s-1,n)

else:

for j in range(i,n+1):

TR[j]=SR[j]

def MergeSort2(L):

TR=[0,0,0,0,0,0,0,0,0,0]

k=1

while(k<len(L)):

MergePass(L,TR,k,len(L)-1)

k=2*k

MergePass(TR,L3,k,len(L)-1)

k=2*k

if __name__ == "__main__":

#MergeSort(L3)

MergeSort2(L3)

print(L3)

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！