归并排序的示例代码

归并排序的示例代码,第1张

归并排序原理

归并排序具体工作原理如下(假设序列共有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 algorithmpublic 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 l<len(left) and r<len(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.h>void 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 i<8 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_1const maxn=7type arr=array[1..maxn] of integervar a,b,c:arri:integerprocedure merge(r:arrl,m,n:integervarr2:arr)var i,j,k,p:integerbegin 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] endendprocedure mergesort(var r,r1:arrs,t:integer)var k:integerc:arrbegin 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) endendbegin 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) writelnend.//============================================program mergesort_2const max=100000var a,r:array[1..max] of long intn,i:long intprocedure msort(s,t:longint)var m,i,j,k:long intbegin 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]endbegin 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 first<last 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.length>0 && right.length>0){        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++) #include<iostream>#include<ctime>#include<cstring>#include<cstdlib>using 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 cin>>n int* data = new int[n] if(!data) exit(1) int k = n while(k--){     cin>>data[n-k-1] } clock_t s = clock() MergeSort(data, n) clock_t e = clock() k=n while(k--){     cout<<data[n-k-1]<<' ' } cout<<endl cout<<the algorithm used<<e-s<<miliseconds.<<endl delete data return 0}二路归并

ConstFI='in.txt'FO='out.txt'MaxN=10000TypeTIndex=LongintTDat=Array[0..MaxN]OfTIndexVarN:TIndexDat:TDatTmp:TDatProcedureMerge(L,Mid,R:TIndex)VarP1,P2:TIndexE1,E2:TIndexP:TIndexI:TIndexBeginP1:=LP2:=Mid+1P:=LRepeatIf(Dat[P1]<=Dat[P2])ThenBeginTmp[P]:=Dat[P1]Inc(P1)Inc(P)EndElseBeginTmp[P]:=Dat[P2]Inc(P2)Inc(P)EndUntil(P1=Mid+1)Or(P2=R+1)If(P1=Mid+1)ThenBeginE1:=P2E2:=REndElseBeginE1:=P1E2:=MidEndForI:=E1ToE2DoBeginTmp[P]:=Dat[I]Inc(P)EndEndProcedureSort(L,R:TIndex)VarMid:TIndex=0BeginMid:=(L+R)Shr1If(L<Mid)ThenSort(L,Mid)If(Mid+1<R)ThenSort(Mid+1,R)Merge(L,Mid,R)ForMid:=LToRDoDat[Mid]:=Tmp[Mid]EndProcedureInitVarI:TIndexBeginFillChar(Dat,SizeOf(Dat),0)Readln(N)ForI:=1ToNDoRead(Dat[I])EndProcedureMainBeginSort(1,N)EndProcedureFinalVarI:TIndexBeginForI:=1ToNDoWrite(Dat[I],'')WritelnEndBeginAssign(Input,FI)Assign(Output,FO)Reset(Input)Rewrite(Output)InitMainFinalClose(Input)Close(Output)End.

Delphi归并排序完整源代码例子: //合并子函数procedureTForm1.MergePass(vardatas:arrayofIntegerleft,mid,right:Integer)vartmpArr:arrayofIntegerarrLen:Integeri,k:Integerbegin1,begin2,end1,end2:IntegerbeginarrLen:=right-left+1SetLength(tmpArr,arrLen)begin1:=leftend1:=midbegin2:=mid+1end2:=rightk:=0while((begin1<=end1)and(begin2<=end2))dobeginif(datas[begin1]<datas[begin2])thenbegintmpArr[k]:=datas[begin1]Inc(begin1)endelsebegintmpArr[k]:=datas[begin2]Inc(begin2)endinc(k)endwhile(begin1<=end1)dobegintmpArr[k]:=datas[begin1]Inc(begin1)Inc(k)endwhile(begin2<=end2)dobegintmpArr[k]:=datas[begin2]Inc(begin2)Inc(k)endfori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i]endend//排序主函数,left是数组左下标,0开始。right是数组右下标。procedureTForm1.MergeSort(vardatas:arrayofIntegerleft,right:Integer)varmid:Integeri:Integerbeginmid:=0if(left<right)thenbeginmid:=(right+left)div2showLog('中间索引:'+inttostr(mid))MergeSort(datas,left,mid)MergeSort(datas,mid+1,right)MergePass(datas,left,mid,right)showLog('--->'+getArrayString(datas))//显示数组中间状态endend//调用方法:procedureTForm1.btn1Click(Sender:TObject)varinArr:array[0..9]ofIntegerbeginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10)showLog('输入数据:'+getArrayString(inArr))MergeSort(inArr,0,High(inArr))showLog('输出数据:'+getArrayString(inArr))end

