Polar Snow Documentation

花有重开日 人无再少年

Python冒泡 选择 插入排序算法详解

发表于 分类于 ， Disqus：

冒泡排序

冒泡排序的原理是两个元素相邻的元素进行比较，小的数放在前面，大的数放在后面。

第一次排序：首先比较第1个数字和第2个数字，小数放前，大数放后；然后比较第2个数和第3个数，小数放前，大数放后……以此类推，找到倒数第二个数字和最后一个数字进行比较，首次排序会将队列中最大的数字放在最后一位

第二次排序：还是从第1位开始和第2位比较，小数放前，大数放后……一直比到倒数第二个数（因为倒数第一个数在第一次排序中已经确定是最大值了）

以此类推，重复以上过程，直到最终排序完毕。

由于排序过程中，永远是小数往前放，大数往后放，类似于气泡上升，所以被称之为冒泡排序，接下来通过Python代码来演示冒泡排序的过程

1
2
3
4
5
6
7
8
9
10
11
12
# 首先来直观感受一下冒泡排序的代码
l = [34, 16, 78, 2, 37, 56, 5]

for j in range(len(l) - 1, 0, -1):
   for i in range(j):
        if l[i] > l[i+1]:
            l[i], l[i+1] = l[i+1], l[i]
            
print(l)

------------
[2, 5, 16, 34, 37, 56, 78]

接下来我们来一步一步实现上面的代码

首次循环

需要相邻两个数进行比较，小值放前，大值放后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 首先需要确定循环多少次
# 循环到每个元素需要 len(l) 次, 对应遍历的索引下标是 range(len(l))
# 由于是两两比较，最后一次比较，取得的是倒数第二个 len(l) - 2 这个元素，去和最后一个元素 len(l) - 1 进行比较
# 所以实际需要遍历的次数比这个列表的总长度要少1
# 而range有从0开始且左闭右开的特性，所以在range中只需-1，至此可以确定需要遍历下表的索引就是 range(len(l) - 1)
for i in range(len(l) - 1):
	# 里面的判断很简单，根据冒泡算法的核心原理
	# 判断当前元素和下一个元素的大小，小放前，大放后
    if l[i] > l[i + 1]:
    	# 如果当前元素大于下一个元素，则交换两个值得位置
        l[i], l[i + 1] = l[i + 1], l[i]

# 至此，完成了冒泡排序的第一次循环
# l列表中有7个元素，则len(l) == 7
# 实际只需遍历6个元素即可 len(l) - 1 == 6
# 根据得到的需要遍历的总元素个数，去生成一串索引遍历数组
# range(6) --> 0 1 2 3 4 5 从0开始且左闭右开
# 这样就取到了需要遍历元素的索引
print(l)

------------
[16, 34, 2, 37, 56, 5, 78]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 再来看个详细输出每次交换信息的版本
for i in range(len(l) - 1): 
    print('比较:', l[i], l[i+1])
    if l[i] > l[i + 1]: 
        l[i], l[i + 1] = l[i + 1], l[i]
        print('交换后的数组:', l)
        
print(l)

------------
比较: 34 16
交换后的数组: [16, 34, 78, 2, 37, 56, 5]
比较: 34 78
比较: 78 2
交换后的数组: [16, 34, 2, 78, 37, 56, 5]
比较: 78 37
交换后的数组: [16, 34, 2, 37, 78, 56, 5]
比较: 78 56
交换后的数组: [16, 34, 2, 37, 56, 78, 5]
比较: 78 5
交换后的数组: [16, 34, 2, 37, 56, 5, 78]
[16, 34, 2, 37, 56, 5, 78]

依次循环

首次循环之后，已经选出了列表中的最大值并放到了最后一位，接下来要做的是再次循环，选择第二大的数字放在倒数第二位

而上面已经实现了首次循环，现在我需要在这次基本循环外，再套上一层循环，由外层循环控制内层的循环总共循环6次。这个表达式很好写range(len(l) - 1) 就能得到6次循环，得到的结果是0 1 2 3 4 5, so, 我可以对代码做出如下修改即可完成冒泡排序

1
2
3
4
5
6
7
8
9
for j in range(len(l) - 1): 
    for i in range(len(l) - 1): 
        if l[i] > l[i + 1]: 
            l[i], l[i + 1] = l[i + 1], l[i]
            
print(l)

