go语言排序代码，go语言快速排序

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

归并排序的示例代码

归并排序原理

归并排序具体工作原理如下（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素

将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

重复步骤2，直到所有元素排序完毕

示例代码

Go语言 func mergeSort(r []int) []int { length := len(r) if length = 1 { return r } num := length / 2 left := mergeSort(r[:num]) right := mergeSort(r[num:]) return merge(left, right)}func merge(left, right []int) (result []int) { l, r := 0, 0 for l len(left) r len(right) { if left[l] right[r] { result = append(result, left[l]) l++ } else { result = append(result, right[r]) r++ } } result = append(result, left[l:]...) result = append(result, right[r:]...) return}Java语言 package　algorithm;public　class　MergeSort　{ //　private　static　long　sum　=　0; /** 　*　pre 　*　二路归并　*　原理：将两个有序表合并和一个有序表　*　/pre 　*　　*　@param　a 　*　@param　s 　*　第一个有序表的起始下标　*　@param　m 　*　第二个有序表的起始下标　*　@param　t 　*　第二个有序表的结束小标　*　　*/ private　static　void　merge(int[]　a,　int　s,　int　m,　int　t)　{ int[]　tmp　=　new　int[t　-　s　+　1]; int　i　=　s,　j　=　m,　k　=　0; while　(i　　m　　j　=　t)　{ if　(a[i]　=　a[j])　{ tmp[k]　=　a[i]; k++; i++; }　else　{ tmp[k]　=　a[j]; j++; k++; } } while　(i　　m)　{ tmp[k]　=　a[i]; i++; k++; } while　(j　=　t)　{ tmp[k]　=　a[j]; j++; k++; } System.arraycopy(tmp,　0,　a,　s,　tmp.length); } /** 　*　　*　@param　a 　*　@param　s 　*　@param　len 　*　每次归并的有序集合的长度　*/ public　static　void　mergeSort(int[]　a,　int　s,　int　len)　{ int　size　=　a.length; int　mid　=　size　/　(len　　1); int　c　=　size　　((len　　1)　-　1); //　-------归并到只剩一个有序集合的时候结束算法-------// if　(mid　==　0) return; //　------进行一趟归并排序-------// for　(int　i　=　0;　i　　mid;　++i)　{ s　=　i　*　2　*　len; merge(a,　s,　s　+　len,　(len　　1)　+　s　-　1); } //　-------将剩下的数和倒数一个有序集合归并-------// if　(c　!=　0) merge(a,　size　-　c　-　2　*　len,　size　-　c,　size　-　1); //　-------递归执行下一趟归并排序------// mergeSort(a,　0,　2　*　len); } public　static　void　main(String[]　args)　{ int[]　a　=　new　int[]　{　4,　3,　6,　1,　2,　5　}; mergeSort(a,　0,　1); for　(int　i　=　0;　i　　a.length;　++i)　{ System.out.print(a[i]　+); } }}Python语言 def MergeSort(lists): if len(lists) = 1: return lists num = int( len(lists)/2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) return Merge(left, right)def Merge(left,right): r, l=0, 0 result=[] while llen(left) and rlen(right): if left[l] right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += right[r:] result+= left[l:] return resultprint MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])C语言 #include stdlib.h#include stdio.hvoid Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){ int i = startIndex, j=midIndex+1, k = startIndex; while(i!=midIndex+1 j!=endIndex+1) { if(sourceArr[i] = sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } while(i != midIndex+1) tempArr[k++] = sourceArr[i++]; while(j != endIndex+1) tempArr[k++] = sourceArr[j++]; for(i=startIndex; i=endIndex; i++) sourceArr[i] = tempArr[i];}//内部使用递归void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){ int midIndex; if(startIndex endIndex) { midIndex = (startIndex + endIndex) / 2; MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex+1, endIndex); Merge(sourceArr, tempArr, startIndex, midIndex, endIndex); }}int main(int argc, char * argv[]){ int a[8] = {50, 10, 20, 30, 70, 40, 80, 60}; int i, b[8]; MergeSort(a, b, 0, 7); for(i=0; i8; i++) printf(%d , a[i]); printf(\n); return 0;}PHP语言 //merge函数将指定的两个有序数组(arr1arr2,)合并并且排序//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据functional_merge($arrA,$arrB){ $arrC = array(); while(count($arrA) count($arrB)){ //这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值, //不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用 $arrC[] = $arrA['0'] $arrB['0'] ? array_shift($arrA) : array_shift($arrB); } returnarray_merge($arrC, $arrA, $arrB);}//归并排序主程序functional_merge_sort($arr){ $len=count($arr); if($len = 1) return $arr;//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组 $mid = intval($len/2);//取数组中间 $left_arr = array_slice($arr, 0, $mid);//拆分数组0-mid这部分给左边left_arr $right_arr = array_slice($arr, $mid);//拆分数组mid-末尾这部分给右边right_arr $left_arr = al_merge_sort($left_arr);//左边拆分完后开始递归合并往上走 $right_arr = al_merge_sort($right_arr);//右边拆分完毕开始递归往上走 $arr=al_merge($left_arr, $right_arr);//合并两个数组,继续递归 return $arr;}$arr = array(12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9);print_r(al_merge_sort($arr));Pascal语言 program　mergesort_1;const　maxn=7;type　arr=array[1..maxn]　of　integer;var　a,b,c:arr;i:integer;procedure　merge(r:arr;l,m,n:integer;varr2:arr);var　i,j,k,p:integer;begin　i:=l;　j:=m+1;　k:=l-1;　while　(i=m)　and　(j=n)　do　begin　k:=k+1;　if　r[i]=r[j]　then　begin　r2[k]:=r[i];　i:=i+1　end　else　begin　r2[k]:=r[j];　j:=j+1;　end　end;　if　i=m　then　for　p:=i　to　m　do　begin　k:=k+1;　r2[k]:=r[p];　end;　if　j=n　then　for　p:=j　to　n　do　begin　k:=k+1;　r2[k]:=r[p];　end;end;procedure　mergesort(var　r,r1:arr;s,t:integer);var　k:integer;c:arr;begin　if　s=t　then　r1[s]:=r[s]　else　begin　k:=(s+t)div2;　mergesort(r,c,s,k);　mergesort(r,c,k+1,t);　merge(c,s,k,t,r1)　end;end;begin　write('Enterdata:');　for　i:=1　to　maxn　do　read(a[i]);　mergesort(a,b,1,maxn);　for　i:=1　to　maxn　do　write(b[i]:9);　writeln;end.//============================================program　mergesort_2;const　max=100000;var　a,r:array[1..max]　of　long　int;n,i:long　int;procedure　msort(s,t:longint);var　m,i,j,k:long　int;begin　if　s=t　then　exit;　m:=(s+t)div2;　msort(s,m);　msort(m+1,t);　i:=s;　j:=m+1;　k:=s;　while　(i=m)　and　(j=t)　do　begin　if　a[i]a[j]　then　begin　r[k]:=a[i];　inc(i);　inc(k);　end　else　begin　r[k]:=a[j];　inc(j);　inc(k);　end;　end;　while　i=m　do　begin　r[k]:=a[i];　inc(i);　inc(k);　end;　while　j=t　do　begin　r[k]:=a[j];　inc(j);　inc(k);　end;　for　i:=s　to　t　do　a[i]:=r[i];end;begin　readln(n);　for　i:=1　to　n　do　read(a[i]);　msort(1,n);　for　i:=1　to　n　do　writeln(a[i]);end.Basic语言 Sub MergeSort(Array() As Integer, First As Integer, Last As Integer)Dim mid As Integer = 0If firstlast Then mid = (first+last)\ 2MergeSort(Array, first, mid);MergeSort(Array, mid+1, last);Merge(Array, first, mid, last);End IfEnd Sub/*以下示例代码实现了归并操作。array[]是元素序列，其中从索引p开始到q位置，按照升序排列，同时，从(q+1)到r也已经按照升序排列，merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。*//*** 0 = p = q r, subarray array[p..q] and array[q+1..r] are already sorted.* the merge() function merges the two sub-arrays into one sorted array.*/void Merge(int array[], int p, int q, int r){ int i,k; int begin1,end1,begin2,end2; int* temp = (int*)malloc((r-p+1)*sizeof(int)); begin1 = p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 = end1)( begin2 = end2)) { if(array[begin1] = array[begin2]){ temp[k] = array[begin1]; begin1++; } else { temp[k] = array[begin2]; begin2++; } k++; } while(begin1=end1 || begin2=end2) { if(begin1=end1) { temp[k++] = array[begin1++]; } if(begin2=end2) { temp[k++] = array[begin2++]; } } for (i = 0; i =(r - p); i++) array[p+i] = temp[i]; free(temp);}JavaScript语言

使用递归的代码如下。优点是描述算法过程思路清晰，缺点是使用递归，mergeSort()函数频繁地自我调用。长度为n的数组最终会调用mergeSort()函数 2n-1次，这意味着一个长度超过1500的数组会在Firefox上发生栈溢出错误。可以考虑使用迭代来实现同样的功能。 function　merge(left, right){ var　result=[]; while(left.length0 right.length0){ if(left[0]right[0]){ /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/ result.push(left.shift()); }else{ result.push(right.shift()); } } return　result.concat(left).concat(right);}function　mergeSort(items){ if(items.length == 1){ return　items;}var　middle = Math.floor(items.length/2), left = items.slice(0, middle), right = items.slice(middle); return　merge(mergeSort(left), mergeSort(right));}非递归算法（C++） #includeiostream#includectime#includecstring#includecstdlibusing namespace std;/**将a开头的长为length的数组和b开头长为right的数组合并n为数组长度，用于最后一组*/void　Merge(int*　data,int　a,int　b,int　length,int　n){　int　right;　if(b+length-1 = n-1)　right = n-b;　else　right = length;　int*　temp = new　int[length+right];　int　i=0, j=0;　while(i=length-1 j=right-1){ 　if(data[a+i] = data[b+j]){ 　 temp[i+j] = data[a+i];i++; } 　else{ temp[i+j] = data[b+j]; j++; }　}　if(j == right){//a中还有元素，且全都比b中的大,a[i]还未使用　 memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int));　} else if(i == length){ memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int)); }　memcpy(data+a, temp, (right + length) * sizeof(int));　delete [] temp;}void　MergeSort(int*　data, int　n){　int　step = 1;　while(step n){ 　for(int　i=0; i=n-step-1; i+=2*step) 　 Merge(data, i, i+step, step, n); //将i和i+step这两个有序序列进行合并 //序列长度为step //当i以后的长度小于或者等于step时，退出　step*=2;//在按某一步长归并序列之后，步长加倍　}}int　main(){　int　n;　cinn;　int*　data = new　int[n];　if(!data)　exit(1);　int　k = n;　while(k--){　 cindata[n-k-1];　}　clock_t　s = clock();　MergeSort(data, n);　clock_t　e = clock();　k=n;　while(k--){　 coutdata[n-k-1]' ';　}　coutendl;　coutthe algorithm usede-smiliseconds.endl;　delete　data;　return　0;}二路归并

ConstFI='in.txt';FO='out.txt';MaxN=10000;TypeTIndex=Longint;TDat=Array[0..MaxN]OfTIndex;VarN:TIndex;Dat:TDat;Tmp:TDat;ProcedureMerge(L,Mid,R:TIndex);VarP1,P2:TIndex;E1,E2:TIndex;P:TIndex;I:TIndex;BeginP1:=L;P2:=Mid+1;P:=L;RepeatIf(Dat[P1]=Dat[P2])ThenBeginTmp[P]:=Dat[P1];Inc(P1);Inc(P);EndElseBeginTmp[P]:=Dat[P2];Inc(P2);Inc(P);End;Until(P1=Mid+1)Or(P2=R+1);If(P1=Mid+1)ThenBeginE1:=P2;E2:=R;EndElseBeginE1:=P1;E2:=Mid;End;ForI:=E1ToE2DoBeginTmp[P]:=Dat[I];Inc(P);End;End;ProcedureSort(L,R:TIndex);VarMid:TIndex=0;BeginMid:=(L+R)Shr1;If(LMid)ThenSort(L,Mid);If(Mid+1R)ThenSort(Mid+1,R);Merge(L,Mid,R);ForMid:=LToRDoDat[Mid]:=Tmp[Mid];End;ProcedureInit;VarI:TIndex;BeginFillChar(Dat,SizeOf(Dat),0);Readln(N);ForI:=1ToNDoRead(Dat[I]);End;ProcedureMain;BeginSort(1,N);End;ProcedureFinal;VarI:TIndex;BeginForI:=1ToNDoWrite(Dat[I],'');Writeln;End;BeginAssign(Input,FI);Assign(Output,FO);Reset(Input);Rewrite(Output);Init;Main;Final;Close(Input);Close(Output);End.

Delphi归并排序完整源代码例子： //合并子函数procedureTForm1.MergePass(vardatas:arrayofInteger;left,mid,right:Integer);vartmpArr:arrayofInteger;arrLen:Integer;i,k:Integer;begin1,begin2,end1,end2:Integer;beginarrLen:=right-left+1;SetLength(tmpArr,arrLen);begin1:=left;end1:=mid;begin2:=mid+1;end2:=right;k:=0;while((begin1=end1)and(begin2=end2))dobeginif(datas[begin1]datas[begin2])thenbegintmpArr[k]:=datas[begin1];Inc(begin1);endelsebegintmpArr[k]:=datas[begin2];Inc(begin2);end;inc(k);end;while(begin1=end1)dobegintmpArr[k]:=datas[begin1];Inc(begin1);Inc(k);end;while(begin2=end2)dobegintmpArr[k]:=datas[begin2];Inc(begin2);Inc(k);end;fori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i];end;end;//排序主函数，left是数组左下标，0开始。right是数组右下标。procedureTForm1.MergeSort(vardatas:arrayofInteger;left,right:Integer);varmid:Integer;i:Integer;beginmid:=0;if(leftright)thenbeginmid:=(right+left)div2;showLog('中间索引：'+inttostr(mid));MergeSort(datas,left,mid);MergeSort(datas,mid+1,right);MergePass(datas,left,mid,right);showLog('---'+getArrayString(datas));//显示数组中间状态end;end;//调用方法：procedureTForm1.btn1Click(Sender:TObject);varinArr:array[0..9]ofInteger;beginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);showLog('输入数据：'+getArrayString(inArr));MergeSort(inArr,0,High(inArr));showLog('输出数据：'+getArrayString(inArr));end;