Linux自动化运维——Python（12）（用Python实现冒泡排序和插入排序）

1.冒泡排序
过程： 
1. 从0位置开始，比较相邻两个数的大小，如果后面的数小于前面，则交换位置。 
2. 遍历一遍下来，最后一个数为整个数组中的最大值。 
3. 把最后一个数排除，继续比较剩下的数组。 
4. 总共比较次数为N*N，时间复杂度为O（n²）

代码实现

list=[3,5,6,32,5,6,2,35,65,22]
def bubble(list1):
    for i in range(len(list1)):
        for j in range(len(list1)-1-i):
            if list1[j+1]<list1[j]:
                list1[j],list1[j+1]=list1[j+1],list1[j]
    print(list1)
bubble(list)

2.插入排序

过程：

1.从1位置开始，比较与前面数的大小，如果小于前面的数，则交换位置，直到不再小于停止。
2.接着从2位置开始，重复这个过程。直到最后位置为止。
3.时间复杂度取决于数组的排序情况，当数组基本有序时候，复杂度很低，接近O（n）。当数组完全无序时，每个数都要经过多次移动，复杂度趋近于O（n²）。
代码实现：

def insert_sort(list):
    """插入排序"""
    n = len(list)
    for i in range(1, n):  # 未排序序列从第二个元素开始遍历
        for j in range(i, 0, -1):  # 已排序序列从后往前遍历
            if list[j] < list[j - 1]:  # 如果当前元素小于前一个元素, 则交换元素位置
                list[j], list[j - 1] = list[j - 1], list[j]
            else:  # 如果大于前一个元素, 则保持位置不变
                break

if __name__ == '__main__':
    list1 = [23,3,4,2,5,44,54,23,11]
    print("排序前:%s" % list1)
    insert_sort(list1)
    print("排序后:%s" % list1)