------------
[2, 5, 16, 34, 37, 56, 78]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# 来感受下带详细输出的版本
for j in range(len(l) - 1): 
    print('---第', j, '次循环---')
    for i in range(len(l) - 1): 
        print('比较:', l[i], l[i+1])
        if l[i] > l[i + 1]: 
            l[i], l[i + 1] = l[i + 1], l[i]
            print('交换后的数组:', l)
            
print(l)

------------
---第 0 次循环---
比较: 34 16
交换后的数组: [16, 34, 78, 2, 37, 56, 5]
比较: 34 78
比较: 78 2
交换后的数组: [16, 34, 2, 78, 37, 56, 5]
比较: 78 37
交换后的数组: [16, 34, 2, 37, 78, 56, 5]
比较: 78 56
交换后的数组: [16, 34, 2, 37, 56, 78, 5]
比较: 78 5
交换后的数组: [16, 34, 2, 37, 56, 5, 78]
---第 1 次循环---
比较: 16 34
比较: 34 2
交换后的数组: [16, 2, 34, 37, 56, 5, 78]
比较: 34 37
比较: 37 56
比较: 56 5
交换后的数组: [16, 2, 34, 37, 5, 56, 78]
比较: 56 78
---第 2 次循环---
比较: 16 2
交换后的数组: [2, 16, 34, 37, 5, 56, 78]
比较: 16 34
比较: 34 37
比较: 37 5
交换后的数组: [2, 16, 34, 5, 37, 56, 78]
比较: 37 56
比较: 56 78
---第 3 次循环---
比较: 2 16
比较: 16 34
比较: 34 5
交换后的数组: [2, 16, 5, 34, 37, 56, 78]
比较: 34 37
比较: 37 56
比较: 56 78
---第 4 次循环---
比较: 2 16
比较: 16 5
交换后的数组: [2, 5, 16, 34, 37, 56, 78]
比较: 16 34
比较: 34 37
比较: 37 56
比较: 56 78
---第 5 次循环---
比较: 2 5
比较: 5 16
比较: 16 34
比较: 34 37
比较: 37 56
比较: 56 78
[2, 5, 16, 34, 37, 56, 78]

上面已经实现了对一个数组进行冒泡排序，但是还有一个缺陷，就是每次内部循环都换循环6次，而通过冒泡算法的核心原理我们已经得知，在每次循环中都会选出最大的数字依次从后往前放置，那么，也就是说，内侧循环的循环规律只要满足分别range6 5 4 3 2 1即可拿到最终的排序结果，请接着往下看

优化调整

前面的分析得出，首次遍历不需要遍历到最后一位，因为是前一位和后一位去比，所以只需遍历到倒数第二位，与倒数第二位+1的元素进行比较就行啦

当首次循环结束后，最后一位已经确定是最大，不需要遍历，根据前面的规律，首次排序后的数组倒数第二位也不需要遍历，因为会有倒数第三位主动与之比较，所以拿上面的数组举例🌰，得到的规律是，数组长度为7，内层循环第一次需要循环6次，第二次需要循环5次，第三次需要循环4次，第四次需要循环3次，第五次需要循环2次，第六次需要循环1次，退出。

我们再来找一下规律（拿首次循环的情况举例🌰）：

  • 内层循环需要的range参数是6, 由len(l) - 1得出0 1 2 3 4 5

  • 外层循环需要的range参数也是6，也由len(l) - 1得出0 1 2 3 4 5

内层循环需要6，但是外层循环range(6)之后得到的队列是0 1 2 3 4 5,我们只需让range从大往小取值即可range(6, 0, -1)取到得值即为6 5 4 3 2 1,正好可以拿到内层循环用，于是，可以做出如下修改

1
2
3
4
5
6
7
8
9
10
11
第一次循环
外层 for j in 6 5 4 3 2 1
	内层 range(6) ---> 0 1 2 3 4 5
第二次循环
外层 for j in 5 4 3 2 1
	内层 range(5) ---> 0 1 2 3 4
第三次循环
外层 for j in 4 3 2 1
	内存 range(4) ---> 0 1 2 3
...
以此类推
1
2
3
4
5
6
7
8
9
10
# 最终代码实现
for j in range(len(l) - 1, 0, -1):
    for i in range(j):
        if l[i] > l[i+1]:
            l[i], l[i+1] = l[i+1], l[i]

print(l)

------------
[2, 5, 16, 34, 37, 56, 78]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 详细输出版
for j in range(len(l) - 1, 0, -1):
    print('---第', j, '次循环---')
    for i in range(j):
        print('比较:', l[i], l[i+1])
        if l[i] > l[i+1]:
            l[i], l[i+1] = l[i+1], l[i]
            print('交换后的数组:', l)

