这是一道检测inversion count的算法。它将检测输入序列中反序输入的个数,即检测其中有几对A[i] > A[j], i < j 比如输入4，3，2，1，输出应该为3+2+1=6.。 因为： 1. 4比3，2，1大，但4在输入序列中是第一位，比3，2，1的index都小 2. 3比2，1大 3. 2比1大

gistfile1.py

#!/usr/bin/python

############################################################
#
#
#   author: [email protected]
#   date: 03/12/2013
#   purpose: count inversions in a given array of numbers
#
#
############################################################



def countInversions(arr):
  """Iterates through the  given array from rear to fron and 
  coutns the number of inversions for each element by using 
  the split_and_count method
  
  @param arr: array of integers
  @return: number of inversions in given array
  """
  count = 0
  n = len(arr)
  for i in range(n-1, -1, -1):
    count += split_and_count(arr, 0, i-1, arr[i])
  return count
  
def split_and_count(arr, i, j, val):
  """Recursive method to count the number of inversions for
  the value 'val' in the array from the i to the j th indices
  It achieves this by recursively splitting the array until it
  reaches the trivial case (i.e. just one element) and combines
  the result of the inversions upwards. In short, this is a
  divide and conquer approach.
  
  @param arr: array of integers
  @param i: starting index of array from which we need to find
            inversions for val
  @param j: index of array upto which we need to look at  the
            array to find inversions for  val
  @param val: value for which we want to find inversions
  @return: no. of inversions for val
  """
  count = 0
  if(i<j):
    k = (i+j)/2
    count += split_and_count(arr, i, k, val) + split_and_count(arr, k+1, j, val)
  elif(i == j):
    if(arr[i] > val):
      count = 1
  return count


def _main():
  """Fetches an array of integers from the user and returns the
  number of inversions in the array"""
  valStr = raw_input("\n\nEnter array elements: ")
  values = valStr.strip().split()
  arrValues = map(lambda x: int(x, 10), values)
  invCount = countInversions(arrValues)
  print "No. of inversions are: {0}".format(invCount)
  
  
if __name__ == "__main__":
  _main()