冒泡排序算法的实现以及优化

前言

冒泡排序核心内容：

相邻元素间两两比较，当一个元素大于右侧相邻元素时，交换它们的位置，如果是小于或等于的话就位置不变。本篇文章主要使用python语言实现最基础的冒泡排序语言以及算法优化，内容均来源于网络或书籍，侵权必删，如有疏漏欢迎评论指出！路漫漫其修远兮, 吾将上下而求索. 望与各位读者共勉!

冒泡排序算法基础v1版

def bubble_sort_v1(array=[]):
    for i in range(len(array)-1):
        for j in range(len(array)-i-1):
            if array[j] > array[j+1]:
                temp = array[j]
                array[j] = array[j+1]
                array[j+1] =temp 
my_array = list([2, 3, 3, 4, 6, 9, 7, 89])
bubble_sort_v1(my_array)
print(my_array)

冒泡排序算法优化v2版

有时经过数次排序后，整个数列已经是有序的了，但V1版还是会傻傻的执行，可以利用is_sorted作为标记，如果在本轮排序中元素有交换，说明数列无序；如果有无元素交换，则说明数列已经有序，直接跳出循环。

def bubble_sort_v2(array=[]):
    for i in range(len(array)-1):
        # 有序标记，每轮初始是True
        is_sorted =True
        for j in range(len(array)-i-1):
            if array[j] > array[j+1]:
                temp = array[j]
                array[j] = array[j+1]
                array[j+1] =temp 
                # 有元素交换的话就不是有序的，标记变为False
                is_sorted = False
        if is_sorted:
                break
            
my_array = list([2, 3, 3, 4, 6, 9, 7, 89])
bubble_sort_v2(my_array)
print(my_array)

冒泡排序算法v3版

每一轮排序后，最后或最前的元素属于有序区，其他为无序区，按照现有逻辑每一轮排序后有序区长度加一，但实际上，数列的真正的有序区可能已经不只这个长度，而有序区的多次比较是毫无意义的。

解决方案：在每轮排序后记录下最后一次元素交换的位置，该位置就是无序数列的边界，分割有序和无序区。

def bubble_sort_v3(array=[]):
    # 记录最后一次交换的位置
    last_exchange_index = 0
    # 无序数列的边界，每次只需比较到这
    sort_border = len(array)-1
    for i in range(len(array)-1):
        # 有序标记，每轮初始是True
        is_sorted =True
        for j in range(sort_border):
            if array[j] > array[j+1]:
                temp = array[j]
                array[j] = array[j+1]
                array[j+1] =temp 
                # 有元素交换的话就不是有序的，标记变为False
                is_sorted = False
                # 把无序数列的边界更新为最后一次交换元素的位置
                last_exchange_index = j
        sort_border = last_exchange_index
        if is_sorted:
                break
            
my_array = list([2, 3, 3, 4, 6, 9, 7, 89])
bubble_sort_v3(my_array)
print(my_array)