本博客基本参考了一像素的博客和《算法导论》，并将Java的实现改成了Python3实现

0 算法概述

0.1 算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 $O(nlogn)$ ，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

排序算法

0.2 算法复杂度

算法复杂度

0.3 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1 冒泡排序

基本思想：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

最大时间复杂度为 $T(n)=\frac{n(n-1)}{2}=O(n^2)$
最小时间复杂度为 $T(n)=n-1=O(n)$

算法描述：

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

Python3 实现

def bubble_sort(nums):
    for i in range(len(nums) - 1):  
        flag = False
        for j in range(len(nums) - i - 1):    
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True
        if not flag:
            return nums
    return nums

2 选择排序

基本思想：选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中选择最小的和第二个元素交换，继续这种选择和交换方式，最终得到一个有序序列。

最大时间复杂度为 $T(n)=\frac{n(n +1)}{2}=O(n^2)$
最小时间复杂度为 $T(n)=n=O(n)$

python实现

def select_sort(nums):
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]

    return nums

算法分析：
表现最稳定的排序算法之一，因为无论什么数据进去都是 $O(n^2)$ 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法。

3 插入排序

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

插入排序是指在待排序的元素中，假设前面 $n-1$ (其中 $n>=2$ )个数已经是排好顺序的，现将第 $n$ 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 $n$ 个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

插入排序在数据规模小或者数据基本有序时十分高效

Python3实现

# No in-place
def insert_sort(a):
    n = len(a)
    b = [a[0]]
    for i in range(1, n):
        j = 0
        while(j < i and a[i] > b[j]):
            j += 1
        b.insert(j, a[i])
    return b

# In-place
def insert_sort(nums):
    for i in range(1, len(nums)):
        k = i
        for j in range(i-1, -1, -1):
            if nums[j] > nums[k]:
                k = j
                nums[k], nums[j] = nums[j], nums[k]
    return nums
# In order not to exchange elements every time in the loop search, the following will be better
def insert_sort2(a):
    n = len(a)
    for i in range(1, n):
        j = i-1
        while j > -1 and a[i] < a[j]:
            j -= 1
        a.insert(j+1, a.pop(i))
    return a

算法分析：
插入排序在实现上，通常采用in-place排序（即只需用到 $O(1)$ 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

可以采用二分查找的方法确定第i个元素待插入的位置（找到第一个大于i元素的元素）可能可以减小时间复杂度。

4 希尔排序

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需 $n-1$ 次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

1959年Shell发明，第一个突破 $O(n^2)$ 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序首先选择一个元素选择步长将数组划分为若干小组，对各个小组分别进行排序，然后不断将步长缩小，不断分组和排序，直到步长为1，对所有的元素进行排序，此时，经过前期的排序工作，能够减少全体元素插入排序的对比次数，大大降低了排序的时间复杂度。

Python3实现

def shell_sort(nums):
    n = len(nums)
    while n>=1:
        n = n//2
        for i in range(n, len(nums)):
            j = i
            while(j>=n):
                if nums[j] < nums[j-n]:
                    nums[j], nums[j-n] = nums[j-n], nums[j]
                    j -= n
                else:
                    break
    return nums

C++实现

void shell_sort(vector<int>& nums)
{
    size_t n = nums.size();
    while (n >= 1)
    {
        n = n / 2;
        for (size_t i = n; i < nums.size(); i++)
        {
            size_t j = i;
            while (j >= n)
            {
                if (nums[j] < nums[j - n])
                {
                    swap(nums[j], nums[j - n]);
                    j -= n;
                }
                else
                    break;
            }
        }
    }
}

5 归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

核心问题是如何将两个已经排序好的数组归并成一个新的数组

解决方法是：可以开辟一个临时数组来辅助归并，新数组的长度和待排序的数组相同，因而空间复杂度相比较之前的排序算法增加 $O(n)$ 。

具体步骤：
在整个过程中需要维护三个指针，分别指向三个数组。下图中蓝色箭头位置表示待写入的位置，红色箭头表示待比较的位置。

首先对两个数组的第一个元素进行比较

将较小者复制到新数组，该数组和新数组的指针自增1，再对两个红色箭头位置的元素进行比较

将较小者复制到新数组，该数组和新数组的指针自增1

一直持续这一过程直到新数组的指针移动到最后，归并结束

需要注意的是，如果有一个待排序数组的指针先达到结束位置，则另一个数组不需要比较，直接移动到新数组即可使归并结束

