输入：n个数的一个序列<a1,a2,...,an> (A[1..n]) 输出：输入序列的一个排序<b1,b2,...,bn>，满足b1≤b2≤...≤bn。

插入排序

思想

扫描数组，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。参考：Wiki百科：插入排序

实现

伪代码

INSERTION-SORT(A) 
    for j = 2 to A.length
        key = A[j]
        //将A[j]插入到已排序序列A[1..j-1]
        i = j - 1
        while i > 0 and A[i] > key
            A[i+1] = A[i]
            i = i -1
        A[i+1] = key

1. Python实现（升序）

def INSERTION_SORT_ASC(A):
    n= len(A) #A的长度
    for j in range(1,n): # 从第二个元素开始，遍历数组
        key, i = A[j], j # 保存当前元素的值key
        while i>0 and A[i-1]>key: #当前元素前面的序列是已经排序好的数组
            A[i] = A[i-1] # 将较大的数后移
            i -=1 # 继续往前找
        A[i] = key # i为当前元素的插入位置

2. Python实现（降序）

def INSERTION_SORT_DESC(A):
    n = len(A)
    for j in range(1,n):
        key, i = A[j], j
        while i>0 and A[i-1]<key:
            A[i] = A[i-1]
            i -= 1
        A[i] = key

## 图片说明

## 复杂度 1. 空间复杂度：O(1), in-place排序 2. 时间复杂度：O(n^2)

注意

只要循环到一个小于或等于key值的数就说明找到key值的位置了。此时需要结束循环
用key值去比较，而不是用相邻的两个值做比较
当n很小的时候效率较高，当n很大的时候，不适用
一种稳定的算法

# 选择排序 ## 思想为每个位置选择当前元素最小的。即，首先找出A中的最小元素并将其与A[0]中的元素进行交换。接着，找出A中次最小元素并将其与A[1]中的元素进行交换。对A中前n-1个元素按该方式继续。参考：Wiki百科：选择排序

## 实现伪代码：

SELECTION_SORT(A)
    for i = 1 to A.length-1
        min = i
        for j=i+1 to A.length //找出当前位置最小的
            if A[j] < A[min]
                min = j
        exchange A[i] with A[min]

1. Python实现（升序）

def SELECTION_SORT_ASC(A):
    n = len(A)
    for i in range(0,n-1):
        min = i
        for j in range(i+1,n): #找出当前位置最小的
            if A[j]<A[min]: min=j
        if i!=min: A[i],A[min] = A[min],A[i]

2. Python实现（降序）

def SELECTION_SORT_DESC(A):
    n = len(A)
    for i in range(0,n-1):
        max = i
        for j in range(i+1,n): #找出当前位置最大的
            if A[j]>A[max]: max=j
        if i!=max: A[i],A[max] = A[max],A[i]

## 图片说明

## 复杂度 1. 空间复杂度：O(1), in-place排序 2. 时间复杂度：O(n^2)

## 注意 1. 记录最小/大那个元素的下标，而不是值。 2. 相同元素的前后顺序可能改变，因此是不稳定的排序算法

冒泡排序

思想

反复交换相邻的未按次序排列的元素。即把小的元素往前调，或者把大的元素往后调参考：Wiki百科：冒泡排序 ## 实现伪代码：

BUBBLESORT(A)
    for i=1 to A.length-1 //从前往后扫描数组
        for j=A.length downto i+1 //从后开始，不断把小的元素往前推
            if A[j] < A[j-1]
                exchange A[j] with A[j-1]

1. Python实现（升序）

def BUBBLE_SORT_ASC(A):
    n = len(A)
    for i in range(0,n-1):
        for j in range(i+1,n)[::-1]:
            if A[j] < A[j-1]: A[j], A[j-1] = A[j-1], A[j]

2. Python实现（降序）

def BUBBLE_SORT_DESC(A):
    n = len(A)
    for i in range(0, n-1):
        for j in range(i+1,n)[::-1]:
            if A[j] > A[j-1]: A[j], A[j-1] = A[j-1], A[j]

## 图片说明

## 复杂度 1. 空间复杂度：O(1), in-place排序 2. 最差/平均/最优时间复杂度：O(n^2) ## 注意 1. 相同元素的前后顺序不会改变，因此是一种稳定的排序算法。 2. 低效的简单排序算法

归并排序

思想：分而治之

分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
解决：使用归并排序递归地排序两个子序列
合并(MERGE)：合并两个已排序的子序列以产生已排序的答案参考：Wiki百科：归并排序

实现

伪代码：

// 合并操作
// p, q, r是数组的下标，满足p≤q<r
// 假设子序列A[p..q]和A[q+1..r]已排好序
// 此过程合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p..r]
// 时间复杂度O(n), n=r-p+1
// 哨兵的设置：避免检查堆为空，只需要执行r-p+1个基本步骤，算法就可以停止
MERGE(A, p, q, r)
    n1 = q - p + 1 //A[p..q]的元素个数
    n2 = r - q //A[q+1..r]的元素个数
    let L[1..n1+1] and R[1..n2+1] be new arrays
    for i=1 to n1
        L[i] = A[p+i-1]
    for j=1 to n2
        R[j] = A[q+j]
    L[n1+1] = ∞ //哨兵
    R[n2+1] = ∞
    i = 1
    j = 1
    for k=p to r
        if L[i] ≤ R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1
// 排序子数组A[p..r]
// 初始调用：MERGE_SORT(A, 1, A.length)
MERGE_SORT(A, p, r):
    if p < r: //若p≥r，则该数组最多有一个元素，所以已经排好序
        q = (p+r)/2 //这里表示整除，分解
        MERGE_SORT(A, p, q) // 左子数组排序
        MERGE_SORT(A, q+1, r) // 右子数组排序
        MERGE(A, p, q, r) //合并

1. Python实现

# 升序
def MERGE(A, p, q, r):
    L,R = A[p:q+1],A[q+1:r+1]
    # 增加哨兵值，float('inf')在Python中表示无穷大
    L.append(float('inf')) # 若降序，则需要修改为L.append(float('-inf'))
    R.append(float('inf')) # 同上
    i, j, k = 0, 0, p
    while k <= r:
        if L[i] < R[j]: # 若降序，则需要修改成L[i] > R[j]
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1
        k+=1
def MERGE_SORT(A, p, r):
    if p < r:
        q = (p+r)//2
        MERGE_SORT(A,p,q)
        MERGE_SORT(A,q+1,r)
        MERGE(A,p,q,r)

## 图片说明

## 复杂度 1. 最差/平均时间复杂度：O(nlogn)；最优时间复杂度：O(n) 2. 最差空间复杂度：O(n)

注意

归并的时候，计算出来的n1, n2是真实的L数组和R数组的长度。如果使用哨兵，申请L数组和R数组的时候，需要给哨兵申请一个位置，也就是说，需要申请的长度比实际上多1，即n1+1, n2+1
归并的时候，将左右数组的元素放到目标（也是源）数组排序后的位置时，循环用目标数组的位置作为继续条件。也就是说，只要目标数组的位置占满了，就可以退出比较循环。
归并的时候，若不使用哨兵，注意主循环结束的条件是，左数组、右数组或者目标数组有一个到达了数组的最后一个元素。
这种排序方法比较占用内存，却是一种效率高且稳定的算法