找逆序对（Python）

作者：dawncold 发布时间：February 3, 2012 分类：技术

其实和昨天的归并排序基本内容一样，就多加了几行输出来帮助理解，找逆序对就是多了一个统计变量而已。


#! /usr/bin/env python
# coding: utf-8

def merge(arraylist, first, middle, last):
    temp = []
    i = first
    j = middle + 1
    while i <= middle and j <= last:
        if arraylist[i] <= arraylist[j]:
            temp.append(arraylist[i])
            i += 1
        else:
            global inv
            inv += middle - i + 1
            temp.append(arraylist[j])
            j += 1
    while i <= middle:
        temp.append(arraylist[i])
        i += 1
    while j <= last:
        temp.append(arraylist[j])
        j += 1
    print temp
    for i in range(0, last - first + 1):
        arraylist[first + i] = temp[i]

def merge_sort(arraylist, first, last):
    if first < last:
        middle = (first + last) / 2
        print "first = %d, middle = %d, last = %d" % (first, middle, last)
        merge_sort(arraylist, first, middle)  
        merge_sort(arraylist, middle + 1, last)
        merge(arraylist, first, middle, last)

if __name__ == "__main__":
    inv = 0
    arr = [2,3,8,6,1]
    print "orign: ", arr
    merge_sort(arr, 0, len(arr) - 1)
    print "final: ", arr
    print "inv = %d" % inv
    1. 1