def merge(s1,s2,s):
    """将两个列表是s1，s2按顺序融合为一个列表s,s为原列表"""
    # j和i就相当于两个指向的位置，i指s1，j指s2
    i = j = 0
    while i+j<len(s):
        # j==len(s2)时说明s2走完了，或者s1没走完并且s1中该位置是最小的
        if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):
            s[i+j] = s1[i]
            i += 1
        else:
            s[i+j] = s2[j]
            j += 1

def merge_sort(s):
    """归并排序"""
    n = len(s)
    # 剩一个或没有直接返回，不用排序
    if n < 2:
        return
    # 拆分
    mid = n // 2
    s1 = s[0:mid]
    s2 = s[mid:n]
    # 子序列递归调用排序
    merge_sort(s1)
    merge_sort(s2)
    # 合并
    merge(s1,s2,s)

算法复杂度
用递归关系表示为：
$T(n)=\begin{cases} \Theta(1) & n=1 \\ 2T(\frac{n}{2}) +\Theta(n) & n>1 \end{cases}$
其中， $2$ 表示子问题的数量， $\frac{n}{2}$ 表示子问题的规模， $\Theta(n)$ 是额外的计算，主要是分解和合并的过程中带来的，直观的来说是merge过程存在的while循环。
采用主方法， $T(n)$ 的解为
$T(n) = \Theta(nlgn)$
参考 算法导论 分治策略章节

6 快速排序

快速排序和归并排序是面试中最常考的排序算法，是分治思想的重要体现。不同的是，归并排序重要的是合（Combine），而快速排序更重要的是分（devide）。

快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。一趟快速排序的具体过程可描述为：从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值，然后将记录中关键字比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。

对于包含 $n$ 个数的输入数组来说，快速排序是一种最坏时间复杂度为 $\Theta(n^2)$ 的排序算法。虽然最差情况时间复杂度很差，但是快速排序通常是实际排序中最好的选择，因为它的平均性能非常好：它的期望时间复杂度为 $\Theta(nlog)$ ，而且 $\Theta(nlog)$ 中隐藏的时间因子非常小。另外它还能进行原址排序，甚至在虚拟环境中也能很好的工作。

一趟快速排序的具体做法（分治中的Devide部分）为：

设置两个指针 $low$ 和 $high$ 分别指向待排序列的开始和结尾，记录下基准值(通常取待排序列的第一个值)；
然后先从 $high$ 所指的位置向前搜索直到找到一个小于基准值的记录并互相交换；
再从 $low$ 所指向的位置向后搜索直到找到一个大于基准值的记录并互相交换；
重复2和3，直到 $low=high$ 时结束，此时基准值已经到达了正确的位置，即基准值前的元素都比它小，后面的元素都比它大。

对于分治的Conquer部分，因为基准值元素已经排好，只需分别对前后的元素进行递归排序就好
对于分治的Combine部分，因为元素排序完成后问题已经解决，不需要合并，所以不必进行这一部分

import random
def quick_sort(nums, start, end):
    if start >= end:
        return
    i = start
    j = end
    # here we use a randomized quicksort algorithm.
    k = random.randint(start, end-1)
    arr[i], arr[k] = arr[k], arr[i]
    baseval = nums[start]
    while i<j:
        while i<j and nums[j] >= baseval:
            j -= 1
        if i<j:
            nums[i] = nums[j]
            i += 1
        while i<j and nums[i] < baseval:
            i += 1
        if i<j:
            nums[j] = nums[i]
            j -= 1
    nums[i] = baseval
    quick_sort(nums, start, i-1)
    quick_sort(nums, j+1, end) # 此时 i = j，所以对[start, i-1]和[i+1, end]递归
    return

if __name__ == '__main__':
    arr = [1, 3, 1, 4, 6, 2, 7, 0]
    quick_sort(arr, 0, len(arr)-1)
    print(arr)

另一种方法
此方法是在MIT的算法导论视频中提到的，貌似比上面的方法好理解，代码也简洁些。
该方法在Devide部分只有一轮从左往右的搜索，运算量应该也较小。

算法描述为：

Devide部分

设置两个指针 $i$ 和 $j$ 分别指向待排序列的第一个元素和第二个元素，记录下基准值(通常取待排序列的第一个值)；
将 $j$ 指向的值和基准值进行比较，若当前值大于基准值则 $j$ 自增1，继续比较，直至找到第一个小于基准值的值；
将 $j$ 指向的值和 $i+1$ 指向的值交换，并将 $i$ 和 $j$ 都自增1；
重复进行步骤2和步骤3，直到 $j$ 大于等于 $end$ 结束；
交换基准值和i指向的值，该部分结束。

