算法之道（2）排序和统计

问：排序算法千千万，主流的、非主流的，都是前辈们提供的经验，这些算法是现成的，直接拿来用就好，为啥还要学习？

答：学习已有的算法，是为了深层理解算法设计与分析的技术，以便能自行设计算法，证明其正确性和理解其效率。

一、排序算法总结

指标解释如下:

• n代表数据规模，^代表几次方，lg为以2为底的log对数，O代表时间复杂度函数的渐进上界。k代表桶的个数（计数排序的排序值或者基数排序的每一位的取值个数），d代表排序值的位数。
• 稳定性：（1）稳定：如果a原本在b前面且a=b，排序之后a仍然在b的前面。（2）不稳定：排序之后a可能会出现在b的后面。
• 排序方式：（1）In-place：原址的，占用常数内存，不占用额外内存。（2）Out-place：占用额外内存。
• 时间复杂度：一个算法执行所耗费的时间。
• 空间复杂度： 运行完一个程序所需内存的大小。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	In-place	不稳定
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
归并排序	O(n lgn)	O(n lgn)	O(n lgn)	O(n)	Out-place	稳定
堆排序	O(n lgn)	O(n lgn)	O(n lgn)	O(1)	In-place	不稳定
快速排序	O(n lgn)	O(n lgn)	O(n^2)	O(lgn)	In-place	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-place	稳定
基数排序	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	Out-place	稳定
桶排序	O(n+k)	O(n+k)	O(n^2)	O(n+k)	Out-place	稳定
希尔排序	O(n lgn)	O(n lg^2 n)	O(n lg^2 n)	O(1)	In-place	不稳定

• 冒泡排序、快速排序属于交换排序。直接插入排序和希尔排序属于插入排序。简单选择排序和堆排序属于选择排序
• 归并排序和快速排序，是通过分治法消减时间复杂度

二、冒泡排序（Bubble Sort）

算法描述

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

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

python代码

# 往后冒泡
def bubble_sort(lists):
    for i in range(len(lists)-1):
        for j in range(len(lists)-i-1):
            if (lists[j] > lists[j+1]):
                tmp = lists[j]
                lists[j] = lists[j+1]
                lists[j+1] = tmp
            print(lists)

numbers = [9,3,1,8,6,5,7,2,4]
bubble_sort(numbers)

gif图解

三、选择排序（Selection Sort）

算法描述

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

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趟结束，数组有序化了。

python代码

def selection_sort(lists):
    for i in range(len(lists)):
        x = i
        for j in range(i, len(lists)):
            if lists[j] < lists[x]:
                x = j
        lists[i], lists[x] = lists[x], lists[i]
        print(lists)
    return lists

numbers = [9,3,1,8,6,5,7,2,4]
selection_sort(numbers)

gif图解

四、插入排序（Insertion Sort）

算法描述

说到插入排序，想想斗地主时，摸牌摆牌的流程。

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

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

python代码

def insertion_sort(lists):          
    for j in range(1,len(lists)):   
        key =lists[j]               
        i=j-1                       
        while i>=0 and lists[i]>key:
            lists[i+1]=lists[i]     
            i=i-1                   
            lists[i+1]=key          
        print(lists)
    return lists

numbers = [9,3,1,8,6,5,7,2,4]
insertion_sort(numbers)

gif图解

五、归并排序（Merge Sort）

算法描述

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

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

python代码

import math

def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    num = math.ceil(len(lists) / 2)
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

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

numbers = [5,4,2,3,1,6,7]
result=merge_sort(numbers)
print(result)

gif图解

六、堆排序（Heap Sort）

堆

二叉堆，是一种数据结构，可以被看成一个近似的完全二叉树，树上的每个节点对应数组中的一个元素。除了最底层外，该树是充满的，而且是从左向右填充。

给定一个节点的小标i，可得到它的父节点、左孩子和右孩子的下标分别为[i/2]、2i、2i+1。

二叉堆分为两种形式：最大堆和最小堆。最大堆满足A[PARENT(i)]>= A[i]，即某个结点的值最多与其父节点一样大。堆排序算法中，我们使用的是最大堆。最小堆通常用于构造优先队列，戴克斯特拉算法。

算法描述

是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序集合了插入排序和归并排序的算法优点，同时具备了插入排序的空间原址性，和归并排序的时间复杂度O(n lgn)。

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后 再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元 素个数为n-1，则整个排序过程完成。

