#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
int a[100] = { 7,5,6,4 };
void mergeSort(int a[],int start , int end ,int &count) {
if (a == NULL) return;
if (start >= end) return;
int mid = (start + end) / 2;
mergeSort(a,start,mid,count);
mergeSort(a, mid+1,end,count);
int result[100];
int i = mid, j = end, k = end - start;
while (i >= start && j >= mid + 1)
{
if (a[i] <= a[j])
{
result[k--] = a[j--];
}
else
{
int t = j;
while (t >= mid + 1)
{
cout << "( " << a[i] << " " << a[t--] << " )\n";
count++;
}
result[k--] = a[i--];
}
}
while(i >= start)
result[k--] = a[i--];
while (j >= mid+1)
result[k--] = a[j--];
for(k = 0,i= start;i<=end;k++,i++)
a[i] = result[k];
}
int main() {
int count = 0;
mergeSort(a, 0, 3,count);
cout << "\n总逆序数：" << count;
return 0;
}
(剑指offer)用归并排序求逆序数
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Description In this problem, you have to analyze a partic...
