前言

一些简单的排序算法，用python来实现，有些慢慢再补充

1 插入排序

# 插入排序
def insert_sort(lst):                           
    for i in range(1, len(lst)):
        x = lst[i]
        j = i
        while j > 0 and lst[j-1] > x:
            lst[j] = lst[j-1]
            j -= 1
        lst[j] = x
        print(lst)                           # 每一趟的排序结果


if __name__ == '__main__':
    lst = [1, 6, 7, 3, 8, 1, 0, 5]
    insert_sort(lst)
    print(lst)

测试结果：
[1, 6, 7, 3, 8, 1, 0, 5]
[1, 6, 7, 3, 8, 1, 0, 5]
[1, 3, 6, 7, 8, 1, 0, 5]
[1, 3, 6, 7, 8, 1, 0, 5]
[1, 1, 3, 6, 7, 8, 0, 5]
[0, 1, 1, 3, 6, 7, 8, 5]
[0, 1, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]

注意：for循环里面的这个print(lst)，打印出每一趟的运行结果，让插入排序的运行结果更加具体，去了也无所谓。
最坏情况下时间复杂度：O(n^2)
平均时间复杂度：O(n^2)

2 选择排序

# 选择排序
def select_sort(lst):
    for i in range(len(lst)-1):
        k = i
        for j in range(i, len(lst)):
            if lst[k] > lst[j]:
                k = j
        if i != k:
            # 与k标记上的数交换位置，因为lst[k]没有排序的数值中足小值
            lst[i], lst[k] = lst[k], lst[i]
        print(lst)


if __name__ == '__main__':
    lst = [1, 6, 7, 3, 8, 1, 0, 5]
    select_sort(lst)
    print('*' * 50)
    print(lst)

