算法の LowLow三人行

lowb三人组

• 冒泡
• 选择
• 插入
• 算法关键点：有序区，无序区

冒泡：

• 首先，列表每两个相邻的数，如果前面的比后面的大，那么交换这两个数。
• 关键点：趟，无序区

# 如果冒泡排序中，执行了一趟而没有交换位置，那么它已经是有序状态，可以直接结束算法。
def bubble_sort(li):
    for i in range(len(li)-1):
        # i代表趟
        # 第 i 趟时：无序区range(len(li)-i) 
        # 因为最后一个是固定的不需要再比较再挪动so -1
        flag = 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]
                flag = True
        if not flag:
            return

选择：

• 在一堆大小不一的球中，进行选择(以从小到大，先选最小球为例)。
  1. 选择一个基准球。
  2. 将剩下的球与基准球比较如果小于基准求，则交换位置。
  3. 第一轮过后，获得最小的球。
  4. 执行123步。

时间复杂度：O(n^2).  需要进行的比较次数为第一轮 n-1，n-2....1, 总的比较次数为 n*(n-1)/2

# 与冒泡只有一点点差别
import random
def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i 
        for j in range(i+1,len(li)-i-1):
            if li[j] > li[min_loc]:
                min_loc = j
            else:
                li[i],li[min_loc] = li[min_loc],li[i]

插入

• 思路：
  1. 列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
  2. 每次从无序区拿出一个元素，插入到有序区的位置，直到无序区变空。
  3. 在有序区，它也会依次去比较，把最小的排在最前面位置。
• 时间复杂度:

o(n^2)

# 思路：列表被分为有序去和无序区。最初有序区只有一个元素。
#      每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。

from timewrap import exe_time
import random

@exe_time
def insert_sort(li):
    for i in range(1,len(li)):
        # i 是无序区第一张牌，默认0位有序
        tmp = li[i] # tmp就是无序区的第一个元素,即摸到的牌
        j = i - 1   # 有序区的最后一个元素的索引
        while j >= 0 and tmp < li[j]:
            # j >= 0  如果没有这句，index 会 outof。
            # 因为我要把最小的值放在最前面，它是通过和前面一个值比较来的位置。
            # 但是第一个元素前面没有值了，所以只能通过判断来让最小的值放在索引为0的位置上。
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp


# n 是我拿到的值，
# J 是n前面的一个值，就是要比的值。
# 其实你看似放在某某前面，但其实是放在某某某的后面。
li = list(range(100))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)

到这，排序lowB三人组完结。💃🏻💃🏻💃🏻

下一篇写快速排序