Chinaunix首页 | 论坛 | 博客
  • 博客访问: 144609
  • 博文数量: 66
  • 博客积分: 1571
  • 博客等级: 上尉
  • 技术积分: 715
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-24 22:55
文章分类

全部博文(66)

文章存档

2012年(66)

我的朋友

分类:

2012-07-18 16:22:21

原文地址:归并排序 作者:onezeroone


  1. #include <stdio.h>
  2. #include <limits.h>

  3. void merge(int *A, int start, int mid, int end);
  4. void mergeSort(int *A, int start, int end);
  5. void myPrint(int *A, int len);

  6. int
  7. main(void)
  8. {
  9.         int a[] = {1,3,5,7,9,0,2,4,6,8,0};
  10.         int len = sizeof(a)/sizeof(a[0]);

  11.         myPrint(a, len);
  12.         mergeSort(a, 0, len-1);
  13.         myPrint(a, len);

  14.         return (0);
  15. }

  16. void
  17. myPrint(int *A, int len)
  18. {
  19.         printf("Enter: ");
  20.         int i = 0;
  21.         for (i = 0; i < len; i++) {
  22.                 printf("%d,",*(A+i));
  23.         }
  24.         printf("\n");
  25. }

  26. void
  27. merge(int *A, int start, int mid, int end)
  28. {
  29.         int n1, n2;
  30.         n1 = mid - start + 1;
  31.         n2 = end - mid;

  32.         n1++;
  33.         n2++;

  34.         int L[n1], R[n2];

  35.         int i, j, k;
  36.         for (i = 0; i < n1-1; i++) {
  37.                 L[i] = *(A+start+i);
  38.         }
  39.         for (j = 0; j < n2-1; j++) {
  40.                 R[j] = *(A+mid+j+1);
  41.         }

  42.         L[i] = INT_MAX;
  43.         R[j] = INT_MAX;

  44.         i = 0;
  45.         j = 0;

  46.         for (k = start; k <= end; k++) {
  47.                 if (L[i] <= R[j]) {
  48.                         *(A+k) = L[i];
  49.                         i++;
  50.                 } else {
  51.                         *(A+k) = R[j];
  52.                         j++;
  53.                 }
  54.         }
  55. }

  56. void
  57. mergeSort(int *A, int start, int end)
  58. {
  59.         int mid;
  60.         if (start < end) {
  61.                 mid = (start+end)/2;
  62.                 mergeSort(A, start, mid);
  63.                 mergeSort(A, mid+1, end);
  64.                 merge(A, start, mid, end);
  65.         }
  66. }
稳定性:稳定
T(n): O(nlgn)
S(n): O(n)






阅读(687) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~