结果：
[0, 6, 7, 3, 8, 1, 1, 5]
[0, 1, 7, 3, 8, 6, 1, 5]
[0, 1, 1, 3, 8, 6, 7, 5]
[0, 1, 1, 3, 8, 6, 7, 5]
[0, 1, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
**************************************************
[0, 1, 1, 3, 5, 6, 7, 8]

注意：同上
最坏情况下时间复杂度：O(n^2)
平均时间复杂度：O(n^2)

3 冒泡排序

有逆序就交换，一趟之后最大值冒泡出来了（在最后）。第二趟可以忽略最后一个最大值……

# 冒泡排序
def bubble_sort(lst):
    for i in range(len(lst)):
        for j in range(1, len(lst)-i):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
        print(lst)


if __name__ == '__main__':
    lst = [1, 6, 7, 3, 8, 1, 0, 5]
    bubble_sort(lst)
    print('*' * 50)
    print(lst)

结果：
[1, 6, 3, 7, 1, 0, 5, 8]
[1, 3, 6, 1, 0, 5, 7, 8]
[1, 3, 1, 0, 5, 6, 7, 8]
[1, 1, 0, 3, 5, 6, 7, 8]
[1, 0, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
**************************************************
[0, 1, 1, 3, 5, 6, 7, 8]

改进后的冒泡的排序，其实也就是发现没有逆序直接跳出循环而已，本质还是一样，最坏情况下事件复杂度还是一样

# 改进后的冒泡排序
def new_bubble_sort(lst):
    for i in range(len(lst)):
        found = False
        for j in range(1, len(lst)-i):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
                found = True
        if not found:                          # 逛第一遍没发现逆序，说明全部是正序了，跳出循环
            break
        print(lst)


if __name__ == '__main__':
    lst = [1, 6, 7, 3, 8, 1, 0, 5]
    new_bubble_sort(lst)
    print('*' * 50)
    print(lst)

    print()

    lst2 = [1, 2, 3, 4, 5, 6, 7, 8]
    new_bubble_sort(lst2)
    print('*' * 50)
    print(lst2)

结果：
[1, 6, 3, 7, 1, 0, 5, 8]
[1, 3, 6, 1, 0, 5, 7, 8]
[1, 3, 1, 0, 5, 6, 7, 8]
[1, 1, 0, 3, 5, 6, 7, 8]
[1, 0, 1, 3, 5, 6, 7, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
**************************************************
[0, 1, 1, 3, 5, 6, 7, 8]

**************************************************
[1, 2, 3, 4, 5, 6, 7, 8]

最坏情况下时间复杂度：O(n^2)
平均时间复杂度：O(n^2)

4 快速排序

快速排序思路比上面三种方法复杂一点，百度看一下思路。
关键：取第一个数为中心轴，把小的放中心轴左边，大的放中心轴右边，然后递归。

def quick_sort(lst):
    qsort_rec(lst, 0, len(lst)-1)


def qsort_rec(lst, l, r):
    if l >= r:
        return
    i = l
    j = r
    pivot = lst[i]
    while i < j:
        while i < j and lst[j] >= pivot:
            j -= 1
        if i < j:
            lst[i] = lst[j]
            i += 1
        while i < j and lst[i] <= pivot:
            i += 1
        if i < j:
            lst[j] = lst[i]
            j -= 1

    lst[i] = pivot
    print(lst)
    qsort_rec(lst, l, i-1)
    qsort_rec(lst, i+1, r)


if __name__ == '__main__':
    lst = [1, 6, 7, 3, 8, 1, 0, 1]
    quick_sort(lst)
    print('*' * 50)
    print(lst)
结果：
[1, 0, 1, 1, 8, 3, 7, 6]
[1, 0, 1, 1, 8, 3, 7, 6]
[0, 1, 1, 1, 8, 3, 7, 6]
[0, 1, 1, 1, 6, 3, 7, 8]
[0, 1, 1, 1, 3, 6, 7, 8]
**************************************************
[0, 1, 1, 1, 3, 6, 7, 8]

我用这么多1测试，是为了看

while i < j and lst[j] >= pivot:
while i < j and lst[i] <= pivot:

这一步，>=号，排序操作少一些。只用 = 号，操作就多一点。
下面是另一种思路，本质上还是一样的，理解上面的也足够了。

def quick_sort1(lst):
    qsort(lst, 0, len(lst)-1)


def qsort(lst, l, r):
    if l >= r:
        return
    privo = lst[l]
    i = l
    for j in range(l+1, r+1):
        if lst[j] < privo:
            i += 1
            lst[i], lst[j] = lst[j], lst[i]

    lst[l], lst[i] = lst[i], lst[l]
    print(lst)
    qsort(lst, l, i-1)
    qsort(lst, i+1, r)


if __name__ == '__main__':
    lst = [3, 6, 7, 3, 8, 1, 0, 5]
    quick_sort1(lst)
    print('*' * 50)
    print(lst)

最坏时间复杂度：O(n^2)
平均时间复杂度：O(n log n)

5 归并排序

def merge(lfrom, lto, low, mid, high):                        # 左右归并
    i, j, k = low, mid, low
    while i < mid and j < high:
        if lfrom[i] <= lfrom[j]:
            lto[k] = lfrom[i]
            i += 1
        else:
            lto[k] = lfrom[j]
            j += 1
        k += 1
    while i < mid:
        lto[k] = lfrom[i]
        i += 1
        k += 1
    while j < high:
        lto[k] = lfrom[j]
        j += 1
        k += 1


def merge_pass(lfrom, lto, llen, slen):
    i = 0
    while i + 2 * slen < llen:
        merge(lfrom, lto, i, i+slen, i+2*slen)
        i += 2 * slen
    if i + slen < llen:
        merge(lfrom, lto, i, i+slen, llen)
    else:
        for j in range(i, llen):
            lto[j] = lfrom[j]


def merge_sort(lst):
    slen, llen = 1, len(lst)
    templst = [None] * llen
    while slen < llen:
        merge_pass(lst, templst, llen, slen)
        slen *= 2
        merge_pass(templst, lst, llen, slen)
        slen *= 2
        print(lst)


if __name__ == '__main__':
    lst = [1, 6, 7, 3, 8, 1, 0, 5]
    merge_sort(lst)
    print('*' * 50)
    print(lst)
结果：
[1, 3, 6, 7, 0, 1, 5, 8]
[0, 1, 1, 3, 5, 6, 7, 8]
**************************************************
[0, 1, 1, 3, 5, 6, 7, 8]