题目大意是求解快排最坏情况下的交换次数，我们知道，快速排序在最坏情况下会退化为冒泡排序，因此快排最坏情况下的交换次数也就是冒泡排序对应的交换次数。很容易想到这一题用冒泡排序，并记录交换次数就行了。
这样做看似可行，其实是行不通的，数据量是500000，由于冒泡排序的时间复杂度是O(N^2)，所以问题的规模就是500000^2=2.5 * E11，一般我们认为计算机每秒的计算量是E9，因此用冒泡排序是行不通的。
联想有关排序的算法，我们希望这一题的时间复杂度能够降为O(NlogN)，快排、堆排序、合并排序满足这样的要求，可是前两种排序方式的交换方式毫无规律可循，只剩下归并排序。
我们来看归并排序，它的核心是归并（由Merge()函数实现），就是将两个有序序列合并为一个有序序列。由冒泡排序我们知道，交换的总次数就是初始序列中每个元素交换次数的总和，每个元素的交换次数等于该元素后面比自己小的元素的个数（因为最终比自己小的元素都在自己前面）。
下图是一次Merge()过程：
可以看出，元素“1”没有移动，元素“4”向后移动了1位，元素“10”向后移动了3位，所以本次合并共移动了4次。统计合并排序过程中所有的移动次数即可。
本题代码如下
#include<stdio.h>
#include<stdlib.h>
#define LEN 500010
long long count;
void Copy(int *a, int *b, int f, int r)
{
for(int i = 0; i <= r - f; i++)
a[i + f] = b[i];
}
void Merge(int *a, int f, int m, int r)
{
int *b = (int *)malloc(sizeof(int) * ( r - f + 1));
int i = f;
int j = m + 1;
int k = 0;
while(i <= m && j <= r)
{
if(a[i] > a[j])
b[k++] = a[j++];
else
{
b[k++] = a[i++];
if(k + f > i)
count += k + f - i;
}
}
while(i <= m)
{
b[k++] = a[i++];
if(k + f > i)
count += k + f - i;
}
while(j <= r)
b[k++] = a[j++];
Copy(a, b, f, r);
free(b);
}
void MergeSort(int *a, int f, int r)
{
if(f < r)
{
int i = (r + f) / 2;
MergeSort(a, f, i);//ÅÅÐò×ó°ë²¿·Ö
MergeSort(a, i + 1, r);//ÅÅÐòÓҰ벿·Ö
Merge(a, f, i, r);//ºÏ²¢
}
}
int main()
{
int i, j;
int N;
int a[LEN];
scanf("%d", &N);
while(N != 0)
{
for(i = 1; i <= N; i++)
scanf("%d", &a[i]);
count = 0;
MergeSort(a, 1, N);
printf("%lld\n", count);
scanf("%d", &N);
}
//system("pause");
}
有关合并排序请参阅：
http://www.cppblog.com/hoolee/archive/2012/07/18/184029.html
posted on 2012-07-18 17:46
小鼠标 阅读(243)
评论(0) 编辑 收藏 引用 所属分类:
排序