/**设个有序关键字表s1=(18,25,37,42),s2=(20,33,40).同时将s1,s2存储在数组r[1...7]中

**s1放r[1..4],s2放[5..7],现要归并到一维数组r2[1..7]中,只要依次比较这两个有序

**表中相应记录关键字,按吵乎取小原则复制到r2中

**/

#include<stdio.h>

#define MAXITEM 100

typedef struct rec

{

int key

char data[20]

}elemnode[MAXITEM]

void merge(elemnode r,elemnode r1,int l,int m,int h)

{ // i,j是r的指示器,i的取值从l到m, j的取值从m+1到h,k是r1的指示器

int i = l,j = m+1,k = l

while(i<=m &&j<=h)

{

if(r[i].key<=r[j].key)

{

r1[k] = r[i]

i++

}

else

{

r1[k] = r[j]j++

}

k++

}

if(i>m)

while(j<=h)

{

r1[k] = r[j]

j++

k++

}

else

while(i<=m)

{

r1[k] = r[i]

i++

k++

}

}

void mergepass(elemnode r,elemnode r1,int n,int l)

{

//将r中长度为L的两个部分合并,第一派肆部分从p到期(p+l-1)

//第二部分从 p+1到(p+2*l-1)

int p = 1

while(n-p+1>2*l)

{

merge(r,r1,p,p+l-1,p+2*l-1)

p+=2*l //p向后移动2*l,准备下一次合并

}

if(n-p+1>l)//一个长度为l的部分与一个长度小于l的部分合并

merge(r,r1,p,p+l-1,n)

else //只剩下一个长度不大于l的部分,将其复制到r1

for(p<=np++) r1[p] = r[p]

}

void mergesort(elemnode r,elemnode r1,int n)

{//对r中数据元素进行归并,结果仍放在r 中升羡悉

int l = 1

while(l<n)

{

mergepass(r,r1,n,l)l*=2

mergepass(r1,r,n,l)l*=2

}

}

void disp(elemnode r,int n)

{

int i

for(i=1i<=ni++)

printf("%6d",r[i].key)

printf("\n")

for(i=1i<=ni++)

printf("%6s",r[i].data)

printf("\n")

}

void main()

{

elemnode s = {{0," "},{75,"王华"},{87,"李英"},{68,"张萍"},{92,"陈涛"},{88,"刘丽"},{61,"章强"},

{77,"孙军"},{96,"朱斌"},{80,"许伟"},{72,"曾亚"}}

elemnode s1

int n = 10

mergesort(s,s1,n)

disp(s,n)

}

这个不难:

#include<stdio.h>

// 一个递归函数

void mergesort(int *num,int start,int end)

// 这个函数用来将两个排好序的数组进行合并

void merge(int *num,int start,int middle,int end)

int main()

{

// 测试数组

int num[10]= {12,54,23,67,86,45,97,32,14,65}

int i

// 排序之前

printf("Before sorting:\n")

for (i=0i<10i++)

{

printf("%3d",num[i])

}

printf("\n")

// 进行合并排序

mergesort(num,0,9)

printf("After sorting:\n")

// 排序之后

for (i=0i<10i++)

{

printf("%3d",num[i])

}

printf("\n")

return 0

}

//这个函数用来将问题细分

void mergesort(int *num,int start,int end)

{

int middle

if(start<end)

{

middle=(start+end)/尺判2

// 归并的基本思想

// 排左边团困铅

mergesort(num,start,middle)

// 排右边

mergesort(num,middle+1,end)

// 合并

merge(num,start,middle,end)

}

}

//这个函数用于将两个塌好已排好序的子序列合并

void merge(int *num,int start,int middle,int end)

{

int n1=middle-start+1

int n2=end-middle

// 动态分配内存,声明两个数组容纳左右两边的数组

int *L=new int[n1+1]

int *R=new int[n2+1]

int i,j=0,k

//将新建的两个数组赋值

for (i=0i<n1i++)

{

*(L+i)=*(num+start+i)

}

// 哨兵元素

*(L+n1)=1000000

for (i=0i<n2i++)

{

*(R+i)=*(num+middle+i+1)

}

*(R+n2)=1000000

i=0

// 进行合并

for (k=startk<=endk++)

{

if(L[i]<=R[j])

{

num[k]=L[i]

i++

}

else

{

num[k]=R[j]

j++

}

}

delete [] L

delete [] R

}


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/12303906.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-24
下一篇 2023-05-24

发表评论

登录后才能评论

评论列表(0条)

保存