第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循环的条件,减少不必要的循环。

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

扫描关注, 与我技术互动

QQ交流群: 211426309

加入知识星球, 每天收获更多精彩内容

分享日常研究的python技术和遇到的问题及解决方案