php歸併排序,php 數組排序函數

本文目錄一覽：

• 1、歸併排序的示例代碼
• 2、常見算法4、合併(歸併)排序 Merge sort
• 3、php 歸併排序，，對於兩次遞歸調用自身有點不理解，求大神指教，不太明白執行過程

歸併排序的示例代碼

歸併排序原理

歸併排序具體工作原理如下（假設序列共有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;

常見算法4、合併(歸併)排序 Merge sort

歸併排序，是創建在歸併操作上的一種有效的排序算法。算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

假如如我這裡有一組數據，歸併排序過程如下：

通俗點來說，就是先分割，再合併。分割的過程中其實可理解為就是以二分法將數組分割成最小單元，然後再按順序合併起來。

1、Python 3 ：

2、PHP：

php 歸併排序，，對於兩次遞歸調用自身有點不理解，求大神指教，不太明白執行過程

可以考慮把變量名修改一下

$l = $start

$m = $mid

$r = $end

這樣的話兩次調用其實也就是把整個數組先拆分成兩部分，然後這兩部分各自做排序，之後再合併

遞歸處理，如果對代碼邏輯不能直接理解的話，可以考慮從實際數據着手來理解

比如假設數組中只有一個數，程序會怎樣執行，假設數組中只有兩個數，程序會怎樣執行。。。