python实现冒泡排序详解编程语言

python算法 – 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))