排序算法知多少

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

2018111115418975029904.gif

排序算法概述

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

排序算法分类

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

![](https://pichome-1254392422.cos.ap-chengdu.myqcloud.com/blog/img/Surface Pro 4 – 1@2x.png)

排序算法对比

时间复杂度^[时间复杂度:对排序数据的总的操作次数。反映当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)是一种简单的排序算法。它重复遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作重复地进行直到没有元素需要交换,即排序完成。这个算法进行时越小的元素会经交换慢慢“浮”到数列的顶端,故得“冒泡之名。

冒泡排序步骤

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

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

2018111115418975029904.gif

冒泡排序示例代码

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)$ 次比较,但这种状况并不常见。事实上,快速排序 $\Theta (n\log n)$ 通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。

快速排序步骤

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

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

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

20181111154194773939997.gif

快速排序示例代码

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 在数组上实现。具体算法描述如下:

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

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

20181111154194998895578.gif

插入排序示例代码

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. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

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

Donald Shell最初建议步长选择为 $\frac{n}{2}$ 并且对步长取半直到步长达到1。虽然这样取可以比 $\mathcal {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$,初始化步长 $stepsize = n$。

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

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

20181112154195404360778.gif

希尔排序示例代码

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. 往后进行比较,找到最小的元素与首位的元素互换位置
  3. 重复 1~2 步一直到只剩一个序列

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

20181112154200663696412.gif

选择排序示例代码

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]

堆排序

归并排序

计数排序

基数排序

桶排序

未完待续。。。