有趣的算法-冒泡排序

冒泡排序

冒泡排序是一个简单的排序算法,它重复地遍历要排序的数列,依次比较两个元素,如果前者比后者大就进行交换操作.遍历数列的循环进行直到没有再需要交换,这数列已经排序完成.算法因为越小的元素会经过交换操作慢慢浮出到数列的顶端所以得名冒泡算法.

点我看冒泡排序效果

点我用Scratch实现冒泡排序

Python求解

def bubble_sort(arr):
    """冒泡排序"""
    # 第一层for表示循环的遍数
    for i in range(len(arr) - 1):
        # 第二层for表示具体比较哪两个元素
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                # 如果前面的大于后面的，则交换这两个元素的位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
if __name__ == '__main__':

    arr = [30, 15, 26, 11, 2, 8, 9, 17]
    print(arr)
    b = bubble_sort(arr)
    print(b)
    
    
    
'''
上述排序算法存在的不足之处在于，对于已经排好序的序列仍然会进行下一次冒泡操作，尽管不会有任何的数据交换操作。
为了避免不必要的操作，程序中设计一个标志变量flag,用于标记比较过程中是否发生了交换。
在每趟交换前把flag置于0，发生了数据交换，就把变量flag的值置为1。在这一趟比较结束之后判断flag变量的值是否等于0，如果等于0，
表示已经排好序了，可以退出排序过程了，否则继续进行下一趟比较。

'''
# 改进后冒泡排序
def bubble_sort(arr):
    """冒泡排序"""
    # 第一层for表示循环的遍数
    for i in range(len(arr) - 1):
        flag=0  # 设置标记变量 
        # 第二层for表示具体比较哪两个元素
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                # 如果前面的大于后面的，则交换这两个元素的位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag=1 # 有交换就让标记变量为1 说明这趟排序有发生交换
                
        if flag==0: # 如果标志变量没有变化 说明这轮没有交换数字 数字已经有序结束循环
            break
        
            
    return arr
if __name__ == '__main__':

    arr = [30, 15, 26, 11, 2, 8, 9, 17]
    print(arr)
    b = bubble_sort(arr)
    print(b)

---

分享