天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

归并排序算法及其实现代码详解

Posted on 2012-11-25 21:23 hoshelly 阅读(3712) 评论(0)  编辑 收藏 引用 所属分类: DS && Algorithm

归并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
例如,有数列{6,202,100,301,38,8,1}
1.  刚开始的分组如下:
  i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 比较次数为3次
 2. 第二次,两两分组合并
  i=2 [ 6 100 202 301 ] [ 1 8 38 ] 比较次数为4
3.  第三次,继续合并
  i=3 [ 1 6 8 38 100 202 301 ] 比较次数为4
总计的比较次数为11次
归并排序具体工作原理如下(假设序列共有n个元素):
1.     将序列每相邻两个数字进行归并操作,形成floor(n / 2)个序列,排序后每个序列包含两个元素
2.     将上述序列再次归并,形成floor(n / 4)个序列,每个序列包含四个元素
3.     重复步骤2,直到所有元素排序完毕
     归并操作的过程如下:
1.     申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2.     设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.     比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.     重复步骤3直到某一指针达到序列尾
5.     将另一序列剩下的所有元素直接复制到合并序列尾

自底向上归并,如图所示:



递归实现代码:

#include <iostream>
 
 using namespace std;
 
 void merge(int*arr, int p, int q, int r)
 {
     int n1 = q - p + 1;
     int n2 = r - q;
 
     int* L = new int[n1];
     int* R = new int[n2];
 
     for(int i = 0; i < n1; i++)
     {
         L[i] = arr[p + i];
     }
     for(int j = 0; j < n2; j++)
     {
         R[j] = arr[q + j + 1];
     }
 
     int i = 0;
     int j = 0;
     int k = p;
 
     while((i < n1) && (j < n2))
     {
         if(L[i] <= R[j])
         {
             arr[k] = L[i];
             i++;
         }
         else
         {
             arr[k] = R[j];
             j++;
         }
         k++;
     }
 
     if (i < n1)
     {
         for(; i < n1; i++, k++)
         {
             arr[k] = L[i];
         }
     }
     if (j < n2)
     {
         for(; j < n2; j++, k++)
         {
             arr[k] = R[j];
         }
     }
 }
 
 void mergesort(int* arr, int p, int r)
 {
     int q = 0;
     if(p < r)
     {
         q = (p + r) / 2;
         mergesort(arr, p, q);
         mergesort(arr, q + 1, r);
         merge(arr, p, q, r);
     }
 }
 
 int main()
 {
     int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
     mergesort(a, 0, 7);
     for(int i = 0; i < 8; i++)
     {
         cout << a[i] << " ";
     }
     cout << endl;
     return 0;
 }

非递归代码实现:

/**
  * merge_sort: 非递归实现 --迭代
  * 非递归思想: 将数组中的相邻元素两两配对。用merge函数将他们排序,
  * 构成n/2组长度为2的排序好的子数组段,然后再将他们排序成长度为4的子数组段,
  * 如此继续下去,直至整个数组排好序。
 *
*/

 #include <stdio.h>
 #include <stdlib.h>

 // merge_sort(): 非递归实现-自底向上
 
// 将原数组划分为left[minmax] 和 right[minmax]两部分
 void merge_sort(int *list, int length)
 {
     int i, left_min, left_max, right_min, right_max, next;
     int *tmp = (int*)malloc(sizeof(int) * length);

     if (tmp == NULL)
     {
         fputs("Error: out of memory\n", stderr);
         abort();
     }

     for (i = 1; i < length; i *= 2) // i为步长,1,2,4,8……
     {
         for (left_min = 0; left_min < length - i; left_min = right_max)
         {
             right_min = left_max = left_min + i; //right_min取left_max的值,以下要用到left_max的值才不会改变left_max原先值
             right_max = left_max + i;

             if (right_max > length) //如果right_max超出了数组长度,则right_max等于数组长度
                 right_max = length;

             next = 0;
             while (left_min < left_max && right_min < right_max) //tmp[next]存储子数组中的最小值
                 tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];

             while (left_min < left_max)  //如果left_min小于left_max,则将最小值原封不动地赋给list[--right_min],right_min 要先减1
                 list[--right_min] = list[--left_max];

             while (next > 0) //将tmp[next]存储的最小值放入list[--right_min]中
                 list[--right_min] = tmp[--next];
         }
         if(i == 1) //打印第一次归并后的数字排列
         {
             for(int j=0;j<length;j++)
               printf("%d ",list[j]);
             printf("\n");
         }
     }

     free(tmp);

 }


 int main()
 {
     int a[1000],t,i;
     scanf("%d",&t);
     for(i=0;i<t;i++)
     {
         scanf("%d",&a[i]);
     }
     merge_sort(a, t);

     // print array
     for (i = 0; i < t; i++)
         printf("%d ", a[i]);

     return 0;
 }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理