print(l)

------------
---第 6 次循环---
比较: 34 16
交换后的数组: [16, 34, 78, 2, 37, 56, 5]
比较: 34 78
比较: 78 2
交换后的数组: [16, 34, 2, 78, 37, 56, 5]
比较: 78 37
交换后的数组: [16, 34, 2, 37, 78, 56, 5]
比较: 78 56
交换后的数组: [16, 34, 2, 37, 56, 78, 5]
比较: 78 5
交换后的数组: [16, 34, 2, 37, 56, 5, 78]
---第 5 次循环---
比较: 16 34
比较: 34 2
交换后的数组: [16, 2, 34, 37, 56, 5, 78]
比较: 34 37
比较: 37 56
比较: 56 5
交换后的数组: [16, 2, 34, 37, 5, 56, 78]
---第 4 次循环---
比较: 16 2
交换后的数组: [2, 16, 34, 37, 5, 56, 78]
比较: 16 34
比较: 34 37
比较: 37 5
交换后的数组: [2, 16, 34, 5, 37, 56, 78]
---第 3 次循环---
比较: 2 16
比较: 16 34
比较: 34 5
交换后的数组: [2, 16, 5, 34, 37, 56, 78]
---第 2 次循环---
比较: 2 16
比较: 16 5
交换后的数组: [2, 5, 16, 34, 37, 56, 78]
---第 1 次循环---
比较: 2 5
[2, 5, 16, 34, 37, 56, 78]

打完收工~~

效率分析

  • 稳定
  • 空间复杂度O(1)
  • 时间复杂度O(n2)
  • 最差情况：反序，需要交换n*(n-1)/2个元素
  • 最好情况：正序，不需要交换元素O(n)

插入排序

插入排序和冒泡排序非常像，和冒泡的区别在于，在冒泡中，相邻两个值进行比较，只要后面的数比前面的数大就交换位置；而插入排序每次假设第0索引的元素是最大值，去和队列中剩余所有的元素进行比较，但是插入排序不会实际去交换两个数的位置，而是会保存最大的那个值得索引，比到最后时，将最大值插入到列表的最后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 先感受下代码
l = [34, 16, 78, 2, 34, 56, 5]
for i in range(len(l) - 1, 0, -1):
    maxindex = 0 
    for j in range(1, i+1):
        if l[j] > l[maxindex]:
            maxindex = j 
    l[i], l[maxindex] = l[maxindex], l[i]
    
print(l)

------------
[2, 5, 16, 34, 34, 56, 78]
  • 外层循环和冒泡的没有任何区别，那此例来说都是取到了6 5 4 3 2 1这个队列
  • 第4行代码设置了一个最大值的索引，我假设每次第0个元素都是最大值，这一步是插入排序的核心，用来保存最大值的索引位置
  • 第5行内存循环和冒泡的有些差别
    • 为什么冒泡从0开始，而插入要指定从1开始？因为插入排序已经指定了最大值的索引的是0，插入排序会拿这个“最大值”去和每一个元素比较，所以当然要从1开始啦！！
    • 为什么以i+1结束？上面也说到了，假设的最大值索引0，要和剩余的所有的元素进行比较，包括取最后一个元素的索引进行比较，而range有左闭右开的特性，不包含右边的值，所以在这里要+1一下，才能取到最后一个值的索引。
  • 第6行，拿列表中的其他元素与“最大值”进行比较
  • 第7行，如果成立，则保存最大值的索引
  • 第8行，在整个列表遍历一次过后，maxindex的索引就是最大值，故将队列中最后一个元素与maxindex对应的元素进行调换，这样一来，每次都会把最大值依次从后往前放置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 体验下详细的信息输出
l = [34, 16, 78, 2, 34, 56, 5]
for i in range(len(l) - 1, 0, -1):
    maxindex = 0
    for j in range(1, i+1):
        if l[j] > l[maxindex]:
            maxindex = j
    l[i], l[maxindex] = l[maxindex], l[i]
    print(l, i)
    
print(l)

------------
[34, 16, 5, 2, 34, 56, 78] 6
[34, 16, 5, 2, 34, 56, 78] 5
[34, 16, 5, 2, 34, 56, 78] 4
[2, 16, 5, 34, 34, 56, 78] 3
[2, 5, 16, 34, 34, 56, 78] 2
[2, 5, 16, 34, 34, 56, 78] 1
[2, 5, 16, 34, 34, 56, 78]

