第17节，把事情想清楚，比写代码更重要

初学者总是急于写代码，或是为了验证自己所学，或是为了体验代码运行时的舒畅感，但有经验的程序员都知道，代码是解决问题过程中，最最简单，最最轻松的一个环节，真正的麻烦，是把问题想清楚。

1. 永远用不到的冒泡排序

很多面试都会让你手写冒泡排序，而冒泡排序在工作中永远都不会使用，因为有效率更高的排序算法，即便是效率更高的排序算法也是现成的，不需要你自己实现，你可以拿来就用。

那为什么还在面试环节考察你冒泡排序算法呢？其实他考察的不是你会不会冒泡排序，他考察的是你理解问题，分析问题，拆解问题的能力。

靠背，靠记忆，是很难写出冒泡排序的，但如果你真正理解冒泡排序算法，任何时候，任何编程语言，你都能快速的写出冒泡排序，哪怕是用伪代码都行。

2. 冒泡排序的思路

冒泡排序的思路是比较相邻两个元素的值，如果左侧的数值大于右侧，那么就交换他们的位置，重复这个过程，直到没有相邻元素需要交换。

比较相邻两个元素的大小，索引为0的和索引为1的进行比较，随后，索引为1的和索引为2的进行比较，列表里最后一个元素右侧没有相邻元素了，因此，它只和左侧的相邻元素比较一次，对于索引为0的元素呢，它只和右侧的相邻元素比较了一次。

ok，那我们就遍历，从索引0开始，假设最大索引是9，那么我们就遍历到8，索引为8的元素和索引为9的元素进行大小比较。经过这一轮比较后，列表里的最大值一定被移动到了索引为9的位置。道理很简单，俩俩比较相邻的元素，如果左侧大，就交换位置，右侧大，不交换，两个元素中较大的元素一定在右侧，然后参与下一次比较。

一个长度为10的列表，按照上面的思路遍历了一次，最大值就移动到了列表末尾，也就是索引为9的位置，那么再遍历一次呢,列表里第2大的元素一定被移动到索引为8的位置，在遍历一次呢,列表里第3大的元素一定被移动到索引为7的位置。

遍历9次，整个列表就变得有序了。

3. 冒泡排序实现

根据前面的分析，我先实现一次遍历比较

lst = [6, 13, 5, 33, 23, 15, 9, 23, 11, 10]

for i in range(len(lst)-1):
    if lst[i] > lst[i+1]:
        tmp = lst[i]
        lst[i] = lst[i+1]
        lst[i+1] = tmp

print(lst[-1])      # 33

遍历一次，俩俩比较，较大的数交换到右侧，列表里最大值一定被移动到列表末尾，接下来，我需要把这个过程重复9次

lst = [6, 13, 5, 33, 23, 15, 9, 23, 11, 10]

for j in range(len(lst)-1):
    for i in range(len(lst)-1):
        if lst[i] > lst[i+1]:
            tmp = lst[i]
            lst[i] = lst[i+1]
            lst[i+1] = tmp

print(lst)

为什么是循环9次呢，因为列表有10个元素，没遍历一次，就有一个数被移动到自己该去的位置上，9个数被移动到自己该去的位置上，最后一个数也必然在自己该在的位置上。

继续思考，当j=5时，已经有5个数被移动到了自己该去的位置上，而且一定是在列表末尾处的5个位置，那么，里面的for循环有必要每次都对他们进行比较么,已经没有必要了，因为他们已经有序，修改代码

lst = [6, 13, 5, 33, 23, 15, 9, 23, 11, 10]

for j in range(len(lst)-1):
    for i in range(len(lst) - 1 - j):
        if lst[i] > lst[i+1]:
            tmp = lst[i]
            lst[i] = lst[i+1]
            lst[i+1] = tmp

print(lst)

我只修改了内曾for循环的条件，减少不必要的循环。

代码永远是次要问题，首要问题是我们清楚的知道自己在做什么，如果不知道自己在做什么，逻辑很模糊，很混乱，你又怎么可能写得出代码呢。