来自当知百科
跳转到: 导航搜索

目录

归并排序

  归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

  将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

归并操作

  归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。

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

  初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数

  i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3

  i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4

  i=3 [ 1 6 8 38 100 202 301 ] 4

  总计: 11次

算法描述

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

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

  设定两个指针,最初位置分别为两个已经排序序列的起始位置

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

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

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

复杂度

  时间O(nlogn)

  空间O(n)

  与快速排序类似。

与快速排序的比较

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

用途

  1、排序(速度仅次于快速排序,但较稳定)

  2、求逆序对

示例代码

  归并排序

  归并排序具体工作原理如下(假设序列共有n个元素):

  将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素

  将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素

  重复步骤2,直到所有元素排序完毕

  示例代码

  示例代码为C语言,输入参数中,需要排序的数组为array[],起始索引为first,终止索引为last。调用完成后,array[]中从first到last处于升序排列。

  void MergeSort(int array[], int first, int last)

  {

  int mid = 0;

  if(first<last)

  {

  mid = (first+last)/2;

  MergeSort(array, first, mid);

  MergeSort(array, mid+1,last);

  Merge(array,first,mid,last);

  }

  }

  以下示例代码实现了归并操作。array[]是元素序列,其中从索引p开始到q位置,按照升序排列,同时,从(q+1)到r也已经按照升序排列,merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。

  /**

  * 0 <= p <= q < r, subarray array[p..q] andarray[q+1..r] are already sorted.

  * the merge() function merges the two sub-arrays into one sortedarray.

  */

  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)

  {

  temp[k++] = array[begin1++];

  }

  while(begin2<=end2)

  {

  temp[k++] = array[begin2++];

  }

  for (i = 0; i < (r - p + 1); i++)

  array[p+i] = temp[i];

  free(temp);

  }

  非递归算法(C++):

  #include <iostream> #include <ctime> #include<cstring> 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 = newint[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(data+a+i+j, data+a+i, (length-i)*sizeof(int)); }memcpy(data+a, temp, (i+j)*sizeof(int)); delete temp; } voidMergeSort(int* data, int n){ int step = 1; while(step < n){for(int i = 0; i <= n-step-1; i += 2*step){ //将i和i+step这两个有序序列进行合并 // 序列长度为step // 当i以后的长度小于或者等于step时,退出Merge(data, i, i+step, step, n); } step *= 2; } } int main(){ intn; 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 algrothem used " << e-s << "miliseconds." << endl; delete data; return 0; }

  二路归并排序 Pascal/Dephi 源代码:

  Const

  FI = 'in.txt' ;

  FO = 'out.txt' ;

  MaxN = 10000 ;

  Type

  TIndex = Longint ;

  TDat = Array [ 0 .. MaxN ] Of TIndex ;

  Var

  N : TIndex ;

  Dat : TDat ;

  Tmp : TDat ;

  Procedure Merge ( 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 ;

  For I := E1 To E2 Do

  Begin

  Tmp [ P ] := Dat [ I ] ;

  Inc ( P ) ;

  End ;

  End ;

  Procedure Sort ( L , R : TIndex ) ;

  Var

  Mid : TIndex = 0 ;

  Begin

  Mid := ( L + R ) Shr 1 ;

  If ( L < Mid ) Then

  Sort ( L , Mid ) ;

  If ( Mid + 1 < R ) Then

  Sort ( Mid + 1 , R ) ;

  Merge ( L , Mid , R ) ;

  For Mid := L To R Do

  Dat [ Mid ] := Tmp [ Mid ] ;

  End ;

  Procedure Init ;

  Var

  I : TIndex ;

  Begin

  FillChar ( Dat , SizeOf ( Dat ) , 0 ) ;

  Readln ( N ) ;

  For I := 1 To N Do

  Read ( Dat [ I ] ) ;

  End ;

  Procedure Main ;

  Begin

  Sort ( 1 , N ) ;

  End ;

  Procedure Final ;

  Var

  I : TIndex ;

  Begin

  For I := 1 To N Do

  Write ( Dat [ I ] , ' ' ) ;

  Writeln ;

  End ;

  Begin

  Assign ( Input , FI ) ;

  Assign ( Output , FO ) ;

  Reset ( Input ) ;

  Rewrite ( Output ) ;

  Init ;

  Main ;

  Final ;

  Close ( Input ) ;

  Close ( Output ) ;

  End .

  算法复杂度

  比较操作的次数介于(nlogn) / 2和nlogn - n + 1。赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:Θ (n)

  Pascal中的归并算法

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

  基本思想方法是:

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

  (2)再另设一个数组a,k指向该数组的第一个单元下标。

  (3)算法分析(过程):

  procedure merge(s,r,a,i,j,k);

  begin

  i1:=i;

  j1:=j;

  k1:=k;

  while (i1<n) and (j1<m) do

  if s[i1]<=r[j1] then

  begin

  a[k]:=s[i1];

  i1:=i1+1;

  k:=k+1;

  end

  else

  begin

  a[k]:=r[j1];

  j1:=j1+1;

  k:=k+1;

  end;

  while j1<=m do

  begin

  a[k]:=r[j1];

  j1:=j1+1;

  k:=k+1;

  end;

  end;

  完整的C++源代码

  #include<iostream.h>

  void Merge(int r[],int r1[],int s,int m,int t)

  {

  int i=s;int j=m+1;int k=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(int l=0;l<8;l++)

  r[l]=r1[l];

  }

  void MergeSort(int r[],int r1[],int s,int t)

  {

  if(s==t)r1[s]=r[s];

  else

  {

  int m=(s+t)/2;

  MergeSort(r,r1,s,m);

  MergeSort(r,r1,m+1,t);

  Merge(r1,r,s,m,t);

  }

  }

  void main()

  {

  int r[8]={10,3,5,1,9,34,54,565},r1[8];

  MergeSort(r,r1,0,7);

  for(int q=0;q<8;q++)

  cout<<" "<<r[q];

  }

个人工具
名字空间

变换
查看
操作
导航
工具箱