numpy argsort排序如何让其稳定排序

2023-08-03 07:03 由 caoeryingzi 发表于 #后端开发

numpy.argsort(a, axis=-1, kind=None, order=None)

Parameters:

aarray_like: Array to sort.
axis int or None, optional: Axis along which to sort. The default is -1 (the last axis). If None, the flattened array is used.
kind {‘quicksort’, ‘mergesort’, ‘heapsort’, ‘stable’}, optional: Sorting algorithm. The default is ‘quicksort’. Note that both ‘stable’ and ‘mergesort’ use timsort under the covers and, in general, the actual implementation will vary with data type. The ‘mergesort’ option is retained for backwards compatibility.

Changed in version 1.15.0.: The ‘stable’ option was added.
order str or list of str, optional: When a is an array with fields defined, this argument specifies which fields to compare first, second, etc. A single field can be specified as a string, and not all fields need be specified, but unspecified fields will still be used, in the order in which they come up in the dtype, to break ties.

Returns:

index_arrayndarray, int: Array of indices that sort a along the specified axis. If a is one-dimensional, a[index_array] yields a sorted a. More generally, np.take_along_axis(a, index_array, axis=axis) always yields the sorted a, irrespective of dimensionality.

我们知道，argsort可以将数组进行排序，返回是排序后的索引，但是默认是按照从小到大排序的，然后通常做法是将其逆序回来。

test = np.array([1,0,0,1,1,1,1,1,0,0,2,2,2,0,0,0,1,0,0,1,1,1])
print (np.argsort(test)[-1])

这里有几个问题：

1. 默认argsort用的是quicksort排序算法，这种方式排序是不稳定的。对稳定的排序算法来说，每次排序结果都一样，而且相同的两个元素，先出现的还是排在前面。

2. 取-1逆序，会打乱数组的顺序。

为什么呢？

可以从argsort的参数看一下，尤其是kind 这个参数这里，默认是quicksort，这个是不稳定的。而对stable, mergesort两个用的都是timsort方法，这种方法是世界上最快的算法，是结合了插入排序和归并排序稳定的排序算法，并做了许多优化，在实际应用中效率很高。而stable是后来版本才出现的，而mergsort是为了兼容旧版本，那么stable，mergesort两种方法得到的结果应该是一样的。

test = np.array([1,0,0,1,1,1,1,1,0,0,2,2,2,0,0,0,1,0,0,1,1,1])
print (np.argsort(test,kind='mergesort')[-1])  ##这样做无法做到先出现的排在前面


result = np.argsort(test)
result1 = np.argsort(test,  kind='stable')

result2 = np.argsort(test,  kind='mergesort')

print (result)
print (result1)
print (result2)

因此，如果你想得到的排序是稳定的，设置kind=stable或者mergesort就可以了，这样能得到稳定的从小达大排序的索引号。但是如果你想得到的是从大到小的排序，又要是稳定算法，是不可以直接逆序进行的，因为这样你跑坏了先出现排在前面的原则。

那么怎么办呢？

在排序时，对数组进行取负，然后直接用argsort进行排序，当然还是要kind=mergesort，这个时候是从大到小排序并且是稳定排序。

test = np.array([1,0,0,1,1,1,1,1,0,0,2,2,2,0,0,0,1,0,0,1,1,1])
print (np.argsort(test,kind='mergesort')[-1])  ##这样做无法做到先出现的排在前面




print ((-test).argsort(kind='mergesort'))
print (np.argsort(-test, kind='mergesort'))

如此一来就能得到稳定的从大到小排序，并且稳定的，先出现的排在前面。代码中后面两种方式一样，这个是毋庸置疑的。

平时我们只关注排序，大概不会注意到中间的差异，但是当你做工程时，如果不注意这些细节是很难做到方便工程上使用的。因此，别看一个小小的函数，影响还是很大的。工程上稳定排序是肯定的，但是argsort默认不是稳定的，而且如果你想从大到小，不是直接逆序就能满足的。

当然如果你想要一个直接进行从大到小排序好的数组，可以直接用numpy.sort即可，用法和argsort是一样的。也是通过配置这些参数达到稳定的排序。要说对数据进行计算，还是numpy厉害，什么功能都有，而且很好用。

一切都在细节中……