題目大意是求解快排最壞情況下的交換次數(shù)，我們知道，快速排序在最壞情況下會退化為冒泡排序，因此快排最壞情況下的交換次數(shù)也就是冒泡排序?qū)慕粨Q次數(shù)。很容易想到這一題用冒泡排序，并記錄交換次數(shù)就行了。
這樣做看似可行，其實是行不通的，數(shù)據(jù)量是500000，由于冒泡排序的時間復雜度是O(N^2)，所以問題的規(guī)模就是500000^2=2.5 * E11，一般我們認為計算機每秒的計算量是E9，因此用冒泡排序是行不通的。
聯(lián)想有關排序的算法，我們希望這一題的時間復雜度能夠降為O(NlogN)，快排、堆排序、合并排序滿足這樣的要求，可是前兩種排序方式的交換方式毫無規(guī)律可循，只剩下歸并排序。
我們來看歸并排序，它的核心是歸并（由Merge()函數(shù)實現(xiàn)），就是將兩個有序序列合并為一個有序序列。由冒泡排序我們知道，交換的總次數(shù)就是初始序列中每個元素交換次數(shù)的總和，每個元素的交換次數(shù)等于該元素后面比自己小的元素的個數(shù)（因為最終比自己小的元素都在自己前面）。
下圖是一次Merge()過程：
可以看出，元素“1”沒有移動，元素“4”向后移動了1位，元素“10”向后移動了3位，所以本次合并共移動了4次。統(tǒng)計合并排序過程中所有的移動次數(shù)即可。
本題代碼如下
#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://m.shnenglu.com/hoolee/archive/2012/07/18/184029.html
posted on 2012-07-18 17:46
小鼠標 閱讀(266)
評論(0) 編輯 收藏 引用 所屬分類:
排序