python冒泡排序

python冒泡排序
一种简单的排序算法。
比较相邻的两个元素，如果第一个比第二个大，那么就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码如下：

seq = [5,4,3,2,1]
print '排序前：',seq
for i in range(len(seq)-1): #这个循环 是循环次数，不是数组下标。
    for j in range(len(seq)-1-i): #这个循环才是真正的数组下标。
        if seq[j] > seq[j+1]:
            seq[j], seq[j + 1] = seq[j + 1], seq[j]

print '排序后：',seq

运行结果如下：

image.png

1. 第一个循环是循环 次数，多少个元素就循环len(seq)-1次，不是数组的下标。

2. 第二个循环才是真正的数组 下标 。循环len(seq)-i-1次。

下面解释一下 为什么第一个for 循环len(seq)-1次。
seq有五个元素，每次循环的时候，都拿一个元素对比其他元素。当对比到第四次的时候，其实整个数组已经是排序好的了

seq = [5,4,3,2,1]
print '排序前：',seq
for i in range(len(seq)): #这个循环 是循环次数，不是数组下标。
    for j in range(len(seq)-i-1): #这个循环才是真正的数组下标。
        if seq[j] > seq[j+1]:
            seq[j], seq[j + 1] = seq[j + 1], seq[j]
    print '排序进行时：第 %s 次循环后，排序好的数组 ' % (i + 1), seq
print '排序后：',seq

不减1的情况下 image.png

减1的情况下：

image.png

第二个for 循环len(seq)-1-i次
为什么要减去 i 呢？
我们看一下上面的运行结果图，
第一次循环时，最后一个元素是随机的元素，此时 i == 0，
第二次循环时，因为最后一个元素是最大的元素了，完全没必要在对比一次了，所以就把最后一个元素pass了，此时 i == 1，所以 len（seq）- 1 - i，剔除最后一个元素。
第三次循环，最后两个元素是整个数组最大的元素，所以最后两个元素完全没必要进行对比，所以pass掉最后两个元素，此时 i == 2，所以 len(seq)-1-i,剔除最后两个元素。
以此类推，直到循环结束。