12_基本排序算法

冒泡排序

时间复杂度：O(n^2)

# O(n^2), n(n-1)/2 = 1/2(n^2 + n)
import random

def bubble_sort(seq):
    n = len(seq)
    for i in range(n-1):
        print(seq)
        for j in range(n-1-i):
            print(seq[j], seq[j+1])
            if seq[j] > seq[j+1]:
                seq[j], seq[j+1] = seq[j+1], seq[j]

def test_bubble_sort():
    seq = list(range(10))
    random.shuffle(seq)
    bubble_sort(seq)
    assert seq == sorted(seq)

if __name__ == '__main__':
    test_bubble_sort()

选择排序

时间复杂度：O(n(n-1)/2)
找到最小的元素插入迭代的起始位置，这样每个位置从它自己的位置开始它就是最小的了，一圈下来数组就有序了。 选择可以理解为 一个 0 到 n-1 的迭代，每次向后查找选择一个最小的元素。

def select_sort(seq):
    n = len(seq)
    for i in range(n-1):
        # 假定 最后一个是min
        min_idx = i
        # i 的后一位开始比较
        for j in range(i+1, n):
            if seq[j] < seq[min_idx]:
                min_idx = j
        if min_idx != i:
            seq[i], seq[min_idx] = seq[min_idx], seq[i]

def test_select_sort():
    seq = list(range(10))
    random.shuffle(seq)
    select_sort(seq)
    assert seq == sorted(seq)

if __name__ == '__main__':
    test_select_sort()

插入排序

时间复杂度：O(n^2)

def insertion_sort(seq):
    n = len(seq)
    for i in range(1, n):
        value = seq[i] # 保存当前位置的值，因为转移的过程中它的位置可能被覆盖
        pos = i
        while pos > 0 and value < seq[pos-1]:
            seq[pos] = seq[pos-1] # 如果前边的元素比它大，就让它一直前移
            pos -= 1
        seq[pos] = value

if __name__ == '__main__':
    seq = [2, 9, 5, 6, 3, 4]
    insertion_sort(seq)