lowB三人组算法-冒泡排序-选择排序-插入排序

时间：2024-12-21 16:06:01

冒泡排序

　　时间复杂度：O(n2)  算法稳定

  • 第一趟，从第一个数开始，相邻两个数比较，大的数交换放后，交换到最后位置得出一个第一大数
  • 第二趟，从第一个数开始，相邻两个数比较，大的数交换放后，交换到倒数第二得出一个第二大数
  • 第n-1趟，最后的两个数比较得出最小数和倒数第二小数

　　代码实现点:时时比较，时时交换

def bubble_sort(li):

    for i in range(len(li)-1):  #第i趟

        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 = list(range(10000))

random.shuffle(li)

bubble_sort(li)

选择排序

　　时间复杂度：O(n2)  算法稳定？

  • 第一趟，从第一个数开始，相邻两个数比较，把小的索引位置赋值给min_index变量，循环数和当前小值比较，循环完后会得出一个最小值的索引，然后最小值位置和第一个值位置交换
  • 第一趟，从第二个数开始，相邻两个数比较，把小的索引位置赋值给min_index变量，循环数和当前小值比较，循环完后会得出一个第二小值的索引，然后最第二小值位置和第二个值位置交换
  • 第n-1趟，最后的两个数比较得出最大数和第二大数，交换

　　代码实现点：时时存储小值索引，一趟后交换

def select_sort(li):

    for i in range(len(li)-1): # i是第几趟

        min_loc = i

        for j in range(i+1, len(li)):

            if li[j] < li[min_loc]:

                min_loc = j

        li[i], li[min_loc] = li[min_loc], li[i]

        print(li)

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

print(li)

select_sort(li)

插入排序

　　时间复杂度：O(n2)  算法稳定？

  • 好比打扑克，手里牌已经有序，抓的牌只要插到顺序正确的位置上

　　代码实现点：记录手里牌的下标和抓到牌的值,利用冒泡的方式去把抓到牌往左冒

def insert_sort(li):

    for i in range(1, len(li)): #i 表示摸到的牌的下标

        tmp = li[i]

        j = i - 1 #j指的是手里的牌的下标

        while j >= 0 and li[j] > tmp:  #小于当前手牌，往左冒

            li[j+1] = li[j]

            j -= 1

        li[j+1] = tmp

        print(li)

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

print(li)

insert_sort(li)

相关文章