首先來看看原題
微軟2010年筆試題
在一個排列中殃姓，如果一對數(shù)的前后位置與大小順序相反掏导，即前面的數(shù)大于后面的數(shù)对供，那么它們就稱為一個逆序數(shù)對逾苫。一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。如{2柬帕，4哟忍，3狡门，1}中，2和1锅很，4和3其馏，4和1，3和1是逆序數(shù)對爆安，因此整個數(shù)組的逆序數(shù)對個數(shù)為4叛复，現(xiàn)在給定一數(shù)組，要求統(tǒng)計出該數(shù)組的逆序數(shù)對個數(shù)扔仓。
計算數(shù)列的逆序數(shù)對個數(shù)最簡單的方便就最從前向后依次統(tǒng)計每個數(shù)字與它后面的數(shù)字是否能組成逆序數(shù)對褐奥。代碼如下：
#include <stdio.h>
int main()
{
const int MAXN = 8;
int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};
int nCount = 0;
int i, j;
for (i = 0; i < MAXN; i++)
for (j = i + 1; j < MAXN; j++)
if (a[i] > a[j])
nCount++;
printf("逆序數(shù)對為: %d\n", nCount);
}
運(yùn)行結(jié)果如下：
這種方法用到了雙循環(huán)，時間復(fù)雜度為O(N^2)当辐，是一個不太優(yōu)雅的方法抖僵。因此我們嘗試用其它方法來解決鲤看。
在《經(jīng)典算法系列之五歸并排序的實現(xiàn)》中觀察歸并排序——合并數(shù)列(1缘揪，3，5)與(2义桂，4)的時候：
1．先取出前面數(shù)列中的1找筝。
2．然后取出后面數(shù)列中的2，明顯慷吊！這個2和前面的3袖裕，5都可以組成逆序數(shù)對即3和2，5和2都是逆序數(shù)對溉瓶。
3．然后取出前面數(shù)列中的3急鳄。
4．然后取出后面數(shù)列中的4，同理堰酿，可知這個4和前面數(shù)列中的5可以組成一個逆序數(shù)對疾宏。
這樣就完成了逆序數(shù)對的統(tǒng)計，歸并排序的時間復(fù)雜度是O(N * LogN)触创，因此這種從歸并排序到數(shù)列的逆序數(shù)對的解法的時間復(fù)雜度同樣是O(N * LogN)坎藐，下面給出代碼：
//從歸并排序到數(shù)列的逆序數(shù)對
#include <stdio.h>
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) //a[i] 前面的數(shù) a[j] 后面的數(shù)
{
if (a[i] < a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
//a[j]和前面每一個數(shù)都能組成逆序數(shù)對
g_nCount += m - i + 1;
}
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左邊有序
mergesort(a, mid + 1, last, temp); //右邊有序
mergearray(a, first, mid, last, temp); //再將二個有序數(shù)列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
return true;
}
int main()
{
printf(" 從歸并排序到數(shù)列的逆序數(shù)對 \n");
const int MAXN = 8;
int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};
g_nCount = 0;
MergeSort(a, MAXN);
printf("逆序數(shù)對為: %d\n", g_nCount);
return 0;
}
運(yùn)行結(jié)果：
推薦閱讀：
經(jīng)典算法應(yīng)用之一----歸并排序（微軟筆試題）
經(jīng)典算法應(yīng)用之二----基數(shù)排序（google筆試題）
經(jīng)典算法應(yīng)用之三----應(yīng)用二中題目的升華
經(jīng)典算法應(yīng)用之四（上）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（中）---基本位操作之算法篇
經(jīng)典算法應(yīng)用之四（下）---百度面試題
經(jīng)典算法應(yīng)用之五---隨機(jī)生成和為S的N個正整數(shù)
經(jīng)典算法應(yīng)用之六---過橋問題和過河問題
經(jīng)典算法應(yīng)用之七----10億數(shù)據(jù)中取最大的100個數(shù)據(jù)
