经典排序算法——冒泡排序及其优化（python代码实现）

        冒泡排序是排序算法中非常经典的一种交换排序算法，思想比较简单，容易理解和实现，一般是初学者最早接触的一种排序算法。

        之所以称之为冒泡排序，就是因为在排序的过程中，像汽水冒泡一样，元素会逐渐一步一步的上浮到最顶端（最后）。

        通过一趟趟地比较，每一趟确定一个剩余待排元素中的最大或最小元素，直到所有元素有序。具体来说，在每一趟排序中，元素两两比较，从起始位置开始，当前元素与后一个元素比较，若这两个元素符合有序，则忽略并后移一个元素继续向后比较，若不符合则先交换元素，然后后移一个元素继续向后比较，直到本趟结束。

性能特点

待排数列：

升序排序 

第一趟排序：

第二趟排序：

第三趟排序：

第四趟排序：

第五趟排序：

第六趟排序：

 有序数列：

        其实，冒泡排序算法还可以做进一步的优化使其效率更高，下面我们来举一个比较极端的例子。

        现在存在一个待排序序列，其已经是一个有序的序列，如下：

那么此时我们的冒泡排序算法将会进行如下排序操作操作：

        我们可以很清晰的看出，当我们的待排序列已经是有序的时候，冒泡排序算法还是会进行一定的无用功操作，这样就降低了算法的效率，因此可以对基本的冒泡排序进行一定的改进：

        我们设置一个标志位来记录，如果我们进行一趟排序操作没有进行任何元素交换，那么就说明待排序列已经是有序的了，因此我们就可以提前结束排序操作。

python代码

# 冒泡排序
def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i): # 每排序一趟就少一个元素需要进行比较（后面的元素已经有序）
            #if arr[j] > arr[j + 1]:  # 升序
            if arr[j] < arr[j + 1]:   # 降序
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


if __name__=="__main__":
    nums = [1, 42, 65, 876, 34, 656, 4, 6757, 89, 24, 65, 42]
    print("start:", nums)
    print("冒泡 :", bubbleSort(nums))

优化 python代码

# 冒泡排序
def bubbleSort(arr):
    for i in range(1, len(arr)):
        flag = False  # 设置标志位，判断当前趟次是否有元素交换
        for j in range(0, len(arr)-i): # 每排序一趟就少一个元素需要进行比较（后面的元素已经有序）
            #if arr[j] > arr[j + 1]:  # 升序
            if arr[j] < arr[j + 1]:   # 降序
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True  # 记录发生了交换
        if flag==False: # 如果元素未发生交换，说明待排序列已经是有序序列，则提前结束排序
            break
    return arr


if __name__=="__main__":
    nums = [1, 42, 65, 876, 34, 656, 4, 6757, 89, 24, 65, 42]
    print("start:", nums)
    print("冒泡 :", bubbleSort(nums))