插入排序相对于冒泡排序的好处是，每次内层循环结束后，不管队列的数值怎样分布，都只会有一次实际的换值操作。

效率分析

  • 稳定
  • 空间复杂度O(1)
  • 时间复杂度O(n2)
  • 最差情况：反序，需要移动n*(n-1)/2个元素
  • 最好情况：正序，不需要移动元素

选择排序

选择排序的核心思想是始终维护一个有序的队列，依次用队列中的每一个元素与后面的所有元素进行对比，小放前，大放后

例如现有如下列表：

1
l = [34, 16, 78, 2, 34, 56, 5]

选择排序算法实现：

1
2
3
4
5
用第1个元素和第2 3 4 5 6 7的元素进行对比
用第2个元素和第3 4 5 6 7的元素进行对比
用第3个元素和第4 5 6 7的元素进行对比
......
依次类推

每次对比完后，拿来对比的那个基准值都会被换成当次循环的最小值，从这里可以对比冒泡和排序

  • 冒泡是相邻两两比较，只要比前面的值小就交换位置，属于从大往小排
  • 插入排序也是相邻两两比较，每次都假设索引0为最大值，与剩余的所有元素进行比较，记录最大值的索引，把最后一个值与最大值进行交换，属于从大往小排
  • 选择排序是从小往大排，第一次取第0索引去和所有元素比较，换得最小值放到了最前面，第二次取第1索引去和所有元素比较，换得的最小值依次从前往后排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
l = [34, 16, 78, 2, 34, 56, 5]

for i in range(len(l)-1):
    print('------' * 9)
    print('待操作的列表--->', l, '操作索引--->', i)
    print('------' * 9)
    for j in range(i+1, len(l)):
        print(l[i], l[j])
        if l[i] > l[j]:
            print('调换位置%s, %s' %(l[j], l[i]))
            l[i], l[j] = l[j], l[i]
            print('调换完位置的列表--->', l)

print(l)

------------
------------------------------------------------------
待操作的列表---> [34, 16, 78, 2, 34, 56, 5] 操作索引---> 0
------------------------------------------------------
34 16
调换位置16, 34
调换完位置的列表---> [16, 34, 78, 2, 34, 56, 5]
16 78
16 2
调换位置2, 16
调换完位置的列表---> [2, 34, 78, 16, 34, 56, 5]
2 34
2 56
2 5
------------------------------------------------------
待操作的列表---> [2, 34, 78, 16, 34, 56, 5] 操作索引---> 1
------------------------------------------------------
34 78
34 16
调换位置16, 34
调换完位置的列表---> [2, 16, 78, 34, 34, 56, 5]
16 34
16 56
16 5
调换位置5, 16
调换完位置的列表---> [2, 5, 78, 34, 34, 56, 16]
------------------------------------------------------
待操作的列表---> [2, 5, 78, 34, 34, 56, 16] 操作索引---> 2
------------------------------------------------------
78 34
调换位置34, 78
调换完位置的列表---> [2, 5, 34, 78, 34, 56, 16]
34 34
34 56
34 16
调换位置16, 34
调换完位置的列表---> [2, 5, 16, 78, 34, 56, 34]
------------------------------------------------------
待操作的列表---> [2, 5, 16, 78, 34, 56, 34] 操作索引---> 3
------------------------------------------------------
78 34
调换位置34, 78
调换完位置的列表---> [2, 5, 16, 34, 78, 56, 34]
34 56
34 34
------------------------------------------------------
待操作的列表---> [2, 5, 16, 34, 78, 56, 34] 操作索引---> 4
------------------------------------------------------
78 56
调换位置56, 78
调换完位置的列表---> [2, 5, 16, 34, 56, 78, 34]
56 34
调换位置34, 56
调换完位置的列表---> [2, 5, 16, 34, 34, 78, 56]
------------------------------------------------------
待操作的列表---> [2, 5, 16, 34, 34, 78, 56] 操作索引---> 5
------------------------------------------------------
78 56
调换位置56, 78
调换完位置的列表---> [2, 5, 16, 34, 34, 56, 78]
[2, 5, 16, 34, 34, 56, 78]

效率分析

  • 不稳定
  • 空间复杂度：O(1)
  • 时间复杂度：O(n2)
  • 最坏情况：O(n2) 第一个元素为最大元素，其余元素正序，需要交换n-1个元素
  • 最好情况：O(n2) 正序，不需要交换元素