Py008-01-04排序

排序

  • 排序：将一组‘无序’的记录序列调整为‘有序’的记录列表

  • 列表排序
    输入：列表
    输出：有序列表

  • 生序和降序

  • 内置排序函数：sort()

常见排序

low B 三人组

  • 冒泡排序
  • 选择排序
  • 插入排序

NB 三人组

  • 快速排序
  • 堆排序
  • 归并排序

其他排序

  • 希尔
  • 计数
  • 基数

冒泡排序 (Bubble sort) 体育委员两两比较法

  • 列表每两个相邻的数，如果后面的比前面的大，则交换这两个数
  • 一趟排序完成后，则无序区减少一个数，有序区增加一个数
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
初始列表
5 2 3 1 4

第一趟 
    5 2 3 1 4
    第一次
    2 5 3 1 4
    第二次
    2 3 5 1 4
    第三次
    2 3 1 5 4
    第四次
    2 3 1 4 5  此时最大的数5已经站定了

第二趟
    2 3 1 4
    第一次
    2 3 1 4 
    第二次
    2 1 3 4
    第三次
    2 1 3 4  此时最大的数4已经站定了

第三趟
    2 1 3
    第一次
    1 2 3
    第二次
    1 2 3    此时最大的数3已经站定了

第四趟
    1 2
    第一次
    1 2      此时最大的数2已经站定了

最后 1 2 3 4 5

冒泡排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def bubble_sort(li):
    for i in range(len(li)-1): # 第几趟
        for j in range(len(li) - i - 1):
            if li[j] > li[j+1]:# 大就交换
                li[j],li[j+1] = li[j+1],li[j]
        print(li)

li = [3,2,4,6,5,1,8,7,9]

bubble_sort(li)

'''
结果如下
[2, 3, 4, 5, 1, 6, 7, 8, 9]
[2, 3, 4, 1, 5, 6, 7, 8, 9]
[2, 3, 1, 4, 5, 6, 7, 8, 9]
[2, 1, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

时间复杂度：O(n*n)

冒泡排序的优化

如果一趟列表中没有发生交换则代表已经排好序了 则后面无需进行那么多次的比较了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def bubble_sort2(li):
    for i in range(len(li)-1): # 第几趟
        exchange = False
        for j in range(len(li) - i - 1):
            if li[j] > li[j+1]:# 大就交换
                li[j],li[j+1] = li[j+1],li[j]
                exchange = True
        print(li)
        if not exchange:
            return

li = [3,2,4,6,5,1,8,7,9]

bubble_sort2(li)

'''
[2, 3, 4, 5, 1, 6, 7, 8, 9]
[2, 3, 4, 1, 5, 6, 7, 8, 9]
[2, 3, 1, 4, 5, 6, 7, 8, 9]
[2, 1, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
'''