冒泡排序

从列表的开头处开始，并且比较一对数据项，直到移动到列表的末尾。每当成对的两项之间的顺序不正确的时候，算法就交换其位置。然后，算法从列表开头到倒数第二个列表项重复这一过程，依次类推，直到该算法从列表的最后一项开始执行。此时，列表是已经排序好的。

Python实现：

import random


def bubble_sort(lyst):
    """冒泡排序 最坏的复杂度是O(n**2), 最好的情况下冒泡排序不会进行任何交换
    :param lyst:
    :return:
    """
    def swap(lyst, i, j):
        """交换项目中 i 和 j的位置"""
        #  可以理解为 lyst[i], lyst[j] = lyst[j], lyst[i]
        temp = lyst[i]
        lyst[i] = lyst[j]
        lyst[j] = temp

    n = len(lyst)
    while n > 1:
        i = 1
        while i < n:
            if lyst[i] < lyst[i - 1]:
                swap(lyst, i, i-1)
            i += 1
        n -= 1
    else:
        print(f"排序后内存地址为：{id(lyst)}")
        return lyst


if __name__ == '__main__':
    size = 10
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size + 1))
    print(lyst)
    print(f"排序前内存地址为：{id(lyst)} \n")
    print(bubble_sort(lyst))

Go 实现：

package main

import "fmt"


func swap(lyst []int, i int, j int) {

    temp := lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp
}

func main()  {
    lyst := []int{100, 900, 111, 99, 56, 103, 78, 95, 1000, 789, 134, 110}
    fmt.Println(lyst)

    n := len(lyst)

    for n > 1 {
        i := 1
        for i < n {
            if lyst[i] < lyst[i -1] {
                swap(lyst, i, i-1)
            }
            i += 1
        }
        n -= 1
    }
    fmt.Println(lyst)
}

时间复杂度：

在最坏的情况下，一共需要 $\frac{1}{2} n^2-\frac{1}{2}n$ 次。因此，冒泡排序最坏的情况复杂度是$ O(n^2)$。