本文是常见的排序算法的一个简单总结，也是算法导论第三版的一些摘要记录，以作备忘和查询。

0X00、简介

• 1. 排序的定义：输入：n 个数的一个序列 <a1,a2,…,an>输出：序列的一个排列 <a1’,a2’,…,an’>, 满足 a1’<=a2’<=…<=an’
• 2. 排序算法复杂度概览

• 3. 术语解释稳定性：如果 a=b，且 a 在 b 前面，排序后 a 仍然在 b 前面，则说算法是稳定的；否则就是不稳定的。内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：一个算法执行所耗费的时间。空间复杂度：运行完一个程序所需内存的大小。
• 4. 关于时间复杂度的排序:(O (n^2)) 排序：各类简单排序：直接插入、直接选择和冒泡排序；(O (nlog2n)) 排序：快速排序、堆排序和归并排序；O (n1+§)) 排序，§ 是介于 0 和 1 之间的常数：希尔排序(O (n)) 排序：基数排序、桶、箱排序。
• 5. 关于稳定性的排序：稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

0X01、冒泡排序

冒泡排序是一种流行但是低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。

1. 算法描述

语言描述

• 1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 3. 针对所有的元素重复以上的步骤，除了最后一个；
• 4. 重复步骤 1~3，直到排序完成。

伪代码描述

BUBBLE-SORT(A)
1  for i = 1 to A.length - 1
2    for j = A.length downto i+1
3       if A[j] < A[j-1]
4           exchange A[j] with A[j-1]

2. 复杂度

时间复杂度

• 最佳情况：T (n) = O (n)
• 最差情况：T (n) = O (n^2)
• 平均情况：T (n) = O (n^2)

空间复杂度：O (1)

3. 代码实现如下

def bubble_sort(a: list):
    cnt = len(a)
    if not cnt:
        return a
    for i in range(1, cnt):
        for j in range(i-1, cnt-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1] , a[j]

    #for i in range(cnt-2):
    #    for j in range(cnt-1, i, -1):
    #        if a[j] < a[j-1]:
    #            a[j], a[j-1] = a[j-1], a[j]


if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    bubble_sort(a)
    print(a)

0X02、插入排序

插入排序 (Insertion-Sort) 是一种简单有效的排序方法。整体思想就是把后边一个待排的元素和前边已经排序好的元素做比较，如果比这元素大，就把前边的元素依次后移，直到找到一个比待排元素小的值，在其后边插入既可。然后在排序下一个待排元素。

1. 算法思路

语言描述

• 1. 从第一个元素开始，该元素可以认为已经被排序；
• 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
• 5. 将新元素插入到该位置后；
• 6. 重复步骤 2~5。

伪代码描述

INSERTION-SORT(A):
1  for j = 2 to A.length:
2    key = A[j]
3    i = j - 1
4    while i > 0 and A[i] > key:
5        A[i+1] = A[i]
6        i = i - 1
7    A[i+1] = key

2. 算法复杂度

时间复杂度

• 最佳情况：T (n) = O (n)。
• 最坏情况：T (n) = O (n^2)。
• 平均情况：T (n) = O (n^2)。

空间复杂度

• O (1)。因为其要占用一个存储空间来放置 key。

3. 算法实现

def insert_sort(a: list):
    cnt = len(a)
    if not cnt:
        return a

    for i in range(cnt - 1):
        value = a[i+1]
        pre_index = i
        while (pre_index >= 0 and value < a[pre_index]):
            a[pre_index + 1] = a[pre_index]
            pre_index -= 1
        a[pre_index+1] = value
    return a


if __name__ == "__main__":
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    insert_sort(a)
    print(a)

0X03、选择排序

表现最稳定的排序算法之一，因为无论什么数据进去都是 O (n2) 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序 (Selection-sort) 是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1. 算法分析

