python数据结构与算法—

python数据结构与算法——冒泡排序

用两种方式实现，非递归和递归

直接上代码：

先是失败的递归方式，涉及到对象引用的问题：

 1 # Bad  想一想为啥不行？
 2 def bubblesort_rec_bad(A):
 3     if len(A)==1:    # 只剩一个数时 直接返回结束递归
 4         return
 5 
 6     for j in range(len(A)-1):
 7         if A[j] < A[j+1]:   # 依次比较两个相邻的数
 8             A[j], A[j+1] = A[j+1], A[j]     #交换两个相邻的数
 9 
10     # 比较余下n-1个数
11     bubblesort_rec_bad(A[:-1])  # <<关键在与深复制的问题

下面是运行结果

    # 错误递归
    A = [12,35,99,16,76]
    bubblesort_rec_bad(A)
    print "bad rec: ",A
    
    >>>bad rec:  [35, 99, 16, 76, 12]

递归调用的参数传递中，A[:-1] 表示列表A的前n-1个元素，并将其值复制一份获得一个新的列表(:),

用C语言说，传入的其实是形参

正确的递归方式可以这样子弄：

1 def bubblesort_rec(A,i):
2     if i==1:    # 只剩一个数时 直接返回结束递归
3         return
4     for j in range(i-1):
5         if A[j] < A[j+1]:   # 依次比较两个相邻的数
6             A[j], A[j+1] = A[j+1], A[j]     #交换两个相邻的数
7     # 比较余下n-1个数
8     bubblesort_rec(A,i-1)

结果：

# 正确递归
    A = [12,35,99,16,76]
    bubblesort_rec(A, len(A))
    print "good rec:",A

good rec: [99, 76, 35, 16, 12]

不用递归也是可以的，用两层循环

1 # 冒泡排序 二层循环格式
2 def bubblesort(A):
3     n = len(A)
4     for i in range(n,1,-1): # i = n, n-1, n-2, ..., 2
5         # 截取 A 的前i个元素进行冒泡
6         for j in range(i-1):
7             if A[j] < A[j+1]:   # 依次比较两个相邻的数
8                 A[j], A[j+1] = A[j+1], A[j]     #交换两个相邻的数

 # 循环格式
    A = [12,35,99,16,76]
    bubblesort(A)
    print "no rec:  ",A

>>>no rec:   [99, 76, 35, 16, 12]