python之冒泡排序

发表于 更新于 分类于 ， Changyan： 本文字数： 815 阅读时长 ≈ 3 分钟

排序算法是每个编程语言通用的，只是语法不通，之前一直没有下仔细了解过，今天有空刚好看了下，思路很简单，但是很聪明：

首先排序算法的原理就是第一个数依次跟后面的数字比较，大于就交换，否则不交换，每次完成一个数字的排序，有多少字就要循环多少次

如：一组数[9, 2, 7, 5, 4],第一次循环比较，第一个数开始依次向后比较，9最大换到了最右边；第二次2在第一位了，开始依次向后比较，7最大换到了最右边，整过个程下来比较了5x4次，我们来用python的语法写一次，python语法可以省略一个中间变量，使得代码量又减小了

1
2
3
4
5
6
7
8
#这里先写下内层循环，就是第一个数依次向后比较的轮次
lis = [9, 2, 7, 5, 4]    
#5个数字比较4次即可得出最大值
for i in range(len(lis)-1):
    if lis[i] > lis[i+1]:
        lis[i], lis[i+1] = lis[i+1], lis[i]
print(lis)
#至此9换到了最右边

第二轮开始比较从2开始比较，后面依次比较的写法

1
2
3
4
5
6
7
8
lis = [9, 2, 7, 5, 4]
#外层循环，控制依次每个数字比较的轮次，这个次数用数字的数量和数字数量减去1都是一样的，因为最后依次不用比较了，都跟最后一个数比较过了，所以我们这里少循环一次
for item in range(len(lis)-1):    
    #5个数字比较4次即可得出最大值
    for i in range(len(lis)-1):
        if lis[i] > lis[i+1]:
            lis[i], lis[i+1] = lis[i+1], lis[i]
print(lis)

结果已经使我们需要的了。仔细看结果我们其实可以考虑一下，我们似乎还是可以优化下代码的。

如，第一个数字9依次比较之后，已经放在了最右边；第二个数开始比较最大值，其实没必要跟最后一个9比较了，9已经是最大了；第2个最大数选择好之后，第3个数依次比较也没必要跟最右侧两个数字比较了，总结一下，每次比较出一个大数字之后，后面数字再比较，循环轮次应该相应减去1。

优化后代码

1
2
3
4
5
6
7
8
lis = [9, 2, 7, 5, 4]
#外层循环，控制依次每个数字比较的轮次，这个次数用数字的数量和数字数量减去1都是一样的，因为最后依次不用比较了，都跟最后一个数比较过了，所以我们这里少循环一次
for item in range(len(lis)-1):    
    #5个数字比较4次即可得出最大值
    for i in range(len(lis)-1-item):
        if lis[i] > lis[i+1]:
            lis[i], lis[i+1] = lis[i+1], lis[i]
print(lis)

总后我们计算下两种方法总共循环次数：

第一种方法最后内循环次数可以看到是4X4=16次

第二种方法最后内循环次数为4+3+2+1=10次

比较的数字越大，这种循环的次数就会差的更多！！！