冒泡排序--python(详解)

对于一个数组:[4, 6, 3, 9]

第一轮：

第一次比较(4<6)：两数不用进行交换 数组不变为[4, 6, 3, 9]

第二次比较(6>3)：两数进行交换 得到一个新数组[4, 3, 6, 9]

第三次比较(6<9)：两数不用进行交换 数组不变为[4, 3, 6, 9]

存在一个数归位 即9

第二轮：

第一次比较(4>3)：两数进行交换 得到一个新数组[3, 4, 6, 9]

第二次比较(3<6)：两数不用进行交换 数组不变为[3, 4, 6, 9]

存在一个数归位 即6

第三轮：

第一次比较(3<4)：两数不用进行交换 数组不变为[3, 4, 6, 9]

存在一个数归位 即4

然后得到一个升序排序的数组[3, 4, 6, 9] 即为结果

结论：

如果前提条件为外层循环从1开始计数的话 那么就有以下结论：

总轮数 = 元素总个数 - 1

当前轮数(i)对应的总比较次数 = 元素总个数 - i

但是一般来说外层循环从0开始计数 所以就有以下结论：

总轮数 = 元素总个数 - 1

当前轮数(i)对应的总比较次数 = 元素总个数 - i - 1

下列是冒泡排序的图解：

冒泡排序图解.xmind

接下来是冒泡排序的代码实现：

# 这是冒泡排序的简易版本
# 定义一个函数 用于对原始数组进行冒泡排序 接收一个参数 即原数组
def bubbleSort(arr):
    # 定义两层循环 外层循环表示轮数 内层循环表示比较次数
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            # 如果存在相对靠前元素大于相对靠后元素的情况 那么就请交换两元素
            if arr[j] > arr[j + 1]:
                # 交换两元素
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
if __name__ == '__main__':
    # 定义一个数组
    arr = [4, 6, 3, 9]
    # 打印排序前的数组
    print(arr)
    # 调用冒泡排序函数 对原始数组进行升序排序
    bubbleSort(arr)
    # 打印排序后的数组
    print(arr)

但是上述代码其实存在三处需要优化的地方：

1.针对特殊情况 没有处理机制

2.当冒泡排序进行到中间阶段的时候 就已经完成升序排序了

3.冒泡排序中某个阶段的数组是由前面的无需部分和后面的有序部分组成的 那么我们排序的范围不是整个范围 而是前面的无序部分

所以经过优化后的数组如下所示：

# 这是冒泡排序的优化版本
# 定义一个函数 用于对原始数组进行冒泡排序 接收一个参数 即原数组
def bubbleSortOptimization(arr):
    # 定义一个变量 用于记录边界 初始值为len(arr)-0-1 即len(arr)-1
    sortBorder = len(arr) - 1
    # 定义一个变量 用于记录最后进行交换元素中的相对靠前元素 初始值为0
    lastExchangeIndex = 0
    # 针对特殊情况 需要由特殊的处理机制
    if arr == None or len(arr) < 2:
        return
    # 定义两层循环 外层循环表示轮数 内层循环表示比较次数
    for i in range(len(arr) - 1):
        # 定义一个变量 用于判断内层循环是否存在两数交换的情况 初始值为True
        isSort = True
        for j in range(sortBorder):
            # 如果存在相对靠前元素大于相对靠后元素的情况 那么就请交换两元素
            if arr[j] > arr[j + 1]:
                # 当存在相对靠前元素大于相对靠后元素的情况时 将isSort变量赋值为False
                isSort = False
                # 交换两元素
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                # 为lastExchange变量重新赋值 
                lastExchangeIndex = j
        # 如果内层循环不存在两数交换的情况 那么就跳出循环
        if isSort:
            break
        # 为边界变量重新赋值
        sortBorder = lastExchangeIndex
if __name__ == '__main__':
    # 定义一个数组
    arr = [4, 6, 3, 9]
    # 打印排序前的数组
    print(arr)
    # 调用冒泡排序函数 对原始数组进行升序排序
    bubbleSortOptimization(arr)
    # 打印排序后的数组
    print(arr)