题目描述
给n个长k的序列,根据每个序列的反序对个数排序。
样例
输入
4
8
0 1 2 3 4 5 6 7
11 6 5 7 3 2 2 0
2 3 6 1 9 3 5 4
0 2 4 5 3 10 6 7
4个序列反序对分别为0,25,10,4个,重新排序得到输出。
输出
[[0, 1, 2, 3, 4, 5, 6, 7], [0, 2, 4, 5, 3, 10, 6, 7], [2, 3, 6, 1, 9, 3, 5, 4], [11, 6, 5, 7, 3, 2, 2, 0]]
算法
求反序对数量
直接两层循环嵌套。
对序列排序
这里题目要求稳定性,而且还是根据被排序的序列的一个参数排序,所以偷懒用选择排序了。
复杂度
求反序对数量的复杂度为O(k^2);对序列排序的复杂度为O(N^2)。总复杂度为O(k^2+N^2)。
注意这里总复杂度是相加的,而N,K都小于200。这也是为什么用选择排序就足够的原因。
python3 代码
n = int(input())
k = int(input())
shelf = []
for i in range(n):
shelf.append(list(map(int, input().split())))
def count_reverse(l):
r = 0
for i in range(len(l)):
for j in range(i):
if l[i] < l[j]:
r += 1
return r
r = []
newshelf=[]
for layer in shelf:
r.append(count_reverse(layer))
print(r)
for i in range(n):
minr = 200*200
pminr = 0
for j in range(n):
if(r[j] < minr):
minr = r[j]
pminr = j
r[pminr] = 200*200
newshelf.append(shelf[pminr])
print(newshelf)