您的位置:

php归并排序,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

这样的话两次调用其实也就是把整个数组先拆分成两部分,然后这两部分各自做排序,之后再合并

递归处理,如果对代码逻辑不能直接理解的话,可以考虑从实际数据着手来理解

比如假设数组中只有一个数,程序会怎样执行,假设数组中只有两个数,程序会怎样执行。。。