107超快速排序（逆序对归并排序模板）

1. 问题描述&＃xff1a;

在这个问题中&＃xff0c;您必须分析特定的排序算法----超快速排序。该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列&＃xff0c;直到序列按升序排序。对于输入序列 9 1 0 5 4&＃xff0c;超快速排序生成输出 0 1 4 5 9。您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。每个测试用例的第一行输入整数 n&＃xff0c;代表该用例中输入序列的长度。接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据&＃xff0c;第 i 行的数据代表序列中第 i 个数。当输入用例中包含的输入序列长度为 0 时&＃xff0c;输入终止&＃xff0c;该序列无需处理。

输出格式

对于每个需要处理的输入序列&＃xff0c;输出一个整数 op&＃xff0c;代表对给定输入序列进行排序所需的最小交换操作数&＃xff0c;每个整数占一行。

数据范围

0 ≤ n <500000&＃xff0c;
一个测试点中&＃xff0c;所有 n 的和不超过 500000。
0 ≤ ai ≤ 999999999

输入样例&＃xff1a;

5
9
1
0
5
4
3
1
2
3
0

输出样例&＃xff1a;

6
0
来源&＃xff1a;https://www.acwing.com/problem/content/description/109/

2. 思路分析&＃xff1a;

分析题目可以知道我们每一次交换的时候如果当前的ai > ai&＃43;1那么恰好减少一个逆序对&＃xff0c;而最终我们是需要使得逆序对的数量为0所以最少需要操作的次数为当前序列中逆序对的数量&＃xff0c;并且存在这样一个方案每一次交换相邻的ai与ai&＃43;1(ai > ai&＃43;1)的元素这样逆序对的数量就会减少1&＃xff0c;最终操作k次就可以使得逆序对的数量为0&＃xff0c;所以最终的答案就是当前序列中逆序对的数量&＃xff0c;可以使用归并排序来求解出逆序对的数量。

3. 代码如下&＃xff1a;

from typing import Listclass Solution:a &＃61; Nonedef mergeSort(self, l: int, r: int):if l >&＃61; r: return 0mid &＃61; l &＃43; r >> 1res &＃61; self.mergeSort(l, mid) &＃43; self.mergeSort(mid &＃43; 1, r)w &＃61; list()i, j &＃61; l, mid &＃43; 1while i <&＃61; mid and j <&＃61; r:if self.a[i] <&＃61; self.a[j]:w.append(self.a[i])i &＃43;&＃61; 1else:# 当前位置到mid的与a[j]都是逆序对所以mid - i &＃43; 1就是当前的a[i]~a[mid]与a[j]的逆序对的数量res &＃43;&＃61; mid - i &＃43; 1w.append(self.a[j])j &＃43;&＃61; 1# 将剩余的元素存储到w中while i <&＃61; mid:w.append(self.a[i])i &＃43;&＃61; 1while j <&＃61; r:w.append(self.a[j])j &＃43;&＃61; 1k &＃61; 0for u in range(l, r &＃43; 1):self.a[u] &＃61; w[k]k &＃43;&＃61; 1return resdef process(self):while True:n &＃61; int(input())if n &＃61;&＃61; 0: breaka &＃61; list()for i in range(n):a.append(int(input()))self.a &＃61; aprint(self.mergeSort(0, n - 1))if __name__ &＃61;&＃61; "__main__":Solution().process()