最近对go语言发生了兴趣，发现go语言语法简洁，非常适合算法的描述和实现，于是对归并排序进行了实现。
例子中需要排序的队列是长度为100的从100到1的数列，排序算法是正序排序，排序正确的话，结果应当为1到100。
因为已设定数组最大值为100，因此“哨兵”简略设置为1000，因为不是算法核心部分，此处“哨兵”最大值处理省略。
/*
归并排序的go语言实现
*/
package main import fmt "fmt" func main () {
/*
生成需要排序的队列100~1
*/
length:=
A:=make([]int,length)
j:=length
for i:=;i<length;i++{
A[i]=j
j--
}
/*
排序
*/
MergeSort(A,,length-)
/*
输出排序后的队列
*/
for i:=;i<length;i++{
fmt.Println(A[i])
}
}
/*
归并排序
*/
func MergeSort(Arrary []int,p int,r int) { if p<r {
q:=
if(r-q+)%=={
q=(p+r-)/
}else{
q=(p+r)/
} MergeSort(Arrary,p,q)
MergeSort(Arrary,q+,r)
Merge(Arrary,p,q,r)
}
}
/*
两列已排序的数组合并
*/
func Merge(Arrary []int,p int,q int,r int) {
n1:=q-p+
n2:=r-q L_Arr:=make([]int,(n1+))
R_Arr:=make([]int,(n2+)) for i:=;i<n1;i++{
L_Arr[i]=Arrary[p+i]
}
L_Arr[n1]=; for i:=;i<n2;i++{
R_Arr[i]=Arrary[q++i]
}
R_Arr[n2]=;
iLnum:=
iRnum:=
for i:=p;i<r+;i++{
if L_Arr[iLnum]<R_Arr[iRnum] {
Arrary[i]=L_Arr[iLnum]
iLnum++
}else{
Arrary[i]=R_Arr[iRnum]
iRnum++
}
}
}
C++实现
#include <iostream>
using namespace std;
void MergeSort(int *,int ,int);
void Merge(int *, int, int,int);
int main(void)
{
//生成需排列的数组
int length=;
int *A=new int[length];
for(int i=,j=length;i<length;i++,j--)
{
A[i]=j;
}
MergeSort(A,,length-);
for(int i=;i<length;i++)
{
cout<<A[i]<<" ";
}
return ;
}
/*
A[p...r]
*/
void MergeSort(int *A,int p,int r)
{
if(p<r)
{
int q=;
//q要取地板，不然在q+1时会溢出
if((r-q+)%==)
{
q=(p+r-)/;
}
else
{
q=(p+r)/;
}
MergeSort(A,p,q);
MergeSort(A,q+,r);
Merge(A,p,q,r);
}
}
/*
A[p...q],A[q+1...r]
*/
void Merge(int *A,int p,int q,int r)
{
int n1=q-p+;
int n2=r-q; int *L_Arr=new int[n1+];
int *R_Arr=new int[n2+];
for(int i=;i<n1;i++)
{
L_Arr[i]=A[p+i];
}
L_Arr[n1]=;
for(int i=;i<n2;i++)
{
R_Arr[i]=A[q++i];
}
R_Arr[n2]=;
int iLnum=;
int iRnum=;
for(int i=p;i<r+;i++)
{
if(L_Arr[iLnum]<R_Arr[iRnum])
{
A[i]=L_Arr[iLnum];
iLnum++;
}
else
{
A[i]=R_Arr[iRnum];
iRnum++;
}
}
}