爆料算法刷题日记 Day1；布置 Day2 算法题

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

算法刷题起航，帮你走向下一个巅峰！

第一道题目前星球内提交作业 90 多人次：作业榜第一名上午时被点赞就11次，总结算法的两个优化点，代码也很简洁，确实值得赞：

提交作业的代码有人使用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:

1. 整体无序

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

1. 局部无序

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

1. 完全有序

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

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

并且，学习别人写的代码，也能从中发现一些问题。比如球友小六首先在群里提出来，有的代码把冒泡排序写成选择排序了，并且好多都出现这个问题。所以在此统一吆喝一声，大家看看有没有类似的错误。

区别：冒泡排序比较的一定是紧紧相邻的两个元素；而选择排序却不是每次比较紧邻的两个元素，而下面的代码就不是每次比较紧邻的两个元素，正是选择排序的基本实现。

如果还是没有很好的理解，我放上两张例子图：

下面是冒泡排序的例子：

下面是选择排序的例子：

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

Day 2 算法题：写出选择排序

参考下面的几幅图，红色表示当前找到的未排序序列中的最小值，绿色表示当前被比较的元素：

又找到一个更小的值2，重新标记它为红色：

一轮比较后，找到最小值2并标记为黄色，表示就位，继续在未排序序列中寻找最小值：

def selection_sort(our_list):
  # 补全代码
  #
  #
  return our_sorted_list

参考本文对选择排序的一些提示，在星球内记录代码及思考过程。

通过这两道基本的算法练习题，找到一些做算法题的感觉。明天Day3 开始系统学习算法知识，从什么是一个算法开始。