Python 之排序（冒泡排序、选择排序、插入排序）

排序

一、冒泡排序

用随机数任意生成5个元素，并用冒泡排序（升序）排列。

# 冒泡排序
import random

list1 = [random.randint(1,100) for i in range(5)]       #1~99随机5个元素
print("没冒泡排序之前为：",list1)

# 冒泡排序(升序)
for i in range(len(list1) - 1):
    flag = True
    for j in range(len(list1)- i- 1):
        if list1[j] > list1[j+1]:
            list1[j], list1[j + 1] = list1[j + 1], list1[j]
            flag = False
    if flag:        #如果在内循环中一次都没有交换（即前一个元素全部大于后一个元素）
        break       #实际上列表已经是有序的了，就不需要再进行循环比较了

print("冒泡排序后：",list1)


#输入输出样例：
#没冒泡排序之前为： [48, 36, 7, 34, 10]
#冒泡排序后： [7, 10, 34, 36, 48]

二、选择排序

算法原理：
假设对列表升序排列（比冒泡排序速度快）
1、首先找到列表中的最小元素并将它和第一个元素交换。
2、找到剩余元素中，值最小的元素并和剩余列表的第一个元素交换。
3、一次类推，直到只剩一个元素。

# 选择排序
import random

list1 = [random.randint(1,100) for i in range(10)]       #1~99随机10个元素
print("没排序之前为：",list1)

# 选择排序(升序)
for i in range(len(list1) - 1):
    min_index = i
    for j in range(i + 1 , len(list1)):
        if list1[j] < list1[min_index]:                         #内循环中求出剩下元素的最小值下标
            min_index = j                                       #如果某个元素比最小值还小，那么最小值下标更新为j
    list1[i] , list1[min_index] = list1[min_index] , list1[i]

print("排序后为：",list1)


#输入输出样例：
#没排序之前为： [66, 58, 11, 15, 64, 73, 34, 93, 34, 99]
#排序后为： [11, 15, 34, 34, 58, 64, 66, 73, 93, 99]

三、插入排序

算法原理：
将一个新元素重复插入到一个已排序的子列表中（效率比冒泡排序和选择排序高）

# 插入排序
import random

list1 = [random.randint(1,100) for i in range(10)]       #1~99随机10个元素
print("没排序之前为：",list1)

# 插入排序(升序)
for i in range(1,len(list1)):
    curr_element = list1[i]                            # 记录下待插元素
    j = i - 1                                          #需要从子列表中的第一个元素开始循环
    while j>=0 and list1[j] >curr_element:             #找到子类别中比待插元素还小的位置：找到插入位置
        list1[j + 1] = list1[j]
        j -= 1
    list1[j + 1] = curr_element                        #在插入位置插入之前保存的待插元素    
    

print("排序后为：",list1)



#输入输出样例：
#没排序之前为： [40, 64, 98, 40, 30, 94, 25, 90, 29, 34]
#排序后为： [25, 29, 30, 34, 40, 40, 64, 90, 94, 98]