​ 本文将着重介绍直接插入排序，直接选择排序，冒泡排序，归并排序与快排排序，以下实现皆为升序。

直接插入排序

​ 特点：稳定，时间复杂度：O(n^2)。

1
2
3
4
5
6
def insertion_sort(a):
    for i in range(1, len(a)):
        while a[i] < a[i-1]:
            a[i], a[i - 1] = a[i - 1], a[i]
            i -= 1
    return a

​ 排序过程：第一个数一定有序，从第二个值开始，将第二个值放入一个temp中，与第一个进行比较，大于放到第一个后面，不大于则将第一位向后移，将第二个数插入到第一位，此时前两个数已经排列好，第三位重复上述过程，在前部已排好的序列中找到位置并插入，原来插入位置极之后的值向后移。继续执行上述过程，直至排序完毕。

​ 上述程序经过优化，将需要进行排序的数直接与前一位值比较，小于则换位置，然后继续向前比较，换位，直到本轮排序完毕，将向后移与插入的过程转换为比较换位。

直接选择排序

​ 特点：不稳定，时间复杂度：O(n^2)。

1
2
3
4
5
6
7
def selection_sort(a):
    for i in range(len(a) - 1):
        m = i
        for j in range(i + 1, len(a)):
            if a[m] > a[i]:
                a[m], a[i] = a[i], a[m]
    return a

​ 排序过程：从第一位开始，与之后位的值进行比较，直到找出最小值，放到第一位，然后从第二位开始比较，直到找出第二小的数放到第二位，重复上述过程，直到排序完成。

冒泡排序

​ 特点：稳定，平均时间复杂度：O(n^2)。

1
2
3
4
5
6
def bubble_sort(a):
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

​ 排序过程：从第一个数开始，如果第一个数大于第二个，两者换位，继续向后比较，如果不大于则不换位，用第二位向后一位比较，重复上述比较过程。

​ 上述程序经过优化，已排好顺序的部分将不参与比较。

归并排序

​ 特点：稳定，时间复杂度O(nlog2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def merge_sort(a):
    if len(a) > 1:
        mid = len(a) // 2
        left = merge(a[:mid])
        right = merge(a[mid:])
        i = 0
        j = 0
        k = 0
        l = len(left)
        r = len(right)
        while i < l and j < r:
            if left[i] < right[j]:
                a[k] = left[i]
                i += 1
                k += 1
            else:
                a[k] = right[i]
                j += 1
                k += 1
    return a

​ 排序过程：采取分治法，将每组都排好序，

快排

​ 特点：不稳定，时间复杂度：O(nlog2n)

1
2
3
4
5
6
7
def quick_sort(a):
    if len(a) <= 1:
        return a
    p = a[0]
    g = [e for e in a[1:] if e > p]
    lq = [e for e in a[1:] if e <= p]
    return quick(lq) + [p] + quick(g)

​ 排序过程：选择一个基值（一般为第一个数），将其放在中间位置，定义两个游标，从左边寻找比基值大的数，从右边找比基值小的数，左右两个游标的值交换，执行此操作直至两个指针相遇。一轮结束后，对基数左右两边的数组继续执行上述操作，直到排序完毕。

​ 快排的每一轮的操作本质上来说就是将大的数放到基值右边，小的数放到基值左边，上述的代码就是通过递归来实现上述思想。

总结

排序方法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 复杂性
直接插入排序 O(n^2) O(n^2) O(n) O(1) 稳定 简单
直接选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
冒泡排序 O(n^2) O(n^2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n^2) O(nlog2n) O(nlog2n) 不稳定 较复杂
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