You are currently viewing Devide and Conquer Counting Inversions with Python

Devide and Conquer Counting Inversions with Python

本文主要内容关于python归并排序求逆序数的算法。

解决问题:给定有限长度的无重复乱序数组,求其逆序数个数。简单来说我们可以用两个循环来解决,但是复杂度为$O(N^2)$,若利用归并排序,复杂度就降为了$O(N log(N))$。以下给出一个实现,

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
class Ivrs_num(object):

def __init__(self, filename):
self.count = 0
self.filename = filename

def load_txt(self):
'''载入txt文件保存为list'''
int_list = []
with open(self.filename) as f:
for line in f:
int_list.append(int(line))
return int_list

def merge(self, ListA, ListB):
'''将两个已经排序好的数组合并成新的排序好的数组
顺便计算逆序数'''
newList = []
while ListA and ListB:
if int(ListA[0]) > int(ListB[0]):
self.count += len(ListA)
newList.append(ListB.pop(0))
else:
newList.append(ListA.pop(0))
return newList + ListA + ListB

def merge_sort(self, A):
'''归并排序'''
if len(A) == 1: return A
else:
middle = len(A) // 2
return self.merge(self.merge_sort(A[:middle]), self.merge_sort(A[middle:]))

def count_ivrs(self):
data = self.load_txt()
self.merge_sort(data)
return self.count

if __name__ == "__main__":
ivrs = Ivrs_num("IntegerArray.txt")
print ivrs.count_ivrs()

发表评论