美文网首页
冒泡排序

冒泡排序

作者: 山水不在 | 来源:发表于2023-01-14 18:08 被阅读0次

    python3实现

    n个元素需要排n-1趟

    # 冒泡排序
    num_list = [
        [1, 9, 8, 5, 6, 7, 4, 3, 2],
        [1, 2, 3, 4, 5, 6, 7, 8, 9]
    ]
    nums = num_list[0]
    print(nums)
    length = len(nums)
    count_swap = 0
    count = 0
    
    # bubble sort
    for i in range(length):
        for j in range(length - i - 1):
            count += 1
            if nums[j] > nums[j + 1]:
                tmp = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = tmp
                count_swap += 1
    print(nums, count_swap, count)
    
    # 输出结果
    # [1, 9, 8, 5, 6, 7, 4, 3, 2]
    # [1, 2, 3, 4, 5, 6, 7, 8, 9] 25 36
    

    冒泡排序优化

    思路
    如 :
    [1,2,3,5,4]
    第一趟 比较交换后为:
    [1,2,3,4,5]
    即为所求
    此时当第二趟 进行比较时 无元素进行交换即可得知元素已排列好,应退出循环
    
    # 冒泡排序优化
    num_list = [
        [1, 9, 8, 5, 6, 7, 4, 3, 2],
        [1, 2, 3, 4, 5, 6, 7, 8, 9]
    ]
    nums = num_list[1]
    print(nums)
    length = len(nums)
    count_swap = 0
    count = 0
    # bubble_sort
    for i in range(length):
        flag = False
        for j in range(length - i - 1):
            count += 1
            if nums[j] > nums[j + 1]:
                tmp = nums[j + 1]
                nums[j + 1] = nums[j]
                nums[j] = tmp
                flag = True
                count_swap += 1
        if not flag:
            break
    print(nums, count_swap, count)
    
    # [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # [1, 2, 3, 4, 5, 6, 7, 8, 9] 0 8
    

    注意⚠️:flag=False的位置

    冒泡法总结

    # 冒泡法需要数据一轮轮比较
    # 可以设定一个标记判断此轮是否有数据交换发生,如果没有发生交换,可以结束排序,如果发生交换,继续下一轮排序
    # 最差的排序情况,初始顺序与目标顺序完全相反,遍历次数1,…,n-1之和n(n-1)/2
    # 最好的排序情况,初始顺序与目标顺序完全相同,遍历次数n-1
    # 时间复杂度O(n2)
    

    相关文章

      网友评论

          本文标题:冒泡排序

          本文链接:https://www.haomeiwen.com/subject/ichocdtx.html