python代码

def heap_sort(lists):
    # MAX-HEAPIFY过程，维护堆的性质，复杂度T(n)=O(lgn)
    def heap_adjust(parent):
        child = 2 * parent + 1  # left child
        while child < len(heap):
            if child + 1 < len(heap):
                if heap[child + 1] > heap[child]:
                    child += 1  # right child
            if heap[parent] >= heap[child]:
                print(heap)
                break
            heap[parent], heap[child] = \
                heap[child], heap[parent]
            parent, child = child, 2 * child + 1
        print(heap)

    heap, lists = lists.copy(), []

    # BUILD-MAX-HEAP过程，建堆，复杂度O(nlgn)
    for i in range(len(heap) // 2, -1, -1):
        heap_adjust(i)

    # HEAPSORT过程，原址排序，n-1次调用MAX-HEAPIFY，每次O(lgn),复杂度是O(nlgn)
    while len(heap) != 0:
        heap[0], heap[-1] = heap[-1], heap[0]
        lists.insert(0, heap.pop())
        heap_adjust(0)
    return lists

numbers = [5,4,2,3,1,6,7]
result=heap_sort(numbers)
print(result)

gif图解

七、快速排序（Quick Sort）

算法描述

名字简单粗暴，就是快，尤其是数据量巨大的情况下。虽然它是一种最坏情况时间复杂度为O(n^2)的排序算法，但通常是实际排序应用中最好的选择，因为它平均性能非常好，期望时间复杂度为O（nlgn），且隐含的常数因子非常小，且能原址排序。

快速排序的基本思想：和归并一样使用了分治思想，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

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

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

python代码

def quick_sort(lists):
    def recursive(begin, end):
        if begin > end:
            return
        l, r = begin, end
        pivot = lists[l]
        while l < r:
            while l < r and lists[r] > pivot:
                r -= 1
            while l < r and lists[l] <= pivot:
                l += 1
            lists[l], lists[r] = lists[r], lists[l]
        lists[l], lists[begin] = pivot, lists[l]
        recursive(begin, l - 1)
        recursive(r + 1, end)

    recursive(0, len(lists) - 1)
    return lists

numbers = [5,4,2,3,1,6,7]
result=quick_sort(numbers)
print(result)

gif图解

时间复杂度

快速排序的性能取决于划分是否平衡。

最坏情况下，划分产生的两个子问题分别包含n-1个元素和0个元素时，每次递归调用都出现这种划分，划分的时间复杂度为O(n)，0个元素数组的递归为O(1)，因此算法运行时间的递归式为：
T(n)=T(n-1)+T(0)+O(n)=T(n-1)+O(n)，因此T(n)=O(n^2)。

最好情况下，划分得到的子问题的规模都不大于n/2，递归式为：
T(n)=2T(n/2)+O(n)，基本就是归并排序的递归式，参考第1节基础内容，为T(n)=O(nlgn)。

平衡情况下，假设划分算法总是产生9:1的划分，递归式为：T(n)=T(9n/10)+T(n/10)+cn，在深度$\log_{10}n$之上，每一层的代价都是cn，递归深度在$\log_{10/9}n$终止前，每层代价至多为cn。因此总代价为O(nlgn)。

对于平均情况的直观观察，一个差的划分后面接着一个好的划分，这个组合产生出三个子数组，大小分别为0、(n-1)/2-1、(n-1)/2，这一组合的划分代价为O(n-1)+O(n)=O(n)，和直接划分成大小为(n-1)/2的两个子数组的划分代价O(n)是相同的。

当然，针对随机化版本的快速排序，有严格的公式证明，较为复杂，可得出快速排序算法的随机划分的期望运行时间为O(nlgn)。

分割线

以上的排序，都是属于比较排序，有几种能在O(nlgn)时间内排序的算法，归并和堆排序达到了最坏情况下的上界，是渐进最优的，快速排序在平均情况下达到该上界。任何比较排序在最坏情况下都要经过Ω(nlgn)次比较。

可以把比较排序抽象成一颗决策树模型，一颗高度为h，有l个可达叶节点的决策树，它对应一个对n个元素所有的比较排序，有

$n! \le l \le 2^h$

两边取对数：

$h \ge \lg(n!) = \Omega(n\lg n)$

因此在最坏情况下，任何比较排序算法都需要做nlgn次比较。

以下为3种线性时间复杂度的排序算法：计数排序、基数排序和桶排序，下界可以突破Ω(nlgn)，都利用了桶的概念。

八、计数排序（Counting Sort）

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围（0到k之间）的整数。如果排序的数据值很大，则空间复杂度很大。

具体算法描述如下：

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

python代码

def count_sort(lists):
    n=len(lists)
    num=max(lists)
    count=[0]*(num+1)
    for i in range(0,n):
        count[lists[i]]+=1
    arr=[]
    for i in range(0,num+1):
        for j in range(0,count[i]):
            arr.append(i)

    return arr;

numbers = [5,4,2,3,1,6,7]
result=count_sort(numbers)
print(result)

九、基数排序（Radix Sort）

基数排序是一种用在卡片排序机上的算法，针对n个d位数，

具体算法描述如下：

1. 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。
2. 接下来将第1步桶中的数值重新串接起来，根据十位数的数值，再次将它们分配至编号0到9的桶子中。
3. 继续串联起来，然后根据百位、千位，直到最高位数为止。

def radix_sort(lists):
    i = 0  #初始为个位排序
    n = 1  #最小的位数置为1（包含0）
    max_num = max(lists)  #得到带排序数组中最大数
    while max_num > 10**n:  #得到最大数是几位数
        n += 1
    while i < n:
        bucket = {}      #用字典构建桶
        for x in range(10):
            bucket.setdefault(x, [])   #将每个桶置空
        for x in lists:    #对每一位进行排序
            radix =int((x / (10**i)) % 10)   #得到每位的基数
            bucket[radix].append(x) #将对应的数组元素加入到相应位基数的桶中
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0:   #若桶不为空
                for y in bucket[k]:   #将该桶中每个元素
                    lists[j] = y      #放回到数组中
                    j += 1
        i += 1
    return lists

numbers = [5,4,2,3,1,6,7]
result=radix_sort(numbers)
print(result)

十、桶排序（Bucket Sort）

桶排序与计数排序类似，但假设输入数据服从均匀分布，输入数据是随机过程生成，且元素均匀、独立的分布在[0,1)区间上。桶排序将[0,1)区间划分为n个相同大小的子区间，称为桶。

• 基数排序和计数排序都可以看作是桶排序。
• 计数排序本质上是一种特殊的桶排序，当桶的个数取最大(最大值-最小值+1)的时候，就变成了计数排序。
• 基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分；基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。

综上，计数排序适用于最大值和最小值差距尽可能小，桶排序适用于元素尽可能均匀分布，基数排序必须是非负整数，且位数d小（即值小）。

至于时间复杂度方面，推算较为复杂。还涉及到一个桶里的插入排序的时间代价，结论是桶排序的期望运行时间为O(n)，即使输入数据不服从均匀分布，桶排序仍然可以在线性时间内完成（满足所有桶的大小的平方和与总元素数呈线性关系的情况下）。

十一、不同排序运行时间测试

世上没有十全十美的排序算法，有优点就会有缺点，即使是快速排序算法，因此需要根据合适的场景做选择。

下面为针对不同排序算法的运行时间统计

随机生成

当然也可以通过np函数生成，这里持久化成文件可以方便不同算法在相同数据情况下的时间比较。

from random import random
from json import dumps, loads


# 生成随机数文件
def dump_random_array(file='numbers.json', size=10 ** 4):
    fo = open(file, 'w', 1024)
    numlst = list()
    for i in range(size):
        numlst.append(int(random() * 10*1000 ))
    fo.write(dumps(numlst))
    fo.close()
    
# 加载随机数列表
def load_random_array(file='numbers.json'):
    fo = open(file, 'r', 1024)
    try:
        numlst = fo.read()
    finally:
        fo.close()
    return loads(numlst)

执行时间统计函数

只需要将@exectime加入到排序函数中即可。

from _datetime import datetime

# 显示函数执行时间
def exectime(func):
    def inner(*args, **kwargs):
        begin = datetime.now()
        result = func(*args, **kwargs)
        end = datetime.now()
        inter = end - begin
        print('time:{0}.{1}'.format(
            inter.seconds,
            inter.microseconds
        ))
        return result

    return inner

十二、顺序统计量算法

在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素，最小值是第1个，最大值是第n个，中位数是第[(n+1)/2]个。

• 找出最大值或最小值，需要n-1次比较。
• 同时找出最大值或最小值，最多需要3[n/2]次比较。