题目概述

在这个问题中，您必须分析特定的排序算法。该算法通过交换两个相邻的序列元素来处理由n个不同整数组成的序列，直到序列按升序排序。对于输入序列:
9 1 0 5 4 ,

Ultra QuickSort生成输出:
0 1 4 5 9 .

您的任务是确定Ultra QuickSort需要执行多少交换操作才能对给定的输入序列进行排序。
输入

输入包含几个测试用例。每个测试用例都从一行开始，该行包含一个整数
n<500000----输入序列的长度。以下n行中的每一行都包含一个整数
0≤ a[i]≤ 999999999，第i个输入序列元素。
输入由长度n=0的序列终止。不处理此序列。

输出

对于每个输入序列，程序都会打印一行，其中包含整数op，
这是对给定输入序列进行排序所需的最小交换操作数。

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

思路解析

这题是逆序对的裸题。
我们先来分析一下逆序对：
对于一个序列a，若 i < j 且 a[i] > a[j]，则称 a[i] 与 a[j] 构成逆序对。
我们使用归并排序法，每次把序列二分，递归对左右两半排序，然后合并。递归对左右两半排序时，可以把左右两半各自内部的逆序对数作为子问题计算，因此我们只需要在合并时考虑 “左边一半里一个较大的数”和“右边一半里一个较小的数”构成逆序对 的情形即可。

归并函数

我们采用两个指针 i 与 j 分别对二者进行扫描，不断比较两个指针所指向数值 a[i] 与 a[j] 的大小，将小的加入到排序的结果数组中。若小的是 a[ j ]，则
a[1~mid] 都比 a[ j ] 要大，它们都可以与 a[ j ] 构成逆序对，共mid-i+1个。

函数代码如下：

int merge(int A[] ,int l, int mid, int r)
{
	int b[100];
	// 合并A[0~mid]和A[mid+1~r]
	// A是待排序数组，b是临时数组，存放较小的数，cnt是逆序对个数
	int i = 0,j = mid + 1;
	int cnt = 0;
	for (int k = 0; k < r; k++)
	{
		if (j >= r || i <= mid && A[i] <= A[j])
			b[k] = A[i++];
		else
		{
			b[k] = A[j++];
			cnt += mid - i + 1;
		}

	}
	for (int k = 0; k < r; k++)
		A[k] = b[k];
	return cnt;

}

int mergeSort(int A[],int left,int right)
{
	if (left < right)
	{
		int mid = left + (right - left) / 2;
		//当前数组内的逆序对数等于两个子数组的逆序对数加上归并时
		//计算出的逆序对数
		return mergeSort(A,left, mid)
			+ mergeSort(A,mid + 1, right)
			+ merge(A,left, mid, right);

	}
	return 0;
}

题目代码

#include<iostream>
using namespace std;

int merge(int A[] ,int l, int mid, int r)
{
	int b[100];
	// 合并A[0~mid]和A[mid+1~r]
	// A是待排序数组，b是临时数组，存放较小的数，cnt是逆序对个数
	int i = 0,j = mid + 1;
	int cnt = 0;
	for (int k = 0; k < r; k++)
	{
		if (j >= r || i <= mid && A[i] <= A[j])
			b[k] = A[i++];
		else
		{
			b[k] = A[j++];
			cnt += mid - i + 1;
		}

	}
	for (int k = 0; k < r; k++)
		A[k] = b[k];
	return cnt;

}

int mergeSort(int A[],int left,int right)
{
	if (left < right)
	{
		int mid = left + (right - left) / 2;
		//当前数组内的逆序对数等于两个子数组的逆序对数加上归并时计算出的逆序对数
		return mergeSort(A,left, mid)
			+ mergeSort(A,mid + 1, right)
			+ merge(A,left, mid, right);

	}
	return 0;
}


void main()
{
	int n;
	cin >> n;
	int A[1000];
	int a;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		A[i] = a;
	}
	cout << mergeSort(A, 0, n);


}

最后

以上就是开朗火龙果为你收集整理的逆序对问题--Ultra-QuickSort题目概述思路解析题目代码的全部内容，希望文章能够帮你解决逆序对问题--Ultra-QuickSort题目概述思路解析题目代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。