冒泡排序与选择排序

跟随实际的 Python 执行过程，观察列表的变化。

1def bubble_sort(items):2    for end in range(len(items) - 1, 0, -1):3        swapped = False4        for j in range(end):5            if items[j] > items[j + 1]:6                items[j], items[j + 1] = items[j + 1], items[j]7                swapped = True8        if not swapped:9            break10    return items

end 之后的后缀已经排好序。提前终止标志使最佳情况的时间复杂度为 O(n)；平均与最坏情况为 O(n²)。此原地实现使用 O(1) 辅助空间。

跟随实际的 Python 执行过程，观察列表的变化。

1def selection_sort(items):2    for start in range(len(items) - 1):3        smallest = start4        for j in range(start + 1, len(items)):5            if items[j] < items[smallest]:6                smallest = j7        items[start], items[smallest] = items[smallest], items[start]8    return items

找出剩余元素中的最小值，再将其交换到正确位置。start 之前的前缀已排序。即使输入已有序，比较的时间复杂度仍为 O(n²)。辅助空间为 O(1)。