锐客网

  1. 首页 > 睿知 > it技术 > >

go语言归并 go归并排序

IT技术进程

golang标准库之sort 标准库sort实现了4种排序方法，插入排序 、 堆排序 、 快排 和 归并排序，但是并没有暴露给用户接口 。sort包会根据数据选择最优的排序方法(其实只使用了3种 ，  归并排序 除外) 。
用户需要实现以下接口才能使用sort包的排序功能 。
对于常用的类型( 整型切片 、 float64切片 、 String切片 )，sort包提供了内置的接口实现
使用举例如下：
举例如下：
归并排序的示例代码归并排序原理
归并排序具体工作原理如下（假设序列共有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 / 2left := mergeSort(r[:num])right := mergeSort(r[num:])return merge(left, right)}func merge(left, right []int) (result []int) {l, r := 0, 0for llen(left)rlen(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　(imj　=　t)　{if　(a[i]　=　a[j])　{tmp[k]　=　a[i];k++;i++;}　else　{tmp[k]　=　a[j];j++;k++;}}while　(im)　{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　/　(len1);int　c　=　size((len1)　-　1);//　-------归并到只剩一个有序集合的时候结束算法-------//if　(mid　==　0)return;//　------进行一趟归并排序-------//for　(int　i　=　0;　imid;　++i)　{s　=　i　*　2　*　len;merge(a,　s,　s　+　len,　(len1)　+　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;　ia.length;　++i)　{System.out.print(a[i]　+);}}}Python语言def MergeSort(lists):if len(lists) = 1:return listsnum = int( len(lists)/2 )left = MergeSort(lists[:num])right = MergeSort(lists[num:])return Merge(left, right)def Merge(left,right):r, l=0, 0result=[]while llen(left) and rlen(right):if left[l]right[r]:result.append(left[l])l += 1else:result.append(right[r])r += 1result += 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+1j!=endIndex+1){if(sourceArr[i] = sourceArr[j])tempArr[k++] = sourceArr[j++];elsetempArr[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(startIndexendIndex){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 = qr, 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语言

推荐阅读


上一篇：如何协作医药电商，怎样做好医药电子商务的员工

下一篇：斗鱼主播靓旭直播间漏批，斗鱼靓旭为什么不直播了