#include<stdio.h>
#include<stdlib.h>
#define MAX 500001
int array[MAX], array1[MAX];
__int64 sum;
void MergeSort(int, int);
void Merge(int, int, int);
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int n, m, i, j = 0;
while (1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
sum = 0;
scanf("%d", &m);
if (m == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
for (i = 0; i < m; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d", &array[i]);
}
MergeSort(0, m - 1);
printf("排序结果\n");
for (i = 0; i < m; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("%d\t", array[i]);
}
}
system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void MergeSort(int i, int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int h;
if (i < j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 将长度为m的输入序列分成两个长度为n/2的子序列 */
h = (i + j)/2;
printf("i = %d h = %d j = %d\n", i, h, j);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 对两个子序列分别进行归并排序 */
MergeSort(i, h);
MergeSort(h + 1, j);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 将2个排好的子序列合并成最终有序序列 */
Merge(i, h, j);
}
}
void Merge(int i, int h, int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int k = 0, y = h + 1, x = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 2个输入区间都不为空时 */
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while (x <= h && y <= j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 取关键字小的记录转移至输出区间 */
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (array[x] > array[y])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
array1[k++] = array[y++];
sum += h - x + 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
array1[k++] = array[x++];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 将非空的输入区间转移至输出区间 */
while (x <= h)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
array1[k++] = array[x++];
}
while (y <= j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
array1[k++] = array[y++];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//* 归并完成后将结果复制到原输入数组 */
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("当前结果\n");
for(x = 0; x < k; x++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
array[i + x] = array1[x];
printf("%d ", array[i + x]);
}
printf("\n");
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
6
1 2 5 6 3 4
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
*/
|