排序算法总结

插入排序

INSERTION-SORT(A)
    for j = 2 to A.length
        key = A[j]
        //Insert A[j] into the sorted sequence 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

归并排序

//假设子数组A[p, q]和A[q+1, r]都已排好序
MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    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

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)

堆排序（最大堆）

PARENT(i)
    return ⌊i/2⌋

LEFT(i)
    return 2i

RIGHT(i)
    return 2i+1

MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r
    if largest ≠ i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = ⌊A.length/2⌋ down to 1
        MAX-HEAPIFY(A, i)

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap-size = A.heap-size - 1
        MAX-HEAPIFY(A, 1)

BUILD-MAX-HEAP示意图

快速排序

QUICKSORT(A, p, r)
    if p < r
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q-1)
        QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r-1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i + 1

快速排序过程图

计数排序（假设n个输入元素中的每一个都是0到k区间内的一个整数）

//数组A[1..n]是输入，B[1..n]存放排序的输出
COUNTING-SORT(A, B, k)
    let C[0..k] be a new array
    for i = 0 to k
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    //C[i] now contains the number of elements equal to i
    for i = 1 to k
        C[i] = C[i] + C[i-1]
    //C[i] now contains the number of elements less than or equal to i
    for j = A.length downto 1
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

基数排序

//假设n个d位的元素存放在数组A中，其中第1位是最低位，第d位是最高位
RADIX-SORT(A, d)
    for i = 1 to d
        use a stable sort to sort array A on digit i

桶排序

//假设输入是一个包含n个元素的数组A，且每个元素A[i]满足0<=A[i]<=1
BUCKET-SORT(A)
    n = A.length
    let B[0..n-1] be a new array
    for i = 0 to n-1
        make B[i] an empty list
    for i = 1 to n
        insert A[i] into list B[⌊nA[i]⌋]
    for i = 0 to n-1
        sort list B[i] with insertion sort
    concatenate the list B[0], B[1], ... B[n-1] together in order