首页 > 代码库 > 归并排序的go语言与C++实现对比

归并排序的go语言与C++实现对比

 

最近对go语言发生了兴趣,发现go语言语法简洁,非常适合算法的描述和实现,于是对归并排序进行了实现。

例子中需要排序的队列是长度为100的从100到1的数列,排序算法是正序排序,排序正确的话,结果应当为1到100。

因为已设定数组最大值为100,因此“哨兵”简略设置为1000,因为不是算法核心部分,此处“哨兵”最大值处理省略。

 1 /* 2 归并排序的go语言实现 3 */ 4 package main 5  6 import fmt "fmt" 7  8 func main () { 9     /*10     生成需要排序的队列100~111     */12     length:=10013     A:=make([]int,length)14     j:=length15     for i:=0;i<length;i++{16         A[i]=j17         j--18     }19     /*20     排序21     */22     MergeSort(A,0,length-1)23     /*24     输出排序后的队列25     */26     for i:=0;i<length;i++{27         fmt.Println(A[i])28     }29 }30 /*31 归并排序32 */33 func MergeSort(Arrary []int,p int,r int) {34 35     if p<r {36         q:=037         if(r-q+1)%2==0{38             q=(p+r-1)/239         }else{40             q=(p+r)/241         }42 43         MergeSort(Arrary,p,q)44         MergeSort(Arrary,q+1,r)45         Merge(Arrary,p,q,r)46     }47 }48 /*49 两列已排序的数组合并50 */51 func Merge(Arrary []int,p int,q int,r int) {52     n1:=q-p+153     n2:=r-q54 55     L_Arr:=make([]int,(n1+1))56     R_Arr:=make([]int,(n2+1))57 58     for i:=0;i<n1;i++{59         L_Arr[i]=Arrary[p+i]60     }61     L_Arr[n1]=1000;62 63     for i:=0;i<n2;i++{64         R_Arr[i]=Arrary[q+1+i]65     }66     R_Arr[n2]=1000;67     iLnum:=068     iRnum:=069     for i:=p;i<r+1;i++{70         if L_Arr[iLnum]<R_Arr[iRnum] {71             Arrary[i]=L_Arr[iLnum]72             iLnum++73         }else{74             Arrary[i]=R_Arr[iRnum]75             iRnum++76         }77     }78 }

 

C++实现

 1 #include <iostream> 2 using namespace std; 3 void MergeSort(int *,int ,int); 4 void Merge(int *, int, int,int); 5 int main(void) 6 { 7        //生成需排列的数组 8     int length=100; 9     int *A=new int[length];10     for(int i=0,j=length;i<length;i++,j--)11     {12         A[i]=j;13     }14     MergeSort(A,0,length-1);15     for(int i=0;i<length;i++)16     {17         cout<<A[i]<<" ";18     }19     return 0;20 }21 /*22 A[p...r]23 */24 void MergeSort(int *A,int p,int r)25 {26     if(p<r)27     {28         int q=0;29                 //q要取地板,不然在q+1时会溢出30         if((r-q+1)%2==0)31         {32             q=(p+r-1)/2;33         }34         else35         {36             q=(p+r)/2;37         }38         MergeSort(A,p,q);39         MergeSort(A,q+1,r);40         Merge(A,p,q,r);41     }42 }43 /*44 A[p...q],A[q+1...r]45 */46 void Merge(int *A,int p,int q,int r)47 {48     int n1=q-p+1;49     int n2=r-q;50 51     int *L_Arr=new int[n1+1];52     int *R_Arr=new int[n2+1];53     for(int i=0;i<n1;i++)54     {55         L_Arr[i]=A[p+i];56     }57     L_Arr[n1]=1000;58     for(int i=0;i<n2;i++)59     {60         R_Arr[i]=A[q+1+i];61     }62     R_Arr[n2]=1000;63     int iLnum=0;64     int iRnum=0;65     for(int i=p;i<r+1;i++)66     {67         if(L_Arr[iLnum]<R_Arr[iRnum])68         {69             A[i]=L_Arr[iLnum];70             iLnum++;71         }72         else73         {74             A[i]=R_Arr[iRnum];75             iRnum++;76         }77     }78 }

 

归并排序的go语言与C++实现对比