蓝桥杯排序算法之low B三人组——冒泡，插入，选择

目录

一、题目

二、分析

三、代码

一、题目

分别用冒泡，插入，选择对列表

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

进行排序

二、分析

冒泡排序：它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端（升序或降序排列）。

def bubble_sort(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
        if not exchange:
            return

1. def bubble_sort(li):：定义了一个名为 bubble_sort 的函数，接收一个列表参数 li。
2. for i in range(len(li)-1):：这个外层循环控制排序的轮数，一共需要进行 len(li)-1 轮比较。每一轮比较都会将当前未排序部分中的最大元素移动到正确的位置。
3. exchange = False：在每一轮比较开始前，设置一个标志变量 exchange 为 False，用于标记在本轮比较中是否发生了交换。
4. for j in range(len(li)-i-1):：这个内层循环用于比较相邻的元素并进行交换。在每一轮中，需要比较的元素数量逐渐减少，因为每一轮都会将一个较大的元素移动到正确的位置。
5. if li[j] > li[j+1]:：如果当前元素大于下一个元素，则进行交换。
6. li[j], li[j+1] = li[j+1], li[j]：交换两个元素的位置。
7. exchange = True：如果发生了交换，则将标志变量设置为 True。
8. if not exchange:：如果在一轮比较中没有发生交换，说明列表已经是有序的，此时可以提前退出排序过程

选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

def select_sort(li):
    for i in range(len(li)- 1):
        min_loc = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
            if min_loc != i:
                li[i], li[min_loc]=li[min_loc], li[i]

1. def select_sort(li):：定义了一个名为 select_sort 的函数，接收一个列表参数 li。
2. for i in range(len(li)- 1):：这个外层循环控制排序的轮数，一共需要进行 len(li)-1 轮比较。每一轮都会从未排序部分中找到最小的元素，并将其放到已排序部分的末尾。
3. min_loc = i：在每一轮开始时，假设当前未排序部分的第一个元素（索引为 i）是最小的元素，将其索引记录在 min_loc 变量中。
4. for j in range(i + 1, len(li)):：这个内层循环用于在未排序部分中寻找最小的元素。从 i + 1 开始，遍历到列表的末尾。
5. if li[j] < li[min_loc]:：如果当前元素小于当前认为的最小元素，则更新 min_loc 为当前元素的索引。
6. if min_loc!= i:：在找到最小元素后，如果最小元素的索引不是当前轮的起始索引 i，说明需要进行交换。
7. li[i], li[min_loc] = li[min_loc], li[i]：将最小元素与当前轮的起始元素进行交换。

插入排序：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

def insert_sort(li):
    for i in range(1, len(li)):
        j = i - 1
        tmp = li[i]
        while j >=0 and li[j] > tmp:
            li[j+1] = li[j]
            j-=1
        li[j+1] = tmp

1. def insert_sort(li):：定义了一个名为 insert_sort 的函数，接收一个列表参数 li。
2. for i in range(1, len(li)):：从第二个元素开始遍历列表，因为第一个元素被认为是已经有序的。
3. j = i - 1：设置一个指针 j，指向当前要插入元素的前一个位置。
4. tmp = li[i]：将当前要插入的元素存储在变量 tmp 中。
5. while j >= 0 and li[j] > tmp:：在已排序部分中从后向前扫描，如果当前元素大于要插入的元素，则将当前元素向后移动一位。
6. li[j + 1] = li[j]：将当前元素向后移动一位。
7. j -= 1：指针 j 向前移动一位。
8. li[j + 1] = tmp：当找到合适的位置时，将 tmp（要插入的元素）插入到该位置

三、代码

def insert_sort(li):
    for i in range(1, len(li)):
        j = i - 1
        tmp = li[i]
        while j >=0 and li[j] > tmp:
            li[j+1] = li[j]
            j-=1
        li[j+1] = tmp

def select_sort(li):
    for i in range(len(li)- 1):
        min_loc = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
            if min_loc != i:
                li[i], li[min_loc]=li[min_loc], li[i]

def bubble_sort(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
        if not exchange:
            return

li=[3,2,4,5,1,8,6,9,7]
bubble_sort(li)
print(li)
li=[3,2,4,5,1,8,6,9,7]
select_sort(li)
print(li)
li=[3,2,4,5,1,8,6,9,7]
insert_sort(li)
print(li)