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

 1 /*
 2 归并排序的go语言实现
 3 */
 4 package main
 5 
 6 import fmt "fmt"
 7 
 8 func main () {
 9 /*
10  生成需要排序的队列100~1
11 */
12 length:=100
13 A:=make([]int,length)
14 j:=length
15 for i:=0;i<length;i++{
16 A[i]=j
17 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:=0
37 if(r-q+1)%2==0{
38 q=(p+r-1)/2
39 }else{
40 q=(p+r)/2
41  }
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+1
53 n2:=r-q
54 
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:=0
68 iRnum:=0
69 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 }

 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 else
35  {
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 else
73  {
74 A[i]=R_Arr[iRnum];
75 iRnum++;
76  }
77  }
78 }

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传