归并排序

编辑：见识网互动百科时间：2019-11-29 14:22:32

同义词归并排序算法一般指归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

中文名: 归并排序
外文名: Merge sort
稳定性: 稳定

时间复杂度: O(n log n)
空间复杂度: O（n)
发明者: 约翰·冯·诺伊曼

归并排序归并操作

编辑

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

归并排序算法描述

编辑

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

归并排序比较

编辑

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

归并排序用途

编辑

归并排序排序

（速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列，应用见2011年普及复赛第3题“瑞士轮”的标程）

归并排序求逆序对数

具体思路是，在归并的过程中计算每个小区间的逆序对数，进而计算出大区间的逆序对数（也可以用树状数组来求解）

scala代码：

objectMainextendsApp{
    varreverse_pairs = 0//逆序数
    defmsort[T](cmp:(T, T) => Boolean)(l:List[T]):List[T] = {
        defmerge(l1:List[T], l2:List[T]):List[T]=(l1, l2)match{
            case(Nil, _) => l2
            case(_, Nil) => l1
            case(x::left1, y::left2) =>
                if(cmp(x, y))
                    x::merge(left1, l2)
                else{
                    reverse_pairs += l1.length
                    y::merge(l1, left2)
                }
        }
        valn = l.length / 2
        if(n == 0)
            return l
        else{
            val(l1, l2) = l.splitAt(n)
            merge(msort(cmp)(l1), msort(cmp)(l2))
        }
    }
    println(msort((x:Int, y:Int) => x

归并排序示例代码

编辑

归并排序原理

归并排序具体工作原理如下（假设序列共有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;
    /**
    　*　    　*　二路归并
    　*　原理：将两个有序表合并和一个有序表
    　*　
    　*　
    　*　@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<>

C语言

#include 
#include 

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_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]

Basic语言

Sub MergeSort(Array() As Integer, First As Integer, Last As Integer)
Dim mid As Integer = 0
If first

JavaScript语言

使用递归的代码如下。优点是描述算法过程思路清晰，缺点是使用递归，mergeSort()函数频繁地自我调用。长度为n的数组最终会调用mergeSort()函数 2n-1次，这意味着一个长度超过1500的数组会在Firefox上发生栈溢出错误。可以考虑使用迭代来实现同样的功能。

function　merge(left, right){
    var　result=[];
    while(left.length>0 && right.length>0){
        if(left[0]

非递归算法（C++）

#include
#include
#include
#include
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<<>

二路归并

Const
FI='in.txt';
FO='out.txt';
MaxN=10000;
Type
TIndex=Longint;
TDat=Array[0..MaxN]OfTIndex;
Var
N:TIndex;
Dat:TDat;
Tmp:TDat;
ProcedureMerge(L,Mid,R:TIndex);
Var
P1,P2:TIndex;
E1,E2:TIndex;
P:TIndex;
I:TIndex;
Begin
P1:=L;
P2:=Mid+1;
P:=L;
Repeat
If(Dat[P1]<=Dat[P2])Then
Begin
Tmp[P]:=Dat[P1];
Inc(P1);
Inc(P);
End
Else
Begin
Tmp[P]:=Dat[P2];
Inc(P2);
Inc(P);
End;
Until(P1=Mid+1)Or(P2=R+1);
If(P1=Mid+1)Then
Begin
E1:=P2;
E2:=R;
End
Else
Begin
E1:=P1;
E2:=Mid;
End;
ForI:=E1ToE2Do
Begin
Tmp[P]:=Dat[I];
Inc(P);
End;
End;
ProcedureSort(L,R:TIndex);
Var
Mid:TIndex=0;
Begin
Mid:=(L+R)Shr1;
If(L

Delphi归并排序完整源代码例子：

//合并子函数
procedureTForm1.MergePass(vardatas:arrayofInteger;left,mid,
right:Integer);
var
tmpArr:arrayofInteger;
arrLen:Integer;
i,k:Integer;
begin1,begin2,end1,end2:Integer;
begin
arrLen:=right-left+1;
SetLength(tmpArr,arrLen);
begin1:=left;
end1:=mid;
begin2:=mid+1;
end2:=right;
k:=0;
while((begin1<=end1)and(begin2<=end2))do
begin
if(datas[begin1]'+getArrayString(datas));//显示数组中间状态
end;
end;
//调用方法：procedureTForm1.btn1Click(Sender:TObject);
var
inArr:array[0..9]ofInteger;
begin
CopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);
showLog('输入数据：'+getArrayString(inArr));
MergeSort(inArr,0,High(inArr));
showLog('输出数据：'+getArrayString(inArr));
end;

归并排序复杂度

编辑

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。

空间复杂度为 O(n)

比较操作的次数介于(nlogn) / 2和nlogn - n + 1。

赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)

归并排序比较占用内存，但却是一种效率高且稳定的算法。

归并排序归并算法

编辑

定义

所谓归并排序是指将两个或两个以上有序的数列（或有序表），合并成一个仍然有序的数列（或有序表）。这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。归并排序的算法比较简单。

基本思想方法：

（1）假设已经有两个有序数列，分别存放在两个数组s，r中；并设i，j分别为指向数组的第一个单元的下标；s有n个元素，r有m个元素。

（2）再另设一个数组a，k指向该数组的第一个单元下标。

（3）算法分析（过程）：

proceduremerge(s,r,a,i,j,k);
begin
i1:=i;
j1:=j;
k1:=k;
while(i1<>

完整的C++源代码

#include
voidMerge(intr[],intr1[],ints,intm,intt){
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t){
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
if(i<=m)
while(i<=m)
r1[k++]=r[i++];
else
while(j<=t)
r1[k++]=r[j++];
for(intn=s;n<=t;n++)
r[n]=r1[n];
}

voidMergeSort(intr[],intr1[],ints,intt){
if(s

归并排序的实现方法：

1.自底向上算法

#include
#include
voidMerge(int*a,intlow,intmid,inthigh){
inti=low,j=mid+1,k=0;
int*temp=(int*)malloc((high-low+1)*sizeof(int));
while(i<=mid&&j<=high)
a[i]<=a[j]?(temp[k++]=a[i++]):(temp[k++]=a[j++]);
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
memcpy(a+low,temp,(high-low+1)*sizeof(int));
free(temp);
}
voidMergeSort(int*a,intn){
intlength;
for(length=1;length>n;
int*data=new
int[n];
if(!data)
exit(1);
intk=n;
while(k--){
cin>>data[n-k-1];
}
clock_ts=clock();
MergeSort(data,n);
clock_te=clock();
k=n;
while(k--){
cout<<>

2.自顶向下

voidMerge(intr[],intr1[],ints,intm,intt){
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t){
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
while(i<=m)
r1[k++]=r[i++];
while(j<=t)
r1[k++]=r[j++];
for(intl=0;l<8;l++)
r[l]=r1[l];
}

voidMergeSort(intr[],intr1[],ints,intt){
if(s==t)
;
else{
intm=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}

词条标签：

，，，