冒泡排序这 2 个小技巧，你了解吗？

vlambda
2020-05-24

冒泡排序这 2 个小技巧，你了解吗？

大家早上好，昨天开始推送《算法刷题日记》系列，通过做一些基础的算法题实践Python，另外中间依然会穿插Python知识点讲解，Python小例子的风格不会改变。

错过昨天的算法刷题作业帖的朋友，可点击下面查看：

昨天晚上的第一道题，目前星球内提交作业 50 多人次：

作业榜第一名目前被点赞10次，总结算法的两个优化点，代码也很简洁，确实值得赞：

提交作业的代码有人使用Python，有c/c++ ，有java，有 Lua，还有 js.

下面，在这里与大家分享下作业点赞第一名 Leven 总结的冒泡排序的两个优化点：

对应的 Python 实现代码：

刚刚我重新整理一版，完全参考球友 Leven 的实现思路：

def bubble_sort(our_list):
    lastSwapIndex, sortBoundary = 0, len(our_list) - 1
    for _ in range(len(our_list)):
        flag = True # 标记数组是否有序
        for j in range(0, sortBoundary):
            if our_list[j] > our_list[j+1]:
                our_list[j], our_list[j+1] = our_list[j +1], our_list[j]  # swap elements
                flag = False
                lastSwapIndex = j  # 标记最后一次交换位置
        sortBoundary = lastSwapIndex  # 比较一轮后，得到下一轮排序的边界
        if flag:
            break
    return our_list

考虑下面三种输入的待排序序列 our_list:

整体无序

print(bubble_sort([3,5,1,3,8,7,9,4,5]))

局部无序

print(bubble_sort([1,2,3,5,4,6,7,8,9]))

完全有序

print(bubble_sort([1,2,3,4,5,6,7,8,9]))

更多星球中其他人的提交，也能很方便的看到，就像一个班级的朋友圈，非常有营养。

你看一个不起眼的冒泡排序算法，如果细细品味起来也是很有意思的，虽然它的性能注定不好，但是我们的目的是为了训练算法思维，提升算法的分析和应用能力。从这个角度而言，我们的目的达到了。我相信坚持这样分析下去，一定可以让大家的算法思维能力变得更好。

欢迎提交你的答案到知识星球里，并完成每日打卡。打卡累积 300 天，无论你多少钱加入的星球，我们都会退还除平台外收取的所有费用，相当于免费学习，这个在看你点不点

昨日发放的166张优惠券还剩 60多张，注意：错过这波就要等一段时间了。不过无所谓，还是那句话：无论你多少钱加入的星球，我们都会退还除平台外收取的所有费用。

长按二维码

加入「算法刷题日记」

vlambda博客
学习文章列表