问题
在这个问题中，您必须分析特定的排序算法----超快速排序。
该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。
对于输入序列9 1 0 5 4，超快速排序生成输出0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数n，代表该用例中输入序列的长度。
接下来n行每行输入一个整数 ai ,代表用例中输入序列的具体数据，第 i 行的数据代表序列中第 i 个数。
当输入用例中包含的输入序列长度为0时，输入终止，该序列无需处理。
输出格式
对于每个需要处理的输入序列，输出一个整数op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。
数据范围
0≤N<500000,
0≤ai≤999999999
输入样例：
5
9
1
0
5
4
3
1
2
3
0
输出样例：
6
0
思路
只通过比较和交换两个相邻两个数值的排序方法，实际上就是冒泡排序算法。在排序过程中，每找到一对大小颠倒的相邻数值，把他们交换，就会使整个序列的逆序对个数减少一。最终排好序后逆序对个数变为 0 ，所以，对 a 进行冒泡排序需要交换的最少次数即为序列 a 中的逆序对个数。直接使用归并排序求出 a 的逆序对个数即为本题的答案。
题解
#include<iostream>
using namespace std;
const int MAX = 5e5 + 5;
int a[MAX];
int back[MAX];
long long cnt;
void merge(int l, int r, int mid) {
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) back[k++] = a[i++];
else {
back[k++] = a[j++];
cnt += mid - i + 1;
}
}
while (i <= mid) back[k++] = a[i++];
while (j <= r) back[k++] = a[j++];
for (int k = l; k <= r; ++k) a[k] = back[k];
}
void merge_sort(int l, int r) {
if (l >= r) return;
if (l + 1 == r) {
if (a[l] > a[r]) {
swap(a[l], a[r]);
cnt++;
}
return;
}
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
merge(l, r, mid);
}
int main() {
int n;
cin >> n;
while (n) {
cnt = 0;
for (int i = 0; i < n; ++i) scanf("%d", &a[i + 1]);
merge_sort(1, n);
cout << cnt << endl;
cin >> n;
}
return 0;
}
| 标题： | AcWing-107-超快速排序 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/51 |
| 更新： | 2022-09-18 22:34:36 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |