python实现冒泡排序

# -*- encoding: utf-8 -*-


def bubble_sort(seq,cmp=cmp):

   """冒泡排序，伪码如下：

   BUBBLESORT(A)

   1  for i ← 1 to length[A]

   2    do for j ← length[A] downto i+1

   3      do if A[j] < A[j-1]

   4        then exchange A[j] ? A[j-1]


   T(n) = θ(n^2)


   Args:

       seq (Sequence): 一个序列对象。

       cmp (Function): 比较函数。默认为内建函数cmp()。


   Returns:

       一个排序后的列表。

   """

   if (seq == None):

       return None

   length = len(seq)


   for i in range(length):

       for j in range(length-1,i,-1):

           if seq[j] < seq[j-1]:

               seq[j],seq[j-1] = seq[j-1],seq[j]


   return seq


if __name__ == '__main__':

   import random,timeit


   items = range(10000)

   random.shuffle(items)


   def test_sorted():

       print(items)

       sorted_items = sorted(items)

       print(sorted_items)


   def test_bubble_sort():

       print(items)

       sorted_items = bubble_sort(items)

       print(sorted_items)


   test_methods = [test_sorted,test_bubble_sort]

   for test in test_methods:

       name = test.__name__ # test.func_name

       t = timeit.Timer(name + '()','from __main__ import ' + name)

       print(name + ' takes time : %f' % t.timeit(1))