Nov 7, 2018

排序算法知多少

大学里学的第一门编程语言是 c++，c++ 的课程中接触的第一种排序算法是冒泡排序，这已经过去八年，很惭愧的是到目前只了解冒泡排序和插入排序两种，作为一名合格的程序猿也应该了解了解其它的排序算法吧！所以开本文记录整理网上所谓的十大排序算法。

排序算法概述

网上常见的排序算法有十种：冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、计数排序、基数排序、桶排序。

排序算法分类

上面十大排序算法按照非线性时间比较类排序^[非线性时间比较类排序: 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 $O (n \log n)$ ，因此称为非线性时间比较类排序。]和线性时间非比较类排序^[线性时间非比较类排序: 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。]进行分类：

![](https://pichome-1254392422.cos.ap-chengdu.myqcloud.com/blog/img/Surface Pro 4 – [email protected])

排序算法对比

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

排序算法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度(平均)	稳定性
冒泡排序	$O (n^{2})$	$O (n^{2})$	$O (n)$	$O (1)$	稳定
快速排序	$O (n \log_{2} n)$	$O (n^{2})$	$O (n \log_{2} n)$	$O (n \log_{2} n)$	不稳定
插入排序	$O (n^{2})$	$O (n^{2})$	$O (n)$	$O (1)$	稳定
希尔排序	$O (n^{1.3})$	$O (n^{2})$	$O (n)$	$O (1)$	不稳定
选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	不稳定
堆排序	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (1)$	不稳定
归并排序	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (n)$	稳定
计数排序	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (n + k)$	稳定
基数排序	$O (n + k)$	$O (n^{2})$	$O (n)$	$O (n + k)$	稳定
桶排序	$O (n \cdot k)$	$O (n \cdot k)$	$O (n \cdot k)$	$O (n + k)$	稳定

冒泡排序

2018年11月08日

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作重复地进行直到没有元素需要交换，即排序完成。这个算法进行时越小的元素会经交换慢慢“浮”到数列的顶端，故得“冒泡之名。

冒泡排序步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。

为了方便理解，以数组 [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23] 排序为例，排序过程如以下动图：

冒泡排序示例代码

python3 实现冒泡算法封装成函数如下：

def bubble_sort(numlist):
    length = len(numlist)
    for i in range(length - 1):
        for j in range(length -1 - i):
            if numlist[j] > numlist[j + 1]:
                numlist[j], numlist[j + 1] = numlist[j + 1], numlist[j]
    return numlist

进行测试，简单测试代码如下：

if __name__ == '__main__':
    l = [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23]
    print(f'sorting... {l}')
    l = bubble_sort(l)
    print(f'sorted  -> {l}')

运行脚本，一切OK：

$ python3 bubble.py
sorting... [12, 3, 45, 65, 54, 34, 78, 9, 10, 23]
sorted  -> [3, 9, 10, 12, 23, 34, 45, 54, 65, 78]

快速排序

2018年11月09日

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 $n$ 个项目要 $O (n \log n)$ （大O符号）次比较。在最坏状况下则需要 $O (n^{2})$ 次比较，但这种状况并不常见。事实上，快速排序 $Θ (n \log n)$ 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

快速排序步骤

快排采用和归并排序相同的分而治之的思想，将待排序数组分成左右两个子数组，对两部分子数组独立排序。当子数组均有序时，整个数组也就有序了^[Python实现快排及其可视化——快排基本原理]。

将原始数组 data 随机打乱，以消除对输入的依赖（本步可选）
选择数组的某个元素作切分元素 v，比如首个元素 data[0]
切分数组
- 从左往右找到第一个大于切分元素v的元素 data[i]
- 从右到左找到第一个小于切分元素v的元素 data[j]
- 交换 data[i] 与 data[j]
- 重复以上三步直到 i >= j
- 交换 data[j] 与切分元素 data[0]
递归调用，对切分后的左侧子数组进行排序
递归调用，对切分后的右侧子数组进行排序

为了方便理解，以数组 [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23] 排序为例，排序过程如以下动图:

快速排序示例代码

python3 实现快速排序封装成函数如下(代码中选择最后一个元素作切分元素 v)：

    if lo < hi:
        p = partition(data, lo, hi)
        quicksort(data, lo, p)
        quicksort(data, p+1, hi)
    return

def partition(data, lo, hi):
    pivot = data[hi-1]
    i = lo - 1
    for j in range(lo, hi):
        if data[j] < pivot:
            i += 1
            data[i], data[j] = data[j], data[i]
    if data[hi-1] < data[i+1]:
        data[i+1], data[hi-1] = data[hi-1], data[i+1]
    return i+1

测试实现的快速排序算法：

if __name__ == '__main__':
    l = [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23]
    print(f'sorting... {l}')
    quicksort(l, 0, len(l))
    print(f'sorted:    {l}')

测试一下：

$ python3 quick.py
sorting... [12, 3, 45, 65, 54, 34, 78, 9, 10, 23]
sorted:    [3, 9, 10, 12, 23, 34, 45, 54, 65, 78]

插入排序

2018年11月10日

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 $O (1)$ 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序步骤

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

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

为了方便理解，以数组 [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23] 排序为例，排序过程如以下动图：

插入排序示例代码

def insert_sort(data):
    n = len(data)
    if n == 1:
        return data
    for i in range(1, n):
        for j in range(i, 0, -1):
            if data[j] < data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]
            else:
                break
    return data

