`
wind_bell
  • 浏览: 291263 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

排序--归并排序

阅读更多

原理:
1、算法基本思路
     设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。

(1)合并过程
     合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。
     重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。

(2)动态申请R1
     实现时,R1是动态申请的,因为申请的空间可能很大,故须加入申请空间是否成功的处理。
实现:

 //将分组a[low]..a[i]和分组a[i + 1]..a[high]合并 
 private static void merge(int[] a, int pivotPos, int low, int high)
 {
  int[] b = new int[a.length];
  int p = low;
  int q = pivotPos + 1;
  int r = low;
  while( p <= pivotPos && q <= high )
  {
   while( p <= pivotPos )
   {
    if( a[p] <= a[q] )
     b[r++] = a[p++];
    else
     break;
   }
   while( q <= high )
   {
    if( a[q] < a[p] )
     b[r++] = a[q++];
    else
     break;
   }
  }
  while( p <= pivotPos )
   b[r++] = a[p++];
  while( q <= high )
   b[r++] = a[q++];

  for( int i = low; i <= high; i++)
   a[i] = b[i];
 }
 
 //归并排序
 //分治策略
 //实践复杂度无论最好、平均都为O(nlogn)
 //空间复杂度:O(n),一个额外的数组
 public static void mergeSort(int[] a, int low, int high)
 {
  if ( low >= high )
   return;
  int pivotPos = (low + high) / 2;
  mergeSort(a, low, pivotPos);
  mergeSort(a, pivotPos + 1, high);
  merge(a, pivotPos, low, high);
 }

复杂度:
最好,最坏,平均都为O(nlogn)

空间复杂度: O(n),因为使用了一个额外的数组

稳定性:归并排序是稳定排序

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics