python 冒泡排序

冒泡排序：将已经排序区域放于列表的末尾，在遍历列表的过程中，将元素两两比较，并将较大的元素交换到更高的位置上去。如此反复，直到所有元素都排序好位置。

以下两个python冒泡排序：#vim   bubble_sort.py

  1 #!/usr/bin/env python
  2
  3 def bubble_sort1(L):                        #第一个冒泡排序
  4     ''' bubble sort.'''
  5     i = len(L) - 1         
  6     while i != -1:
  7         Max =find_max(L,i)
  8         L[i],L[Max] = L[Max],L[i]
  9         i = i - 1          
 10
 11 def find_max(L,m):                        #第一个冒泡排序寻找最大值函数
 12     ''' find the max index.'''
 13     Max = m
 14     i = m -1
 15     while i != -1:
 16         if L[i] > L[Max]:
 17            Max = i
 18
 19         i = i - 1
 20
 21     return Max
 22
 23
 24 def bubble_sort2(L):                      #第二个冒泡排序
 25     for j in range(len(L)):
 26         while j != 0:
 27             if L[j-1] > L[j]:
 28                 L[j],L[j-1] = L[j-1],L[j]
 29             j = j -1        
~                       

第二个排序，代码相对少些，但是性能貌似不如第一个排序。

测试：
#vim sort_time.py

#!/usr/bin/env python3.1  

import time
from bubble_sort import bubble_sort
from bubble_sort import bubble_sort2

def built_in(L):
    ''' Call list.sort -- we need our own function to do this so that we can treat it as we treat our own sorts.'''
    L.sort()

def print_times(L):
    ''' Print the number of millinseconds it takes for selection_sort and insertion_sort to run.'''
    print len(L),
    for func in (bubble_sort,bubble_sort2):
        L_copy = L[:]
        t1 = time.time()
        func(L_copy)
        t2 = time.time()
        print "\t%.1f" %((t2 - t1) * 1000.),
    print

for list_size in [10,1000,2000,3000,4000]:
    L = range(list_size)
    L.reverse()
    print_times(L)


结果：
#python sort_time.py
10         0.0          0.0
1000     84.3        214.9    
2000     336.3      847.0
3000     738.2      1844.2
4000     1294.2    3335.6


第一个比第二个排序速度竟然快了一倍多？！？