首页 > 代码库 > 算法之合并排序

算法之合并排序

2024-07-22 13:01:51   223人阅读

    上篇文章讲到插入排序算法，是一个标准的增量方法：在排好的子数组后，将元素插入，形成新的数组。今天要介绍的是一种新方法：分治法。

 
    分治法，将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就能得到原问题的解。在每一层递归上都会有三个步骤：
  • 分解：将原问题分解成一系列子问题；
  • 解决：递归地解决各子问题，若子问题足够小，则直接求解；
  • 合并：将子问题的结果合并成原问题的解。
 
    合并排序算法完全依照了上述模式，直观的操作如下：
  • 分解：将n个元素分成各含n/2个元素的子序列
  • 解决：用合并排序法将两个子序列递归的排序
  • 合并：合并两个已排序的子序列以得到排序结果
    对于子序列排序时，其长度为1时，递归结束。当个元素视为已排好序。
 
    合并过程伪代码：
    
merge(A, p, q, r)    n1=q-p+1    n2=r-q    L R = []    for i=1->n1        L[i]=A[p+i-1]    for j=1>n2        R[j]=A[q+j]    L[n1+1]=Infinity    R[n2+1]=Infinity    for k=p->r        if L[i]<=R[i]            A[k]=L[i]            i++        else            A[k]=R[j]            j++

　　

 
    合并排序伪代码：
    
mergeSort(A, p, r)    if p < r        q = parseInt((p+r)/2)        mergeSort(A, p, q)        mergeSort(A,q+1,r)        merge(A,p,q,r);

　　

 
    js实现实例为：
   
 var ARR = [5,2,4,7,1,3,2,6]; function merge(arr, p, q, r) {  var n1 = q - p + 1;  var n2 = r - q;  var L = [];  var R = [];  for(var i = 1; i <= n1; i++) {   L[i] = arr[p+i-1];  }  for(var j = 1; j <= n2; j++) {   R[j] = arr[q+j];  }  L[n1 + 1] = Infinity;  R[n2 + 1] = Infinity;  i = j = 1;  for(var k = p; k <= r; k++) {   if(L[i] <= R[j]) {    arr[k] = L[i];    i++;   }else {    arr[k] = R[j];    j++;   }  }  return arr; }  function mergeSort(arr, p, r) {  if(p < r) {   var q = Math.floor((p+r)/2);   mergeSort(arr, p, q);   mergeSort(arr, q+1, r);   return merge(arr, p, q, r);  } }  console.log(mergeSort(ARR, 0, ARR.length-1));

　　

 
    合并的过程如下所示：
    
 
 
参考资料：《算法导论》
    

算法之合并排序


联系
我们