• 1. 初始状态：无序区为 R [1..n]，有序区为空；
• 2. 第 i 趟排序 (i=1,2,3…n-1) 开始时，当前有序区和无序区分别为 R [1..i-1] 和 R (i..n）。该趟排序从当前无序区中 - 选出关键字最小的记录 R [k]，将它与无序区的第 1 个记录 R 交换，使 R [1..i] 和 R [i+1..n) 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；
• 3. n-1 趟结束，数组有序化了。

2. 算法复杂度

• 最佳情况：T (n) = O (n2)
• 最差情况：T (n) = O (n2)
• 平均情况：T (n) = O (n2)

3. 算法实现

def selection_sort(a: list):
    """
    选择排序

    """
    cnt = len(a)
    if not cnt:
        return a
    for i in range(cnt):
        minIndex = i
        for j in range(cnt)[i:]:
            if a[j] < a[minIndex]:
                a[minIndex], a[j] = a[j], a[minIndex]
    return a


if __name__ == "__main__":
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    selection_sort(a)
    print(a)

0X04、希尔排序

希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破 O (n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

1. 算法思路

我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2. 算法复杂度

• 最佳情况：T (n) = O (nlog2 n)
• 最坏情况：T (n) = O (nlog2 n)
• 平均情况：T (n) =O (nlog2n)　

3. 算法实现

def shell_sort(a: list):
    """
    希尔排序
    算法思路：
    时间复杂度：O(n^2)，最好：O(n)，最坏：O(n^2)
    空间复杂度：O(1)
    """
    cnt = len(a)
    if not cnt:
        return a
    gap = cnt // 2
    while gap > 0:
        for i in range(gap, cnt, 1):
            tmp = a[i]
            pre_index = i - gap
            while pre_index >= 0 and a[pre_index] > tmp:
                a[pre_index+gap] = a[pre_index]
                pre_index -= gap
            a[pre_index+gap] = tmp
        gap //= 2
    return a


if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    shell_sort(a)
    print(a)

0X05、归并排序

归并排序是分治思想的一种实现。这里分治模式的每层递归时都有三个步骤：

• 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
• 解决这些子问题，递归的求解各个子问题。然而，若小问题的规模足够小，则直接求解。
• 合并这些子问题的解成原问题的解。
  这便是分治模式的思想。把大问题拆分成几个规模较小的子问题，把子问题在拆分成几个在小的问题，直至可以直接求解。然后把所有子问题的解合并就是原问题的解。

1. 算法思想

归并排序完全是分治思想的实现。

语言描述

• 分解。分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列。
• 解决。使用归并排序递归地排序两个子序列。
• 合并。合并两个已排序的子序列以产生已排序的答案。

伪代码描述

MERGE(A,p,q,r)
1  n1 = p - q + 1
2  n2 = r - q
3  let L[1..n1+1] and R[1..n2+1] to be new arrays
4  for i = 1 to n1
5    L[i] = A[p+i-1]
6  for j = 1 to n2
7    R[j] = A[q+j]
8  L[n1+1] = ∞
9  R[n2+1] = ∞
10 i = 1
11 j = 1
12 for k = p to r
13   if L[i] <= R[j]
14      A[k] = L[i]
15      i = i+1
16   else
17      A[k] = R[j]
18      j = j+1


MERGE-SORT(A,p,r)
1  if p < r
2     q = (p+r)/2
3     MERGE-SORT(A,p,q)
4     MERGE-SORT(A,q+1,r)
5     MERGE(A,p,q,r)

2. 算法复杂度

时间复杂度

• 最佳情况：T (n) = O (n)
• 最差情况：T (n) = O (nlogn)
• 平均情况：T (n) = O (nlogn)

空间复杂度

• O(1)

3. 算法实现

def merge_sort(a: list):
    cnt = len(a)
    if cnt < 2:
        return a
    mid = cnt // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))


def merge(left: list, right: list):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result


if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    print(merge_sort(a))

0X06、快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1. 算法思路

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

语言描述

• 从数列中挑出一个元素，称为 “基准”（pivot）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
• 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

伪代码描述

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

PARTITION(A,p,r)
1  x = A[r]
2  i = p-1
3  for j = p to r-1
4    if A[j] <= x
5        i = i+1
6        exchange A[i] with A[j]
7  exchange A[i+1] with A[r]
8  return i+1

2. 算法复杂度

时间复杂度

• 最佳情况：T (n) = O (nlogn)
• 最差情况：T (n) = O (n2)
• 平均情况：T (n) = O (nlogn)　

空间复杂度

• O(1)

3. 算法实现

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q)
        quick_sort(array, q + 1, r)


def partition(array, l, r):
    i = l - 1
    for j in range(l, r):
        if array[j] <= array[r]:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i+1], array[r] = array[r], array[i+1]
    return i

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(quicksort([3,6,8,10,1,2,1]))

if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    quick_sort(a, 0, len(a) - 1)
    print(a)

