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

bindong · · 1511 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

最近对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~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 }

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         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 }