从描述来看， $i$ 只有在 $a[i+1]$ 和 $a[j]$ 发生交换时才自加 $1$ ，而能过通过 $while$ 搜索的 $a[j]$ 值必定小于 $base$ ，又由于 $i$ 从 $0$ 开始取值，从而会将整个list中的所有小于 $base$ 的值搬到 $i$ 值的前面。

Conquer部分和Combine部分和上面相同

算法实现如下：

import random

def partition(arr, start, end):
    i = start
    j = start + 1
    # here we use a randomized quicksort algorithm.
    k = random.randint(start, end-1)
    arr[i], arr[k] = arr[k], arr[i]
    while j<end:
        while j<end and arr[j] >= arr[start]:
            j += 1
        if j<end:
            arr[i+1], arr[j] = arr[j], arr[i+1]
            i += 1
            j += 1
    arr[start], arr[i] = arr[i], arr[start]
    return i

def quick_sort(arr, start, end):
    if start >= end:
        return
    i = partition(arr, start, end)
    quick_sort(arr, start, i)
    quick_sort(arr, i+1, end)

if __name__ == '__main__':
    arr = [random.randint(1, 10000) for _ in range(10000)]
    quick_sort(arr, 0, len(arr))
    print(arr)

7 堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 $O(nlogn)$ ，它也是不稳定排序。二叉堆可以分成两种形式：最大堆和最小堆。最大堆的父节点值不小于对应的左右子节点值，最小堆的父节点值不大于相应的子节点值。
对于最大堆
$A[PARENT(i)] \geq A[i]$
对于最小堆
$A[PARENT(i)] \leq A[i]$

最大堆和最小堆

假设节点下标从0开始，二叉堆具有的一些性质：

若父节点的下标为 $0$ ，则左子节点的下标是 $2i+1$ ，有子节点的下标是 $2i+2$
当用数组表示n个元素的堆时，叶节点的下标是 $\lfloor (n/2) \rfloor$ , $\lfloor (n/2)+1 \rfloor$ ,..., $n-1$ 。
如果将一个包含n个元素的数组看成是一颗完全二叉堆，那么堆的高度是 $\Theta(logn)$ ，一些基本操作的运行时间至多与堆的高度成正比，即时间复杂度为 $O(logn)$ 。

升序排列数组采用最大堆，降序排列采用最小堆
堆排序的过程包含3步：

（最重要的一步）维护堆：假定调用该步骤之前堆已经是最大二叉堆，那么插入一个新值以后可能不满足堆的性质，需要对新堆进行维护。将A[i]的值与其子节点进行比较，若大于子节点值，那么程序结束，反之需要交换父节点和最大的子节点的值，交换以后子节点可能又不满足最大堆的性质，需要递归的维护堆，直到达到叶节点时退出递归，程序结束。
建立堆：i遍历所有的父节点，对堆进行维护即可。注意，根据性质2，父节点从 $\lfloor (n/2)-1 \rfloor$ 取值到 $0$
堆排序：首先建立最大堆，然后将根节点与最后一个子节点进行交换，并将堆的规模向前缩小1，然后对堆进行调整，再将根节点与最后一个子节点交换，将堆规模缩小1，重复进行，完成排序。

python实现如下：

import random
def max_heapify(a, i, n):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < n and a[left] > a[largest]:
        largest = left
    if right < n and a[right] > a[largest]:
        largest = right
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest, n)

