LowB三人组（冒泡排序，插入排序，选择排序）（数据结构课设篇1，python版）（排序综合）

本章博客主要详细讲解一下LowB三人组排序，为什么叫LowB三人组呢？因为他们的时间复杂度都为O（n^2）。下篇博客会再讲解NB三人组（堆排序，归并排序和快速排序），第三篇博客会讲解其他排序（基数排序，希尔排序和桶排序）

ps: random和time库的用法在冒泡排序里讲解。

这也是数据结构的课设之一，总计三篇博客（大部分的排序都进行了讲解），实验内容如下：

概念：

"LowB三人组"指的是冒泡排序、插入排序和选择排序，它们被称为"LowB"是因为它们的时间复杂度较高，性能较差，不适合处理大规模数据。它们的时间复杂度都是O(n^2)，在大规模数据下性能表现较差。

NB三人组排序是堆排序、归并排序和快速排序，这是因为这些排序算法在实现上比较复杂，但在大规模数据上有较好的性能。堆排序、归并排序和快速排序都适用于大规模数据，它们具有较好的平均时间复杂度和空间复杂度，时间复杂度都为O(n log n)。

实验内容

利用随机函数产生N个随机整数（20000以上）,对这些数进行多种方法进行排序。
要求：

1. 至少采用四种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
2. 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比，），找出其中两种较快的方法。

下面就开始讲解。

冒泡排序：

先看下冒泡排序的过程：

如图所示为每一趟冒泡排序后的状态，每一趟冒泡排序选从第一个数开始遍历，比较两数大小，把大的数和小的数交换位置，每一趟冒泡排序都能选出一个最大值放在最后。

代码及详细注释

这里设置了个监视哨，作用是如果数组有序，则只需遍历一遍数组就会结束，大大减少了运行时间。

import random
import time
def bubble_sort(li):
    for i in range(len(li) - 1):  # 第i趟
        exchange = False  # 设置交换标志位为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  # 将交换标志位置为True
        if not exchange:  # 如果一趟排序中没有发生交换
            return li  # 直接返回列表，排序完成

li = [random.randint(1, 100000000) for i in range(10000)] # 生成10000个从1到1亿的随机数
start = time.time()  # 开始计时
print(li)
bubble_sort(li)
print(li)
end = time.time()  # 结束计时
print('运行时间：%s Seconds' % (end - start))

这里引用了random和time库，一个用来生成随机数，randint()用法是生成整数，time用来计时程序运行时间，类型为浮点型，精度较高。

运行结果如下（数组太大就只放计时的结果）：

这里运行结果每次都会有变化，主要看生成随机数的排序情况。但冒泡排序执行时间都会在几秒内（较慢）

插入排序：

一样，先看一下插入排序的过程：

插入排序其实跟你打牌时摸牌一样，打斗地主摸牌时摸到一张新牌就给它插入到已排好序的牌里。插入排序就是这个过程，刚开始时选择第一个数排序，然后再选下一个新数插入排序如此往复，直到所有数组有序。

代码及详细注释：

import random
import time
def sort(li):
    for i in range(1, len(li)):  # 从第二张牌开始摸牌
        tmp = li[i]  # 摸到的牌
        j = i - 1  # 手里的牌的最后一张的下标
        while j >= 0 and li[j] > tmp:  # 如果手里的牌比摸到的牌大
            li[j + 1] = li[j]  # 将手里的牌往后移动一位
            j -= 1  # 继续和前一张手里的牌比较
        li[j + 1] = tmp  # 将摸到的牌插入到正确的位置

li = [random.randint(1, 100000000) for i in range(10000)]
start = time.time()
print(li)
sort(li)
print(li)
end = time.time()
print('运行时间：%s Seconds'%(end-start))

运行结果：

选择排序：

选择排序的过程：

从图中就可以看出来什么是选择排序，选择排序就是每趟选取最小的元素与它最终应该在的位置上的元素交换位置，直到数组有序。

代码及详细注释：

import random
import time
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]  # 将最小值和当前位置交换位置
li = [random.randint(1, 100000000) for i in range(10000)]
start = time.time()
print(li)
select_sort(li)
print(li)
end = time.time()
print('运行时间：%s Seconds'%(end-start))

运行结果：

总结：

LowB三人组还是比较简单和好理解的，接下来的博客会讲解NB三人组（堆排序，归并排序和快速排序），第三篇博客会讲解其他排序（基数排序，希尔排序和桶排序） 。