14.知其然知其所以然，逐行代码详解Python实现选择排序
和孩子一起学Python2020-03-28 08:46
百家号不支持代码格式，文章里的代码排版都是乱的。
如果需要拷贝代码，可以去同名的微信公众号。
在百度搜索“选择排序”，有1630万个结果。可见网上已经有非常多的教程介绍选择排序的原理和实现。
不过这些教程都侧重于介绍选择排序的原理。
有些还制作了生动的gif动画来模拟整个过程。
如下的动画就转自百度搜索里排在第2位的“菜鸟教程”，由于公众号对gif动画有15秒的限制，下面的动画并不完整，如需观看完整动画，可以去原网站。
这些教程在详细介绍完选择排序的原理之后，往往直接就给出了代码。
但对于初学者，特别是少儿初学者，即使明白了原理，要理解代码，还是有一定难度。
所以，下面将一步步详解介绍选择排序的代码。
首先，我们先构造一个无序的数列：list1
import randomlist1 = random.sample(range(0,100),15)
n = len(list1)
不着急对list1进行排序，我们先完成第1步：从list1里找到最小的元素，并把它放到第1位。
第1步：找到最小的，放到第1位
假设列表里的元素就如下图。
人的思维方式：最小的不就是2吗？把它和第1位的3换一下不就好了吗？
电脑的工作方式：但是在电脑里，前面介绍过，列表就如下图一样。列表里的元素是不可见的。
因为不可见，所以必须通过循环，逐一查看列表里的每一个元素。
不妨先假设第1个元素就是最小的元素。
那么在循环的过程中，就可以逐一用当前的元素和最小的元素做比较，如果当前元素比最小的元素小，那么最小元素换成当前元素。
minNum = list1[0]
for j inrange(n):
if list1[j] < minNum:
minNum = list1[j]
不过，我们需要思考：是应该找最小的元素，还是找最小元素的位置。
上面的程序执行完之后，minNum = 2，找到了最小的元素，可是你不知道2在列表里的位置，怎么和第1位的元素互换呢？
所以，我们应该找的是最小元素的位置。
minPos = 0
for j inrange(n):
if list1[j] < list1[minPos]:
minPos = j
找到最小元素的位置后，就可以和第1位的元素互换了。
要注意的是，不要写成下面这样。
list1[0] = list1[minPos]
list1[minPos] = list1[0]
可以写成
temp = list1[0]
list1[0] = list1[minPos]
list1[minPos] = temp
或者用前面学习过的多变量赋值的知识，写成
list1[0],list1[minPos] = list1[minPos],list1[0]
所以，第1步，找最小元素并放到第1位的完整程序如下。
minPos = 0
for j inrange(n):
if list1[j] < list1[minPos]:
minPos = j
list1[0],list1[minPos] = list1[minPos],list1[0]
可以验证一下。
依次类推
找第2小的：
minPos = 1
for j inrange(1,n):
if list1[j] < list1[minPos]:
minPos = j
list1[1],list1[minPos] = list1[minPos],list1[1]
找第3小的：
minPos = 2
for j inrange(2,n):
if list1[j] < list1[minPos]:
minPos = j
list1[2],list1[minPos] = list1[minPos],list1[2]
……
我们发现，做每一步，不同的仅仅是开始的位置，其它代码完全相同。
所以，我们可以把它放到一个外层循环里。
如下是完整的程序：
外层 i 从 0 循环到 n。
当 i 循环到某个位置时。
内层 j 从 i 循环到n，也即寻找当前位置往后的最小元素，并换到当前位置。
import random
list1 = random.sample(range(0,100),15)
n = len(list1)
for i in range(n):
minPos = i
for j in range(i,n):
if list1[j] < list1[minPos]:
minPos = j
list1[i],list1[minPos] = list1[minPos],list1[i]
print(list1)
冒泡排序
冒泡排序的过程如下动画所演示。
1.从第1个元素开始，每次比较相邻的2个元素，如果第1个比第2个大，就交换它们的位置。
2.第1次遍历完成之后，最大的元素就会被交换到最后。（如动画里的50）
3.继续从第1个元素开始，重复之前的行为。
4.第2次遍历完成之后，第2大的元素就会被交换到倒数第2的位置。（如动画里的48） ……
给定一个无序的列表，用冒泡排序算法对它进行排序。
import random
list2 = random.sample(range(0,100),9)
n = len(list2)
举报/反馈
0
0
收藏
分享
