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

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

    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. Out[175]: 
    2. array([[ 1.3389,  0.9111,  0.5955, -0.1872, -0.2682],
    3.        [ 1.1925,  1.0054, -0.1989, -0.3215, -0.5168],

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

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

    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]])
    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被应用的。

    稳定的（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列出了可用的排序算法及其相关的性能指标。大部分用户完全不需要知道这些东西，但了解一下总是好的。

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

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

    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：

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

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