测试一下：

if __name__ == '__main__':
    l = [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23]
    print(f'sorting... {l}')
    l = insert_sort(l)
    print(f'sorted:    {l}')

结果：

$ python3 insert.py
sorting... [12, 3, 45, 65, 54, 34, 78, 9, 10, 23]
sorted:    [3, 9, 10, 12, 23, 34, 45, 54, 65, 78]

希尔排序

2018年11月11日

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

Donald Shell最初建议步长选择为 $\frac{n}{2}$ 并且对步长取半直到步长达到1。虽然这样取可以比 $O (n^{2})$ 类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了^[已知的最好步长序列是由 Sedgewick 提出的 (1, 5, 19, 41, 109,...)，该序列的项来自 $9 \times 4^{i} - 9 \times 2^{i} + 1$ 和 $2^{i + 2} \times (2^{i + 2} - 3) + 1$ 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。——希尔排序 @ 维基百科 ]。

希尔排序步骤

这里步长选择为 $\frac{n}{2}$ 并且对步长取半直到步长达到1的序列：

序列个数为 $n$ ，初始化步长 $s t e p s i z e = n$ 。

取新步长为 $\frac{s t e p s i z e}{2}$ ，如果 $s t e p s i z e < 1$ 算法结束
从第一个元素开始，该元素可以认为已经被排序
取出按照新步长 $s t e p s i z e$ 的下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到按新步长的下一位置
重复步骤 4，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置
重复步骤 3~6，直到按照新步长 $s t e p s i z e$ 的插入排序结束
重复 1～7步骤

为了方便理解，以数组 [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23] 排序为例，排序过程如以下动图：

希尔排序示例代码

def shell_sort(numlist):
    n = len(numlist)
    # 初始步长
    stepsize = n // 2
    while stepsize > 0:
        for i in range(stepsize, n):
            # 每个步长进行插入排序
            temp = numlist[i]
            j = i
            # 插入排序
            while j >= stepsize and numlist[j - stepsize] > temp:
                numlist[j] = numlist[j - stepsize]
                j -= stepsize
            numlist[j] = temp
        # 得到新的步长
        stepsize = stepsize // 2
    return numlist

测试一下：

if __name__ == '__main__':
    l = [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23]
    print(f'sorting... {l}')
    l = shell_sort(l)
    print(f'sorted:    {l}')

结果：

$ python3 shell.py
sorting... [12, 3, 45, 65, 54, 34, 78, 9, 10, 23]
sorted:    [3, 9, 10, 12, 23, 34, 45, 54, 65, 78]

选择排序

2018年11月12日

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 $n$ 个元素的表进行排序总共进行至多 $n - 1$ 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序步骤

选择未排序的序的首元素作为作为比对元素
往后进行比较，找到最小的元素与首位的元素互换位置
重复 1～2 步一直到只剩一个序列

为了方便理解，这里以对序列 [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23] 排序为例展示排序过程动画如下：

选择排序示例代码

def select_sort(numlist):
    length = len(numlist)
    for i in range(length-1):
        min_index = i
        for j in range(i+1, length):
            if numlist[min_index] > numlist[j]:
                min_index = j
        if min_index != i:
            numlist[min_index], numlist[i] = numlist[i], numlist[min_index]
    return numlist

测试一下封装的算法：

if __name__ == '__main__':
    l = [12, 3, 45, 65, 54, 34, 78, 9 ,10, 23]
    print(f'sorting... {l}')
    print(f'sorrted    {select_sort(l)}')

测试结果：

$ python3 select.py
sorting... [12, 3, 45, 65, 54, 34, 78, 9, 10, 23]
sorrted    [3, 9, 10, 12, 23, 34, 45, 54, 65, 78]

堆排序

归并排序

计数排序

基数排序

桶排序

未完待续。。。

打赏作者

访问量 348

3 评论

Anonymous Chrome 85.0.4183.83 Windows 10/11

2020-09-02回复

快速排序的空间复杂度应该是O(1)才对

Anonymous Chrome 71.0.3578.98 Windows 10/11

2019-01-05回复

太棒了

Anonymous Chrome 70.0.3538.110 macOS 10.14.2

2018-12-15回复

这是一天写了一个哈哈哈

5km Safari 12.0 iOS 12.1.1

@Anonymous

对呀，还剩好几个，后面有时间再继续更新😅😂