def build_max_heap(a):
    n = len(a)
    for i in range(n//2-1, -1, -1):
        max_heapify(a, i, n)

def heap_sort(a):
    n = len(a)
    build_max_heap(a)
    for i in range(n-1):
        a[0], a[n-1-i] = a[n-1-i], a[0]
        max_heapify(a, 0, n-1-i)

a7 = [random.randint(0, 100) for _ in range(20)]
print(a7)
heap_sort(a7)
print(a7)

给出C++版本的堆排序

#include <bits/stdc++.h>
using namespace std;

void max_heapify(vector<int> &nums, size_t i, size_t n)
{
    size_t largest = i;
    size_t left = 2*i + 1;
    size_t right = 2*i + 2;

    if ((left < n) && (nums[left] > nums[largest]))
        largest = left;
    if ((right < n) && (nums[right] > nums[largest]))
        largest = right;

    if (largest != i)
    {
        swap(nums[i], nums[largest]);
        max_heapify(nums, largest, n);
    }
}

void build_max_heapify(vector<int>& nums)
{
    size_t n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        max_heapify(nums, i, n);
}

void heap_sort(vector<int>& nums)
{
    size_t n = nums.size();
    build_max_heapify(nums);
    for (size_t i = 0; i < n; i++)
    {
        swap(nums[0], nums[n - 1 - i]);
        max_heapify(nums, 0, n - 1 - i);
    }
}

int main()
{
    vector<int> nums = { 4, 7, 6, 1, 0, 3, 2 };
    heap_sort(nums);
    for (auto c : nums)
        cout << c << " ";
    cout << endl;
}

8 计数排序

计数排序假设 $n$ 个输入元素的每一个都是在 $0$ 到 $k$ 区间内取值的整数(数据分布比较集中)，其中 $k$ 为某个整数。当 $k=O(n)$ 时，排序的时间复杂度为 $O(n)$ 。

计数排序的基本思想是：对每一个输入元素 $x$ 确定小于 $x$ 的元素个数，利用这一信息就可以直接把 $x$ 放在它在输出数组上的位置上了。

计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。

def count_sort(a):
    n = len(a)
    k = max(a)
    b = [0] * n
    c = [0] * (k+1)
    for i in range(n):
        c[a[i]] += 1
    for i in range(1, k+1):
        c[i] += c[i-1]
    # The coordinates of a and b in the book introduction to algorithm are from 1 to n,
    # here we from 0 to n-1, so need to subtract 1 from the element of c.
    for i in range(k+1):
        c[i] -= 1
    for i in range(n-1, -1, -1):
        b[c[a[i]]] = a[i]
        c[a[i]] -= 1
    return b

在待排序数据如下时(n和k的规模相当)$)

import random
arr = [random.randint(1, 1000000) for _ in range(1000000)]

在本机上运行随机化快速排序算法时间为8.99299693107605秒，运行计数排序时间为2.281738042831421秒

9 基数排序

基数排序的基本思想是先按照最低有效位对数组进行排序，然后按照次低有效位进行排序，直到最高位，并且要求按位排序算法必须稳定。基数排序类似于桶排序，桶的数量为10。

基数排序示意图

python 实现如下

import random
def radix_sort(a):
    i = 0
    j = len(str(max(a)))
    while i < j:
        s = [[] for _ in range(10)]
        for x in a:
            s[int(x / 10**i % 10)].append(x)
        a.clear()
        for x in s:
            for y in x:
                a.append(y)
        i += 1

a9 = [random.randint(0, 100) for _ in range(20)]
print(a9)
radix_sort(a9)
print(a9)

10 桶排序

快速排序是将集合拆分为两个值域，这里称为两个桶，再分别对两个桶进行排序，最终完成排序。桶排序则是将集合拆分为多个桶，对每个桶进行排序，则完成排序过程。两者不同之处在于，快排是在集合本身上进行排序，属于原地排序方式，且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间，在额外空间上对桶进行排序，避免了构成桶过程的元素比较和交换操作，同时可以自主选择恰当的排序算法对桶进行排序。

当然桶排序更是对计数排序的改进，计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。桶排序则是弱化了这种浪费情况，将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。

桶排序示意图

这里仅考虑最简单的情况，即采用最多的桶对元素进行计数，再按照桶输出元素即可
python实现如下

import random
def bucket_sort(a):
    n = len(a)
    k = max(a) + 1
    b = [0] * k
    for i in range(n):
        b[a[i]] += 1
    a.clear()
    for i in range(k):
        t = [i] * b[i]
        a.extend(t)

a10 = [random.randint(0, 100) for _ in range(20)]
print(a10)
bucket_sort(a10)
print(a10)

可以看到，桶排序类似于计数排序，上面的实现时间复杂度在所有的实现里最低，当数据的分布比较稀疏时将带来较大的内存空间浪费，还可以改进。具体来说，可以减少桶的数量，并在桶的内部应用稳定排序算法，从而在提高了时间复杂度的前提下极大的改善了空间复杂度。

排序算法

排序算法

0 算法概述

0.1 算法分类

0.2 算法复杂度

0.3 相关概念

1 冒泡排序

2 选择排序

3 插入排序

4 希尔排序

5 归并排序

6 快速排序

7 堆排序

8 计数排序

9 基数排序

10 桶排序

相关阅读更多精彩内容

友情链接更多精彩内容