首页 > 代码库 > 归并排序的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++实现对比
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。