python冒泡排序与插入排序算法实现。

小鱼儿 2022-02-05 11:51 275阅读 0赞

# 冒泡排序算法 #

花费时间很多的一种排序算法

我们有 a1,a2…an个数据，

a1和a2比较
    如果a1>a2
    a1 a2交换位置

然后a2 和 a3 比较，一直比到 an。
    这是一次轮回，每次轮回，an都是最大（或最小，根据a1 a2的判断条件）的数

第一次排序，an已经为最大（或最小）
    
    然后进行第二次比较，第二轮 数组去掉最后一个最大的值，其他继续进行排序。
    
    理论上 要进行 n(n-1)/2 次 交换.

# 使用python 来实现这个算法
    import random
    random_list = [ random.randint(1,20) for i in range(10) ]
    
    # 有10个元素，理论上要进行10轮排序
    # 第一次排序，要进行9次交换。
    # 第二次排序，要进行8次交换
    list_len = len(random_list) - 1 # 减一，避免数组越界的问题
    
    print(random_list)
    for i in range(10):
        sort_over = True # 冒泡排序，进行优化
        for j in range(list_len  - i ):
            """ # 如果i=3,那么最后3位已经排序好了 # 只需要再排序 len - i 次即可 """
            if random_list[j] > random_list[j+1]:
                random_list[j],random_list[j+1] = random_list[j+1],random_list[j]
                # 第i轮，j和j+1 进行交换
                print(f"{i},{j},swap:",random_list)
                sort_over = False
            else:
                print(f"{i},{j},swap:",random_list)
        if sort_over == True:
            break
    print(random_list)

# 插入排序 #

插入算法，将一个新数组，插入到一个有序序列中，并使序列继续保持有序。

插入排序的话，可以将列表插入到一个空表中。
    或
    前n个是有序，后m个是待插入序列。
    4,5,7,6,9,3
    4,5,7 有序
    6,9,3 待插入
    
    刚才是的时候，把第一个元素当做有序序列，后面的是待插入序列~！

import random
    
    random_list = [random.randint(1, 20) for i in range(0, 20)]
    list_len = len(random_list)
    
    for i in range(1, list_len):
        j = 0
        is_swap = False # 优化
        # j为索引，有序
        # i为待插入的值的索引
        while j < i:  #
            # 比较 0,1 的值，从小到大排序的
            # 有序序列 从 0到j开始比较
            # 一直到 待插入的数据，比有序序列小，停止
            if random_list[j] > random_list[i]:
                is_swap = True # 除了此优化，还可以用二分查找等方法
                break
            j = j + 1  # 继续下一个比较
        if is_swap == True:
            continue
        tmp = random_list[i]  # 插入的值
        k = i  # 记录索引，一会会加减操作
        # 数据移动
        while k > j:
            random_list[k] = random_list[k - 1]
            k = k - 1
        # 插入数据
        random_list[k] = tmp
    print(random_list)