107. 超快速排序
摘要
Title: 107. 超快速排序
Tag: 逆序对、归并排序
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
107. 超快速排序
-
题意
在这个问题中，您必须分析特定的排序算法----超快速排序。
该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序。
对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。 -
思路
题目就是在模拟冒泡排序，而交换的次数，就是冒泡排序的交换次数就是我们的逆序对个数
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42'''
Author: NEFU AB-IN
Date: 2022-02-18 16:17:54
FilePath: \ACM\Acwing\107.py
LastEditTime: 2022-02-18 16:17:55
'''
a = []
def merge(l, r):
if l >= r:
return 0
mid = l + r >> 1
res = merge(l, mid) + merge(mid + 1, r)
i, j = l, mid + 1
tmp = []
while i <= mid and j <= r:
if a[i] <= a[j]:
tmp.append(a[i])
i += 1
else:
tmp.append(a[j])
j += 1
res += mid - i + 1
tmp += a[i:mid + 1]
tmp += a[j:r + 1]
a[l:r + 1] = tmp
return res
while True:
n = int(input())
if n == 0:
exit(0)
for i in range(n):
a.append(int(input()))
print(merge(0, n - 1))
a = []