/**
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
*/
- #include<stdio.h>
- #include<stdlib.h>
- typedef struct node *pNode;
- struct node
- {
- __int64 data;
- };
- __int64 mergeSort(pNode source,pNode destination,__int64 begin,__int64 end);
- __int64 merge(pNode source,pNode destination,__int64 begin,__int64 mid,__int64 end);
- void printArray(pNode destination,__int64 n);
- int main()
- {
- __int64 n,i,result;//n表示输入的表示待排序的元素个数
- pNode source,destination,pTemp1,pTemp2;
- while(1 == scanf("%I64d",&n) && n != 0)
- {
- source = NULL;
- destination = NULL;
- source = (pNode)malloc(n * sizeof(__int64));
- destination = (pNode)malloc(n * sizeof(__int64));
- if(source == NULL || destination == NULL)
- {
- exit(1);
- }
- for(i=0; i<n; i++)
- {
- scanf("%I64d",&((source+i)->data));
- }
- // printArray(sourceArray,n);
- result = mergeSort(source,destination,0,n-1);
- //printArray(destination,n);
- // printArray(sourceArray,n);
- printf("%I64d\n",result);
- pTemp1 = source;
- pTemp2 = destination;
- free(pTemp1);
- free(pTemp2);
- }
- return 0;
- }
- __int64 mergeSort(pNode source,pNode destination,__int64 begin,__int64 end)
- {
- __int64 mid,temp1 = 0,temp2 = 0,temp3 = 0;
- if(begin == end)
- {
- (destination+begin)->data = (source+end)->data;
- }
- else if(begin < end)
- {
- mid = (begin + end) / 2;
- temp1 = mergeSort(source,destination,begin,mid);
- temp2 = mergeSort(source,destination,mid+1,end);
- temp3 = merge(source,destination,begin,mid,end);
- }
- return temp1 + temp2 + temp3;
- }
- __int64 merge(pNode source,pNode destination,__int64 begin,__int64 mid,__int64 end)
- {
- __int64 i = begin,j = mid + 1,k = begin,count = 0;
- while(i <= mid && j <= end)
- {
- if((source+i)->data <= (source+j)->data)
- {
- (destination+k)->data = (source+i)->data;
- i++;
- k++;
- }
- else
- {
- (destination+k)->data = (source+j)->data;
- //printf("%d,%d\n",sourceArray[i],sourceArray[j-1]);
- count += mid - i + 1;
- j++;
- k++;
- }
- }
- while(i <= mid)
- {
- (destination+k)->data = (source+i)->data;
- i++;
- k++;
- }
- while(j <= end)
- {
- (destination+k)->data = (source+j)->data;
- j++;
- k++;
- }
- i = begin;
- while(i <= end)
- {
- (source+i)->data = (destination+i)->data ;
- i++;
- }
- return count;
- }
- //打印数组
- void printArray(pNode destination,__int64 n)
- {
- __int64 i;
- for(i=0; i<n; i++)
- {
- printf("%I64d ",(destination+i)->data);
- }
- printf("\n");
- }
阅读(1148) | 评论(0) | 转发(0) |