java实现归并排序(java归并排序程序讲解)
归并排序的示例代码
归并排序原理
归并排序具体工作原理如下（假设序列共有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;
JAVA归并排序算法，有两行代码看不懂
以var a = [4,2,6,3,1,9,5,7,8,0];为例子。
1.希尔排序。 希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。
function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap0){ for (var k = 0; k gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i = k+gap; i len; i=i+gap) { temp = arr[i]; tagArr.push(temp); for (j=i-gap; j -1; j=j-gap) { if(arr[j]temp){ arr[j+gap] = arr[j]; }else{ break; } } arr[j+gap] = temp; } console.log(tagArr,"gap:"+gap);//输出当前进行插入排序的数组。 console.log(arr);//输出此轮排序后的数组。 } gap = parseInt(gap/2); } return arr; }
过程输出：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
由输出可以看到。第一轮间隔为5。依次对这些间隔的数组插入排序。
间隔为5：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
间隔为2：
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1
排序后：
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
间隔为1：
排序后：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
2.快速排序。把一个数组以数组中的某个值为标记。比这个值小的放到数组的左边，比这个值得大的放到数组的右边。然后再递归 对左边和右边的数组进行同样的操作。直到排序完成。通常以数组的第一个值为标记。
代码:
function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len2){ return arr; } tag = arr[0]; for(i=1;ilen;i++){ if(arr[i]=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); }
3.归并排序。把一系列排好序的子序列合并成一个大的完整有序序列。从最小的单位开始合并。然后再逐步合并合并好的有序数组。最终实现归并排序。
合并两个有序数组的方法：
function subSort(arr1,arr2){ var len1 = arr1.length,len2 = arr2.length,i=0,j=0,arr3=[],bArr1 = arr1.slice(),bArr2 = arr2.slice(); while(bArr1.length!=0 || bArr2.length!=0){ if(bArr1.length == 0){ arr3 = arr3.concat(bArr2); bArr2.length = 0; }else if(bArr2.length == 0){ arr3 = arr3.concat(bArr1); bArr1.length = 0; }else{ if(bArr1[0]=bArr2[0]){ arr3.push(bArr1[0]); bArr1.shift(); }else{ arr3.push(bArr2[0]); bArr2.shift(); } } } return arr3; }
归并排序：
function mergeSort(arr){ var len= arr.length,arrleft=[],arrright =[],gap=1,maxgap=len-1,gapArr=[],glen,n; while(gapmaxgap){ gap = Math.pow(2,n); if(gap=maxgap){ gapArr.push(gap); } n++; } glen = gapArr.length; for (var i = 0; i glen; i++) { gap = gapArr[i]; for (var j = 0; j len; j=j+gap*2) { arrleft = arr.slice(j, j+gap); arrright = arr.slice(j+gap,j+gap*2); console.log("left:"+arrleft,"right:"+arrright); arr = arr.slice(0,j).concat(subSort(arrleft,arrright),arr.slice(j+gap*2)); } } return arr; }
排序[4,2,6,3,1,9,5,7,8,0]输出：
left:4 right:2 left:6 right:3 left:1 right:9 left:5 right:7 left:8 right:0 left:2,4 right:3,6 left:1,9 right:5,7 left:0,8 right: left:2,3,4,6 right:1,5,7,9 left:0,8 right: left:1,2,3,4,5,6,7,9 right:0,8
看出来从最小的单位入手。
第一轮先依次合并相邻元素：4,2; 6,3; 1,9; 5,7; 8,0
合并完成之后变成： [2,4,3,6,1,9,5,7,0,8]
第二轮以2个元素为一个单位进行合并：[2,4],[3,6]; [1,9],[5,7]; [0,8],[];
合并完成之后变成：[2,3,4,6,1,5,7,9,0,8]
第三轮以4个元素为一个单位进行合并：[2,3,4,6],[1,5,7,9]; [0,8],[]
合并完成之后变成： [1,2,3,4,5,6,7,9,0,8];
第四轮以8个元素为一个单位进行合并： [1,2,3,4,5,6,7,9],[0,8];
合并完成。 [0,1,2,3,4,5,6,7,8,9];
Java 合并排序 求程序
百度文库找了一个
四、合并排序 1、基本思想
合并排序的基本操作是：首先将待排序序列划分为两个长度相等的子序列；然后分别对两个子序列进行归并排序，得到两个有序的子序列；最后将两个有序的子序列合并成一个有序数列。
MergeSort(A[2*n]) {
divide A[2*n] into A[1,……,n],A[n-1,……,2*n];//划分 MergeSort(A[1,……,n]);//归并排序前半个子序列
MergeSort(A[[n-1,……,2*n]);//归并排序后半个子序列 Merge;//合并 }
2、算法复杂度分析
合并步的时间复杂度为O(n)。合并排序算法的时间复杂度为O(nlog2n)。
3、编程实现
public int[] MergeSort(int[] A, int[] tempA, int s, int t){
//如果序列中有一个以上的元素，即st则进行排序
if(s t){
int center = (s + t) / 2;
MergeSort(A, tempA, s, center)
;//归并排序前半个子序列
MergeSort(A, tempA, center + 1, t);
//归并排序后半个子序列
Merge(A,tempA, s, center, t);
//合并
}
return tempA;
}
public int[] Merge(int[] A, int[] tempA, int s, int m, int t){ int n = t- s + 1;
//n为数据总个数
int i=s;j=m+1;k=s
while(i = m j = t){
//取A[i]和A[j]中较小者放入tempA[k]
if(A[i]=A[j]){
tempA[k++] = A[i++]; }
else{
tempA[k++] = A[j++]; } }
if(i=m) while(i=m)
tempA[k++]=A[i++];//处理前一个子序列
else while(j=t)
tempA[k++]=A[j++];//处理后一个子序列
return tempA;
}
java 编写一个程序,输入3个整数,然后程序将对这三个整数按照从大到小进行排列
可以实现比较器Comparator来定制排序方案，同时使用Colletions.sort的方式进行排序，代码如下：
public void sortDesc(ListLong s){
Collections.sort(s, new ComparatorLong() {
public int compare(Long o1, Long o2) {
Long result = o2 - o1;
return result.intValue();
}
});
s.forEach(item-{
System.out.print(item +" ");
});
}
同时常用的比较排序算法主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
java的冒泡排序实现如下：
public?static?void?bubbleSort(int?[]arr)?{????????for(int?i?=0;iarr.length-1;i++)?{????????????for(int?j=0;jarr.length-i-1;j++)?{//-1为了防止溢出????????????????if(arr[j]arr[j+1])?{????????????????????int?temp?=?arr[j];?????????????????????????????????????????arr[j]=arr[j+1];?????????????????????????????????????????arr[j+1]=temp;????????????}????????????}????????????}????}
还有非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
JAVA中有哪几种常用的排序方法？每个排序方法的实现思路是如何的？每个方法的思想是什么？？
一、冒泡排序
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较 a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对 a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定；
缺点：慢，每次只能移动相邻两个数据。
二、选择排序
冒泡排序的改进版。
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n- 1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
优点：移动数据的次数已知（n-1次）；
缺点：比较次数多。
三、插入排序
已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、 b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来 a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
三、缩小增量排序
由希尔在1959年提出，又称希尔排序(shell排序)。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(dn)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、 a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'd，重复上述操作，直到d=1。
优点：快，数据移动少；
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
四、快速排序
快速排序是目前已知的最快的排序方法。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据 a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据a[x]，a[k+1]~a[n]中的每一个数据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。
五、箱排序
已知一组无序正整数数据a[1]、a[2]、……a[n]，需将其按升序排列。首先定义一个数组x[m],且m=a[1]、a[2]、……a[n]，接着循环n次，每次x[a]++.
优点：快，效率达到O(1)
缺点：数据范围必须为正整数并且比较小
六、归并排序
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
java十大算法
算法一：快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
1 从数列中挑出一个元素，称为 "基准"（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
算法二：堆排序算法
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1
算法三：归并排序
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素