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

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

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

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

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

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

实验内容:

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

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

下面就开始讲解。

冒泡排序：

概念：

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个过程持续到列表已经排序完成。冒泡排序的时间复杂度为O(n^2)。冒泡排序的基本思想是：

1. 从第一个元素开始，依次比较相邻的两个元素，如果顺序不对就交换它们。
2. 继续比较相邻的元素，直到最大（或最小）的元素被交换到数列的最后一个位置。
3. 重复上述步骤，直到整个数列都变得有序。

如图：

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

代码及详细注释：

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

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)]
print(li)
start = time.time()
bubble_sort(li)
end = time.time()
print(li)
print('运行时间：%s Seconds' % (end - start))

random和time库

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

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

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

插入排序：

概念：

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的时间复杂度为O(n^2)。插入排序的基本思想是：

1. 从第二个元素开始，将其与前面的元素进行比较，找到合适的位置插入。
2. 继续对后面的元素进行插入操作，直到整个数列都变得有序。

如图：

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

代码及详细注释：

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)]
print(li)
start = time.time()
sort(li)
end = time.time()
print(li)
print('运行时间：%s Seconds'%(end-start))

运行结果：

选择排序：

概念：

选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中继续寻找最小（或最大）的元素，放到已排序序列的末尾。选择排序的时间复杂度为O(n^2)。选择排序的基本思想是：

1. 首先，在待排序的数据中找到最小（或最大）的元素，将其与第一个位置的元素交换。
2. 然后，在剩下的数据中找到最小（或最大）的元素，将其与第二个位置的元素交换。
3. 重复上述步骤，直到整个数列都变得有序。

如图：

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

代码及详细注释：

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)]
print(li)
start = time.time()
select_sort(li)
end = time.time()
print(li)
print('运行时间：%s Seconds'%(end-start))

运行结果：

总结：

LowB三人组的思路和代码还是好理解和实现的，代码的详细讲解都在注释里，接下来的博客会讲解NB三人组（堆排序，归并排序，快速排序）（数据结构课设篇2，python版）（排序综合），第三篇博客会讲解其他排序（基数排序，希尔排序和桶排序）（数据结构课设篇3，python版）（排序综合） 。