Chinaunix首页 | 论坛 | 博客
  • 博客访问: 502773
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-09-16 20:17:57

/**
Description

2-归并排序对给出序列进行排序(升序),输出使用2-归并排序时关键字交换次数。


数据输入:

测试文件包含多测试用例, 第个测试用例以N(0 < N < 500,000 )开始, 接着有N个数,
最后一个测试用例为n=0, 不作处理.


数据输出:

对第个测试用例输出一行,仅包含2-归并排序时关键字交换次数.

Sample Input

5
9
1
0
5
4

3
1
2
3

0



Sample Output

6
0

*/


点击(此处)折叠或打开

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


  3. typedef struct node *pNode;

  4. struct node
  5. {
  6.     __int64 data;
  7. };

  8. __int64 mergeSort(pNode source,pNode destination,__int64 begin,__int64 end);
  9. __int64 merge(pNode source,pNode destination,__int64 begin,__int64 mid,__int64 end);
  10. void printArray(pNode destination,__int64 n);

  11. int main()
  12. {
  13.     __int64 n,i,result;//n表示输入的表示待排序的元素个数
  14.     pNode source,destination,pTemp1,pTemp2;

  15.     while(1 == scanf("%I64d",&n) && n != 0)
  16.     {
  17.         source = NULL;
  18.         destination = NULL;

  19.         source = (pNode)malloc(n * sizeof(__int64));
  20.         destination = (pNode)malloc(n * sizeof(__int64));

  21.         if(source == NULL || destination == NULL)
  22.         {
  23.             exit(1);
  24.         }


  25.         for(i=0; i<n; i++)
  26.         {
  27.             scanf("%I64d",&((source+i)->data));
  28.         }

  29.        // printArray(sourceArray,n);
  30.         result = mergeSort(source,destination,0,n-1);

  31.         //printArray(destination,n);
  32.        // printArray(sourceArray,n);
  33.         printf("%I64d\n",result);

  34.         pTemp1 = source;
  35.         pTemp2 = destination;
  36.         free(pTemp1);
  37.         free(pTemp2);
  38.     }

  39.     return 0;
  40. }


  41. __int64 mergeSort(pNode source,pNode destination,__int64 begin,__int64 end)
  42. {
  43.     __int64 mid,temp1 = 0,temp2 = 0,temp3 = 0;
  44.     if(begin == end)
  45.     {
  46.         (destination+begin)->data = (source+end)->data;
  47.     }
  48.     else if(begin < end)
  49.     {
  50.         mid = (begin + end) / 2;
  51.         temp1 = mergeSort(source,destination,begin,mid);
  52.         temp2 = mergeSort(source,destination,mid+1,end);
  53.         temp3 = merge(source,destination,begin,mid,end);
  54.     }

  55.     return temp1 + temp2 + temp3;
  56. }


  57. __int64 merge(pNode source,pNode destination,__int64 begin,__int64 mid,__int64 end)
  58. {
  59.     __int64 i = begin,j = mid + 1,k = begin,count = 0;
  60.     while(i <= mid && j <= end)
  61.     {
  62.         if((source+i)->data <= (source+j)->data)
  63.         {
  64.             (destination+k)->data = (source+i)->data;
  65.             i++;
  66.             k++;
  67.         }
  68.         else
  69.         {
  70.             (destination+k)->data = (source+j)->data;
  71.             //printf("%d,%d\n",sourceArray[i],sourceArray[j-1]);
  72.             count += mid - i + 1;
  73.             j++;
  74.             k++;
  75.         }
  76.     }

  77.     while(i <= mid)
  78.     {
  79.         (destination+k)->data = (source+i)->data;
  80.         i++;
  81.         k++;
  82.     }

  83.     while(j <= end)
  84.     {
  85.         (destination+k)->data = (source+j)->data;
  86.         j++;
  87.         k++;
  88.     }

  89.     i = begin;
  90.     while(i <= end)
  91.     {
  92.         (source+i)->data = (destination+i)->data ;
  93.         i++;
  94.     }

  95.     return count;
  96. }


  97. //打印数组

  98. void printArray(pNode destination,__int64 n)
  99. {
  100.     __int64 i;

  101.     for(i=0; i<n; i++)
  102.     {
  103.         printf("%I64d ",(destination+i)->data);
  104.     }

  105.     printf("\n");
  106. }


























阅读(813) | 评论(0) | 转发(0) |
0

上一篇:Oracle分析函数学习笔记1

下一篇:24点问题

给主人留下些什么吧!~~