【Python】Numpy排序函数详解

简介

np.sort是最常用的排序函数，其输入参数中，axis可以指定排序的坐标轴，其最常用的使用方法如下

>>> x = np.random.rand(2,4)
>>> x
array([[0.92849373, 0.18556701, 0.47361308, 0.63378477],
       [0.25428974, 0.94955477, 0.74649189, 0.945536  ]])
>>> np.sort(x, axis=0)
array([[0.25428974, 0.18556701, 0.47361308, 0.63378477],
       [0.92849373, 0.94955477, 0.74649189, 0.945536  ]])
>>> np.sort(x,axis=1)
array([[0.18556701, 0.47361308, 0.63378477, 0.92849373],
       [0.25428974, 0.74649189, 0.945536  , 0.94955477]])
1
2
3
4
5
6
7
8
9
10

numpy中针对数组排序，实现了多种不同的算法，在sort中，通过kind参数可以选择排序方案

上表中✅表示$O(n\log n)$。

由于本文主要讲解np.sort的用法，所以下面堆这四种kind做一个简要的说明，而不去深挖其实现的细节。

quicksort

其中，在最新的numpy中，quicksort采用的并不是经典的快排算法，而是改良后的introsort算法。

快排算法大家都非常熟悉了，其简单的Python示意如下

def qSort(arr):
    if len(arr) < 1:
        return arr
    midValue = arr[len(arr)//2]
    L = [x for x in arr if  x < midValue]
    M = [x for x in arr if x == midValue]
    R  = [x for x in arr if x > midValue]
    return qSort(L) + M + qSort(R)

print(qSort([3,34,56,7,89,2,4]))
1
2
3
4
5
6
7
8
9
10

由于不断地二分，使得迭代次数从经典插入的$n$次下降为${\log }_{2}N$次，突破了$n^2$的限制，从而获得了快排的美名。

但从上面的代码也可以看到，首先，当元素个数较少时，快排是体现不出性能的；其次，当元素个数较多时，会产生非常深的递归，造成较大的内存开销。

introSort针对快排的这两个弱点，做了如下优化

1. 当递归到某一深度，arr的元素个数较少时，采取插入排序
2. 当递归的层次过深，则更改排序策略，使用堆排序

堆排序

堆排序是建立在最大堆或者最小堆这种数据结构之上的，所谓最小堆，本质是一个完全二叉树，要求父节点不大于其所有子节点。

最小堆的完全二叉树结构，决定了树高在${\log }_2(n+1)$的水平，从而使得自上而下遍历最大堆的时间复杂度降低到${\log }_2(n+1)$。

根据上图可知，若父节点的序号为$n$，则左子节点序号为$2n+1$,右子节点序号为$2n+2$。

可以将上图理解为一个排好序的最小堆，如果1位变成15，那么这个节点将违反最小堆的原则，经过比对，应该调换15和3的位置。调换之后，15仍然比7和8大，则继续调换15和7的位置，则这个最小堆变为

归并排序

归并排序是算法导论中介绍的第一种使用分治策略的排序算法，基本思路是将数组拆分成子数组，然后令子数组有序，再令数组之间有序，则可以使整个数组有序。其算法步骤如下：

设数组有$n$个元素， { a 0 , a 1 , … , a n } \{a_0,a_1,\ldots,a_n\} {a0​,a1​,…,an​}

1. 如果数组元素大于2，则将数组分成左数组和右数组，否则将数组转成有序数组
2. 对左数组和右数组执行1操作。
3. 合并左数组和右数组。

TimSort和introSort相似，都是缝合得比较厉害的排序算法，其中introSort是C++标准库中的快排方案，而TimSort则是Tim Peters于2002年首先应用在Python的。

timsort的基本思路是最大限度地利用数组中已经存在的有序子数组，Tim将这些已经有序的子数组称为run，排序过程中，像归并排序一样，不断地将迭代元素放入每个run中，同时对不同的run进行合并，直到只剩下一个run。