冒泡

#标准版本
def bubble_sort(array):
    n = len(array)
    for i in range(n):  # i从0到n
        for j in range(1, n-i):  # 1开始，即j-1=0开始
            if array[j-1] > array[j]:
                array[j-1], array[j] = array[j], array[j-1]
    return array
#优化版本
def bubble_sort2(array):
    n = len(array)
    for i in range(n):
        flag = 1                    #标记
        for j in range(1,n-i):
            if  array[j-1] > array[j] :
                array[j-1],array[j] = array[j],array[j-1]
                flag = 0
        if flag :                   #标记为正，说明以上的都排好了，以后的迭代没意义了
            break
    return array
#优化版本2
def bubble_sort(array):
    n=len(array)
    k=n
    for i in range(n):
        flag=True
        for j in range(1,k):
            if array[j-1]>array[j]:
                array[j-1],array[j]=array[j],array[j-1]
                k=j                #记录最后交换的位置，后面的都排好了。
                flag=False
        if flag:
            break
    return array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

选择排序

def selection_sort(array):       #每次把序列中的最小值换到最前面
    n = len(array)           #因为记录index交换少，所以性能略优于冒泡
    for i in range(n):
        minIndex = i
        for j in range(i+1, n):
            if array[j] < array[minIndex]:
                minIndex = j
        array[i], array[minIndex] = array[minIndex], array[i]
    return array
1
2
3
4
5
6
7
8
9

插入排序

def insert_sort(array):   #假设有概率序列初始状态就是局部有序，那么插入排序比冒泡和选择好。
    n=len(array)
    for i in range(1,n):
        if array[i-1]>array[i]:          #这句可以不要
            num=array[i]
            index=i
            for j in range(i-1,-1,-1):
                if array[j]>num:
                    array[j+1]=array[j]     #往后移动
                    index=j                 #腾出来的原来的位置就变成了可插入的位置被记录
                else:
                    break
            array[index]=num
    return array
1
2
3
4
5
6
7
8
9
10
11
12
13
14

希尔排序

def shell_sort(array):
    n=len(array)
    gap=round(n/2)     #设置gap
    while gap>0:
        for i in range(gap,n):   #这里相当于跨着步子的插入排序
            num=array[i]
            index=i
            while index>=gap and array[index-gap]>num:
                array[index]=array[index-gap]
                index=index-gap
            array[index]=num
        gap=round(gap/2)
    return array
1
2
3
4
5
6
7
8
9
10
11
12
13

归并排序

def merge_sort(array):  # 递归
    if len(array) <= 1: return array  # python每次都是新的数组，可以用数组长度小于等于1来判断
    num = len(array) // 2  # py27 3/2和3//2相同,python3 3//2才是地板除
    left = merge_sort(array[:num])
    right = merge_sort(array[num:])
    return merge(left, right)

def merge(left, right):  # 合并
    l,r = 0,0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l = l + 1
        else:
            result.append(right[r])
            r += 1
    # 一边没有之后，加上所有的
    result += left[l:]
    result += right[r:]
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

快排

def quick_sort(array):
    """快速排序"""
    if len(array) >= 2:  # 递归入口及出口
        mid = array[len(array) // 2]  # 选取基准值，也可以选取第一个或最后一个元素
        left, right = [], []  # 定义基准值左右两侧的列表
        array.remove(mid)  # 从原始数组中移除基准值
        for num in array:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return array
1
2
3
4
5
6
7
8
9
10
11
12
13
14

堆排序

def adjust_heap(heap,heapsize,father):
    left=2*father+1 #计算左儿子index
    right=father+1 #计算右儿子index
    large=father #最大值的index先默认为爸爸
    if left<heapsize and heap[large]<heap[left]:
        large=left
    if right<heapsize and heap[large]<heap[right]:
        large=right
    if large!=father:  #如果有最大值的index有调整，再交换
        heap[large],heap[father]=heap[father],heap[large]
        adjust_heap(heap,heapsize,large) #继续向下调整

def heap_sort(array):
    n=len(array)
    for father in range(((n-1)-1)//2,-1,-1):  #计算出最后一个父节点，然后一步一步往前遍历前面的父节点
        adjust_heap(array,n,father)

    for i in range(n-1,-1,-1):
        array[0],array[i]=array[i],array[0] #根结点（最大值）放最后一个
        adjust_heap(array,i,0)  #继续从根结点开始调整
    return array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

排序算法复杂度分析