算法理解之排序-冒泡排序

冒泡排序是一种简单的排序算法, 算法依次走访未排序的元素, 然后将相邻元素依次两两比较, 将最大的元素不断移动至最后, 直到所有元素均被排序过为止. 因为最大元素是从某个位置不断"浮"上去的, 所以称为冒泡排序

算法分析

取得相邻的两个元素, 比较两个元素大小, 若第一个元素大于第二个元素, 则交换位置(上浮).
将相邻元素位置后移一位, 再次按步骤1比较, 直至该元素比对到已排序过位置或最后位置.
重复步骤1与步骤2直到完成排序.

动图效果

冒泡排序.gif

时间复杂度与空间复杂度与稳定性

稳定性: 稳定
时间复杂度: O(N^2)
空间复杂度: O(1)

稳定性分析: 两外相邻的元素比较, 只要在前者大于后者于才变更位置, 其他情况下不变.
时间复杂度解析: 冒泡排序需要完成两层迭代过程, 第一层确保每个元素都进行排序.第二层来比较并排序元素.所以时间复杂度为O(N^2).
空间复杂度解析: 所有排序均在当前列表中完成, 不存在额外使用内存情况. 所以空间复杂度为O(1).

代码示例:

Python

def bubble_sort(li):
    # 获取列表总长度.
    li_len = len(li)
    # 第一层循环, 确保所有元素被遍历
    for i in range(li_len - 1):
        # 第二层循环, 比较并排序元素
        for j in range(li_len - i - 1):
            # 比较当前元素与相邻的下个元素
            if li[j] > li[j + 1]:
                # 交换相邻元素
                li[j], li[j + 1] = li[j + 1], li[j]
    return li