• A.6 更多有关排序的话题
    • 间接排序：argsort和lexsort
    • 其他排序算法
    • 部分排序数组
    • numpy.searchsorted：在有序数组中查找元素

    A.6 更多有关排序的话题

    跟Python内置的列表一样，ndarray的sort实例方法也是就地排序。也就是说，数组内容的重新排列是不会产生新数组的：

    1. In [160]: arr = np.random.randn(6)
    3. In [161]: arr.sort()
    5. In [162]: arr
    6. Out[162]: array([-1.082 ,  0.3759,  0.8014,  1.1397,  1.2888,  1.8413])

    在对数组进行就地排序时要注意一点，如果目标数组只是一个视图，则原始数组将会被修改：

    1. In [163]: arr = np.random.randn(3, 5)
    3. In [164]: arr
    4. Out[164]: 
    5. array([[-0.3318, -1.4711,  0.8705, -0.0847, -1.1329],
    6.        [-1.0111, -0.3436,  2.1714,  0.1234, -0.0189],
    7.        [ 0.1773,  0.7424,  0.8548,  1.038 , -0.329 ]])
    9. In [165]: arr[:, 0].sort()  # Sort first column values in-place
    11. In [166]: arr
    12. Out[166]: 
    13. array([[-1.0111, -1.4711,  0.8705, -0.0847, -1.1329],
    14.        [-0.3318, -0.3436,  2.1714,  0.1234, -0.0189],
    15.        [ 0.1773,  0.7424,  0.8548,  1.038 , -0.329 ]])

    相反，numpy.sort会为原数组创建一个已排序副本。另外，它所接受的参数（比如kind）跟ndarray.sort一样：

    1. In [167]: arr = np.random.randn(5)
    3. In [168]: arr
    4. Out[168]: array([-1.1181, -0.2415, -2.0051,  0.7379, -1.0614])
    6. In [169]: np.sort(arr)
    7. Out[169]: array([-2.0051, -1.1181, -1.0614, -0.2415,  0.7379])
    9. In [170]: arr
    10. Out[170]: array([-1.1181, -0.2415, -2.0051,  0.7379, -1.0614])

    这两个排序方法都可以接受一个axis参数，以便沿指定轴向对各块数据进行单独排序：

    1. In [171]: arr = np.random.randn(3, 5)
    3. In [172]: arr
    4. Out[172]: 
    5. array([[ 0.5955, -0.2682,  1.3389, -0.1872,  0.9111],
    6.        [-0.3215,  1.0054, -0.5168,  1.1925, -0.1989],
    7.        [ 0.3969, -1.7638,  0.6071, -0.2222, -0.2171]])
    9. In [173]: arr.sort(axis=1)
    11. In [174]: arr
    12. Out[174]: 
    13. array([[-0.2682, -0.1872,  0.5955,  0.9111,  1.3389],
    14.        [-0.5168, -0.3215, -0.1989,  1.0054,  1.1925],
    15.        [-1.7638, -0.2222, -0.2171,  0.3969,  0.6071]])

    你可能注意到了，这两个排序方法都不可以被设置为降序。其实这也无所谓，因为数组切片会产生视图（也就是说，不会产生副本，也不需要任何其他的计算工作）。许多Python用户都很熟悉一个有关列表的小技巧：values[::-1]可以返回一个反序的列表。对ndarray也是如此：

    1. In [175]: arr[:, ::-1]
    2. Out[175]: 
    3. array([[ 1.3389,  0.9111,  0.5955, -0.1872, -0.2682],
    4.        [ 1.1925,  1.0054, -0.1989, -0.3215, -0.5168],
    5.        [ 0.6071,  0.3969, -0.2171, -0.2222, -1.7638]])

    间接排序：argsort和lexsort

    在数据分析工作中，常常需要根据一个或多个键对数据集进行排序。例如，一个有关学生信息的数据表可能需要以姓和名进行排序（先姓后名）。这就是间接排序的一个例子，如果你阅读过有关pandas的章节，那就已经见过不少高级例子了。给定一个或多个键，你就可以得到一个由整数组成的索引数组（我亲切地称之为索引器），其中的索引值说明了数据在新顺序下的位置。argsort和numpy.lexsort就是实现该功能的两个主要方法。下面是一个简单的例子：

    1. In [176]: values = np.array([5, 0, 1, 3, 2])
    3. In [177]: indexer = values.argsort()
    5. In [178]: indexer
    6. Out[178]: array([1, 2, 4, 3, 0])
    8. In [179]: values[indexer]
    9. Out[179]: array([0, 1, 2, 3, 5])

    一个更复杂的例子，下面这段代码根据数组的第一行对其进行排序：

    1. In [180]: arr = np.random.randn(3, 5)
    3. In [181]: arr[0] = values
    5. In [182]: arr
    6. Out[182]: 
    7. array([[ 5.    ,  0.    ,  1.    ,  3.    ,  2.    ],
    8.        [-0.3636, -0.1378,  2.1777, -0.4728,  0.8356],
    9.        [-0.2089,  0.2316,  0.728 , -1.3918,  1.9956]])
    11. In [183]: arr[:, arr[0].argsort()]
    12. Out[183]: 
    13. array([[ 0.    ,  1.    ,  2.    ,  3.    ,  5.    ],
    14.        [-0.1378,  2.1777,  0.8356, -0.4728, -0.3636],
    15.        [ 0.2316,  0.728 ,  1.9956, -1.3918, -0.2089]])

    lexsort跟argsort差不多，只不过它可以一次性对多个键数组执行间接排序（字典序）。假设我们想对一些以姓和名标识的数据进行排序：

    1. In [184]: first_name = np.array(['Bob', 'Jane', 'Steve', 'Bill', 'Barbara'])
    3. In [185]: last_name = np.array(['Jones', 'Arnold', 'Arnold', 'Jones', 'Walters'])
    5. In [186]: sorter = np.lexsort((first_name, last_name))
    7. In [187]: sorter
    8. Out[187]: array([1, 2, 3, 0, 4])
    10. In [188]: zip(last_name[sorter], first_name[sorter])
    11. Out[188]: <zip at 0x7fa203eda1c8>

    刚开始使用lexsort的时候可能会比较容易头晕，这是因为键的应用顺序是从最后一个传入的算起的。不难看出，last_name是先于first_name被应用的。

    笔记：Series和DataFrame的sort_index以及Series的order方法就是通过这些函数的变体（它们还必须考虑缺失值）实现的。

    其他排序算法

    稳定的（stable）排序算法会保持等价元素的相对位置。对于相对位置具有实际意义的那些间接排序而言，这一点非常重要：

    1. In [189]: values = np.array(['2:first', '2:second', '1:first', '1:second',
    2. .....:                    '1:third'])
    4. In [190]: key = np.array([2, 2, 1, 1, 1])
    6. In [191]: indexer = key.argsort(kind='mergesort')
    8. In [192]: indexer
    9. Out[192]: array([2, 3, 4, 0, 1])
    11. In [193]: values.take(indexer)
    12. Out[193]: 
    13. array(['1:first', '1:second', '1:third', '2:first', '2:second'],
    14.       dtype='<U8')

    mergesort（合并排序）是唯一的稳定排序，它保证有O(n log n)的性能（空间复杂度），但是其平均性能比默认的quicksort（快速排序）要差。表A-3列出了可用的排序算法及其相关的性能指标。大部分用户完全不需要知道这些东西，但了解一下总是好的。

    表A-3 数组排序算法

    部分排序数组

    排序的目的之一可能是确定数组中最大或最小的元素。NumPy有两个优化方法，numpy.partition和np.argpartition，可以在第k个最小元素划分的数组：

    1. In [194]: np.random.seed(12345)
    3. In [195]: arr = np.random.randn(20)
    5. In [196]: arr
    6. Out[196]: 
    7. array([-0.2047,  0.4789, -0.5194, -0.5557,  1.9658,  1.3934,  0.0929,
    8.         0.2817,  0.769 ,  1.2464,  1.0072, -1.2962,  0.275 ,  0.2289,
    9.         1.3529,  0.8864, -2.0016, -0.3718,  1.669 , -0.4386])
    11. In [197]: np.partition(arr, 3)
    12. Out[197]: 
    13. array([-2.0016, -1.2962, -0.5557, -0.5194, -0.3718, -0.4386, -0.2047,
    14.         0.2817,  0.769 ,  0.4789,  1.0072,  0.0929,  0.275 ,  0.2289,
    15.         1.3529,  0.8864,  1.3934,  1.9658,  1.669 ,  1.2464])

    当你调用partition(arr, 3)，结果中的头三个元素是最小的三个，没有特定的顺序。numpy.argpartition与numpy.argsort相似，会返回索引，重排数据为等价的顺序：

    1. In [198]: indices = np.argpartition(arr, 3)
    3. In [199]: indices
    4. Out[199]: 
    5. array([16, 11,  3,  2, 17, 19,  0,  7,  8,  1, 10,  6, 12, 13, 14, 15,  5,
    6.         4, 18,  9])
    8. In [200]: arr.take(indices)
    9. Out[200]: 
    10. array([-2.0016, -1.2962, -0.5557, -0.5194, -0.3718, -0.4386, -0.2047,
    11.         0.2817,  0.769 ,  0.4789,  1.0072,  0.0929,  0.275 ,  0.2289,
    12.         1.3529,  0.8864,  1.3934,  1.9658,  1.669 ,  1.2464])

    numpy.searchsorted：在有序数组中查找元素

    searchsorted是一个在有序数组上执行二分查找的数组方法，只要将值插入到它返回的那个位置就能维持数组的有序性：

    1. In [201]: arr = np.array([0, 1, 7, 12, 15])
    3. In [202]: arr.searchsorted(9)
    4. Out[202]: 3

    你可以传入一组值就能得到一组索引：

    1. In [203]: arr.searchsorted([0, 8, 11, 16])
    2. Out[203]: array([0, 3, 3, 5])

    从上面的结果中可以看出，对于元素0，searchsorted会返回0。这是因为其默认行为是返回相等值组的左侧索引：

    1. In [204]: arr = np.array([0, 0, 0, 1, 1, 1, 1])
    3. In [205]: arr.searchsorted([0, 1])
    4. Out[205]: array([0, 3])
    6. In [206]: arr.searchsorted([0, 1], side='right')
    7. Out[206]: array([3, 7])

    再来看searchsorted的另一个用法，假设我们有一个数据数组（其中的值在0到10000之间），还有一个表示“面元边界”的数组，我们希望用它将数据数组拆分开：

    1. In [207]: data = np.floor(np.random.uniform(0, 10000, size=50))
    3. In [208]: bins = np.array([0, 100, 1000, 5000, 10000])
    5. In [209]: data
    6. Out[209]: 
    7. array([ 9940.,  6768.,  7908.,  1709.,   268.,  8003., 9037.,   246.,
    8.         4917.,  5262.,  5963.,   519.,  8950.,  7282.,  8183.,  5002.,
    9.         8101.,   959.,  2189.,  2587.,  4681.,  4593.,  7095.,  1780.,
    10.         5314.,  1677.,  7688.,  9281.,  6094.,  1501.,  4896.,  3773.,
    11.         8486.,  9110.,  3838.,  3154.,  5683.,  1878.,  1258.,  6875.,
    12.         7996.,  5735.,  9732.,  6340.,  8884.,  4954.,  3516.,  7142.,
    13.         5039.,  2256.])

    然后，为了得到各数据点所属区间的编号（其中1表示面元[0,100)），我们可以直接使用searchsorted：

    1. In [210]: labels = bins.searchsorted(data)
    3. In [211]: labels
    4. Out[211]: 
    5. array([4, 4, 4, 3, 2, 4, 4, 2, 3, 4, 4, 2, 4, 4, 4, 4, 4, 2, 3, 3, 3, 3, 4,
    6.        3, 4, 3, 4, 4, 4, 3, 3, 3, 4, 4, 3, 3, 4, 3, 3, 4, 4, 4, 4, 4, 4, 3,
    7.        3, 4, 4, 3])

    通过pandas的groupby使用该结果即可非常轻松地对原数据集进行拆分：

    1. In [212]: pd.Series(data).groupby(labels).mean()
    2. Out[212]: 
    3. 2     498.000000
    4. 3    3064.277778
    5. 4    7389.035714
    6. dtype: float64