LOW B 排序三人组

为什么是LOW B 排序三人组呢, 看到最后就知道了

1.冒泡排序

首先要讲的是冒泡排序

冒泡排序的原理是从第一个元素开始与后面的每个元素进行比较

比较一个判断是否符合交换的条件

交换过程如下图:

这里要注意的是排序的趟数和要交换的元素,因为冒泡排序是按每两个元素比较交换来排序的,而且每一次排序都会固定一个元素,所有假如说有五个元素那他就需要进行4趟排序,这里可以好好理解一下

def bubble_sort_1(li):
    for i in range(len(li) - 1):  #第i趟
        for j in range(len(li) - 1 - i):  #第j个元素
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
        print(li)

import random
​
li = [random.randint(1, 10) for i in range(10)]
print(li)
bubble_sort_1(li)

这里我们要优化一下就是如果我冒泡排序三次我的顺序就已经排好了,那我后面的操作相当于重复了,那么我们就要在每一趟排序前设置一个变量,然后每次交换位置我们将变量改变,如果我们的变量没有变我们就跳过这次趟排序

def bubble_sort_2(li):
    for i in range(len(li) - 1):  #第i趟
        exchange = False
        for j in range(len(li) - 1 - i):  #第j个元素
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        print(li)
        if not exchange:
            return

li = [9, 8, 7, 1, 2, 3, 4, 5, 6]
print(li)
bubble_sort_2(li)

2.简单排序

简单排序的思想是取最小

第一种很好理解就是取出最小的元素然后将最小的那个元素放到另一个列表中,再在原来的列表中删除最小的元素

但是这个有个弊端就是你的列表中不能有相同的元素,而且这种方法的内存比较高,因为你有新建了一个列表

def select_sort_simple(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new

li = [3, 2, 4, 1, 5, 6, 7, 8, 9]
print(select_sort_simple(li))

那么第二种方法是怎样的呢

首先和冒泡排序一样我们要进行len(li)-1趟排序,每一趟排序开始前我们都会将这次排序的第一个元素的下标用min_loc来存,然后从这个元素的后面一个元素开始进行比较如果后面的元素比我们min_loc 元素小,我们就交换,并更换min_loc 的值.

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]
    return li

li = [3, 2, 4, 1, 5, 6, 7, 8, 9]
print(select_sort(li))

3.插入排序

插入排序的思想和我们打扑克差不多, 就是你小的牌应该在你大的牌的前面

一边摸牌，一边理牌，将摸到的牌放到已经整理好的牌中。假如我们手上已经有6，7，9，10，手上摸到的是8。处理方式就是先拿8和10比较，发现8小于10，再拿8和前面的9比较，发现8也是小于9，于是再和前面的7比，发现8大于7，最终就找到8应该放在7和9之间。

那么按照这个思想我们从第二个元素开始进行排序,第二个元素和它后面的元素我们看成我们的牌堆,我们从里面取牌给他排序.

def insert_sort(li):
    for i in range(1, len(li)):  #i 表示当前取到的数下标
        tmp = li[i]
        j = i - 1  # j 指要取到的这个数的前一个数的下标
        while li[j] > tmp and j >= 0:  # 找到要插入的位置
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = tmp
        # print(li)
    return li
​

li = [3, 2, 4, 1, 5, 7, 9, 6, 8]
print(li)
print(insert_sort(li))

那么为什么叫做LOW B 三人组呢因为他们的时间复杂度都是O(n^2),时间复杂度都很高,那么下次我们来说NEW B 三人组.