0X07、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序 (Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。

1. 算法思路

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素 i 放在新数组的第 C (i) 项，每放一个元素就将 C (i) 减去 1。

2. 算法复杂度

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O (n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

• 最佳情况：T (n) = O (n+k)
• 最差情况：T (n) = O (n+k)
• 平均情况：T (n) = O (n+k)

3. 算法实现

def count_sort(array):
    leng = len(array)
    c = []
    res = []
    for i in range(0, 100):
        c.append(0)
    for i in range(0, leng):
        c[array[i]] = c[array[i]]+1
        res.append(0)
    for i in range(0, 100):
        c[i] = c[i-1]+c[i]
    for i in range(leng-1, -1, -1):
        res[c[array[i]]-1] = array[i]
        c[array[i]] = c[array[i]]-1
    return res;


if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    print(count_sort(a))

0X08、基数排序

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为 O (kn), 为数组长度，k 为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

1. 算法思路

• 取得数组中的最大数，并取得位数；
• arr 为原始数组，从最低位开始取每个位组成 radix 数组；
• 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）

2. 算法复杂度

• 最佳情况：T (n) = O (n * k)
• 最差情况：T (n) = O (n * k)
• 平均情况：T (n) = O (n * k)

基数排序有两种方法：

• MSD 从高位开始进行排序
• LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶
• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值

3. 算法实现

def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j//(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists


if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    radix_sort(a)
    print(a)

0X09、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort) 的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

1. 算法思路

• 人为设置一个 BucketSize，作为每个桶所能放置多少个不同数值（例如当 BucketSize==5 时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放 100 个 3）；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
• 从不是空的桶里把排好序的数据拼接起来。
  注意，如果递归使用桶排序为各个桶排序，则当桶数量为 1 时要手动减小 BucketSize 增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

2. 算法复杂度

桶排序最好情况下使用线性时间 O (n)，桶排序的时间复杂度，取决于对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O (n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

• 最佳情况：T (n) = O (n+k)
• 最差情况：T (n) = O (n+k)
• 平均情况：T (n) = O (n2)　

3. 算法实现

class node:
    def __init__(self, k):
        self.key = k
        self.next = None


def bucket_sort(lista):
    h = []
    for i in range(0, 10):
        h.append(node(0))
    for i in range(0, len(lista)):
        tmp = node(lista[i])
        map = lista[i]//10
        p = h[map]
        if p.key is 0:
            h[map].next = tmp
            h[map].key = h[map].key+1
        else:
            while(p.next != None and p.next.key <= tmp.key):
                p = p.next
            tmp.next = p.next
            p.next = tmp
            h[map].key = h[map].key+1
    k = 0
    for i in range(0, 10):
        q = h[i].next
        while(q != None):
            lista[k] = q.key
            k = k+1
            q = q.next


if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    bucket_sort(a)
    print(a)

0X10、堆排序

堆排序 (heap-sort), 和归并排序一样，不同于插入排序的是，堆排序的时间复杂度是 O (nlogn)。与插入排序相同，不同于堆排序的是，堆排序具有空间原址性：任何时候都需要常数个额外的元素空间来存储临时数据。
其思想便是引用一种成为堆的数据结构。常见的有大根堆（最大堆）和小根堆（最小堆）。在排序中一般使用大根堆，小根堆通常构建优先队列。

• 大根堆：除了根以外的所有节点 i 都满足：A [PARENT (i)]>=A [i]
• 小根堆：除了根以外的所有节点 i 都满足：A [PARENT (i)]<=A [i]

1. 算法思路

伪代码描述

# 用于维护最大根堆的性质
# 对于树高为h的大根堆，其时间复杂度为O(h)
MAX-HEAPIFY(A,i)
1  l = LEFT(i)
2  r = RIGHT(i)
3  if l <= A.heap-size and A[l] > A[i]
4    largest = l
5  else larget = r
6  if r <= A.heap-size and A[r] > A[largest]
7    largest = r
8  if largest != i
9    exchange A[i] with A[largest]
10   MAX-HEAPIFY(A,largest)

# 建堆
BUILD-MAX-HEAP(A)
1  A.heap-size = A.length
2  for i = ?A.length/2? downto 1
3    MAX-HEAPIFY(A, i)

# 堆排序
HEAP-SORT(A)
1  BUILD-MAX-HEAP(A)
2  for i = A.length downto 2
3    exchange A[1] with A[i]
4    MAX-HEAPIFY(A, 1)

2. 算法复杂度

时间复杂度

• 最佳情况：T (n) = O (nlogn)
• 最差情况：T (n) = O (nlogn)
• 平均情况：T (n) = O (nlogn)

空间复杂度

• O(1)

3. 算法实现

from collections import deque

def swap_param(L, i, j):
    L[i], L[j] = L[j], L[i]
    return L

def heap_adjust(L, start, end):
    temp = L[start]

    i = start
    j = 2 * i

    while j <= end:
        if (j < end) and (L[j] < L[j + 1]):
            j += 1
        if temp < L[j]:
            L[i] = L[j]
            i = j
            j = 2 * i
        else:
            break
    L[i] = temp

def heap_sort(L):
    L_length = len(L) - 1

    first_sort_count = L_length // 2
    for i in range(first_sort_count):
        heap_adjust(L, first_sort_count - i, L_length)

    for i in range(L_length - 1):
        L = swap_param(L, 1, L_length - i)
        heap_adjust(L, 1, L_length - i - 1)

    return [L[i] for i in range(1, len(L))]

if __name__ == '__main__':
    a = [2, 1, 4, 6, 3, 45, 76, 47, 34, 5, 23]
    L = deque(a)
    L.appendleft(0)
    print(heap_sort(L))