大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > C++归并排序算法

C++归并排序算法

关键词:C++归并算法排序算法  阅读(955) 赞(13)

[摘要]本文是对C++归并排序算法的讲解,对学习C++编程技术有所帮助,与大家分享。

归并排序完全遵循分治模式,主要操作分为三步:

1.分解:分解待排序的n个元素序列为2个n/2个元素的子序列。

2.解决:使用归并排序递归的排序两个子序列。

3.合并:合并两个已排序的子序列。

最重要的步骤就是合并2个已经排序的序列。例如:A和B都是从小到大排序的序列。依次对比A的第一个元素和B的第一个元素,把其中较小的元素出序列,插入到C中,直到两个序列中的元素都为空。最后,C序列就是一个包含A序列和B序列且从小到排序的序列。

伪码:

 Merge(A,p,q,r)
      n1 = q - p + 1
      n2 = r - q
      let L[1..n1 + 1]  and R[1.. n2 + 1] be new arrays
      for i = 1 to n1
           L[i] = A[p + i - 1]
      for j = 1 to n2
           R[i] = A[q + j]
     L[n1 + 1] = ∞
     R[n2 + 1] = ∞
     i = 1
     j = 1
    for k = p to r
        if L[i] <= R[j] 
            A[k] = L[i]
            i = i + 1
         else
            A[k] = R[i]
            j = j + 1

上述伪码中,其中A为待排序的数组,且A[p..q ]和A[q + 1..r]都是排序好的。9,10行中,在L,R最后插入一个值,作为哨兵值,每当出现哨兵值时,它不可能为较小的值,这样可以简化代码,避免检查L或R为空。

图例:

最后我们使用Merge_sort 排序数组A[p...r]中的元素。若p >= r,时,数组中最多只有一个元素,所以是排序好的,程序结束;否则,分解数组A[p...r]为两个子数组A[p...q]和A[q + 1...r],然后合并2个子数组。

伪码:

 Merge_sort(A,p,r)
    if p < r
            q = ⌊(p + r) / 2⌋
            Merge_sort(A,p,q)
            Merge_sort(A,q + 1,r)
            Merge(A,p,q,r)

图例:

归并排序的时间复杂度:T(n) = O(nlgn)

C++代码:

 void Merge(int a[],int p,int q,int r)
 {
     int n1 = q - p + 1;
     int n2 = r - q;
 
     int *L = new int[n1],*R = new int [n2];
     for(int i = 0;i < n1;i++)
     {
         L[i] = a[p + i];
     }
     for(int i = 0;i < n2;i++)
     {
         R[i] = a[q + i + 1];
     }
 
     for(int k = p,iL = 0,iR = 0; k <= r;k++)
     {
         if(iL != n1 && iR == n2)
             a[k] = *L++;
         if(iR != n2 && iL == n1)
             a[k] = *R++;
 
         if(iL != n1 && iR != n2)
         {        
             if(*L < *R)
             {
                 a[k] = *L;
                 L++;
                 iL++;
             }
             else
             {
                 a[k] = *R;
                 R++;
                 iR++;
             }
         }
     }
     delete[] (L - n1);
     delete[] (R - n2);
 }
 
 //合并排序,T(n) = O(nlgn)
 void Merge_sort(int a[],int p,int r)
 {
     if(p < r)
     {
         int q = (p + r) / 2;
         Merge_sort(a,p,q);
         Merge_sort(a,q + 1,r);
         Merge(a,p,q,r);
     }
 }


相关评论