文章目录
*
– 简介
– quicksort
– 堆排序
– 归并排序
简介
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]])
numpy中针对数组排序，实现了多种不同的算法，在 sort中，通过 kind参数可以选择排序方案
kind速度最坏性能稳定性’quicksort’`1
O ( n 2 ) O(n^2)O (n 2 )
否’heapsort’3✅否'mergesort'2✅是'timsort''2✅是
上表中✅表示O ( n log n ) O(n\log n)O (n lo g 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]))
由于不断地二分，使得迭代次数从经典插入的n n n次下降为log 2 N \log_2N lo g 2 N次，突破了n 2 n^2 n 2的限制，从而获得了快排的美名。
但从上面的代码也可以看到，首先，当元素个数较少时，快排是体现不出性能的；其次，当元素个数较多时，会产生非常深的递归，造成较大的内存开销。
introSort针对快排的这两个弱点，做了如下优化
- 当递归到某一深度， arr的元素个数较少时，采取插入排序
- 当递归的层次过深，则更改排序策略，使用堆排序
堆排序
堆排序是建立在最大堆或者最小堆这种数据结构之上的，所谓最小堆，本质是一个完全二叉树，要求父节点不大于其所有子节点。
最小堆的完全二叉树结构，决定了树高在log 2 ( n + 1 ) \log_2(n+1)lo g 2 (n +1 )的水平，从而使得自上而下遍历最大堆的时间复杂度降低到log 2 ( n + 1 ) \log_2(n+1)lo g 2 (n +1 )。
根据上图可知，若父节点的序号为n n n，则左子节点序号为2 n + 1 2n+1 2 n +1,右子节点序号为2 n + 2 2n+2 2 n +2。
可以将上图理解为一个排好序的最小堆，如果1位变成15，那么这个节点将违反最小堆的原则，经过比对，应该调换15和3的位置。调换之后，15仍然比7和8大，则继续调换15和7的位置，则这个最小堆变为
; 归并排序
归并排序是算法导论中介绍的第一种使用分治策略的排序算法，基本思路是将数组拆分成子数组，然后令子数组有序，再令数组之间有序，则可以使整个数组有序。其算法步骤如下：
设数组有n n n个元素，{ a 0 , a 1 , … , a n } {a_0,a_1,\ldots,a_n}{a 0 ,a 1 ,…,a n }
- 如果数组元素大于2，则将数组分成左数组和右数组，否则将数组转成有序数组
- 对左数组和右数组执行1操作。
- 合并左数组和右数组。
TimSort和 introSort相似，都是缝合得比较厉害的排序算法，其中 introSort是C++标准库中的快排方案，而 TimSort则是Tim Peters于2002年首先应用在Python的。
timsort的基本思路是最大限度地利用数组中已经存在的有序子数组，Tim将这些已经有序的子数组称为 run，排序过程中，像归并排序一样，不断地将迭代元素放入每个 run中，同时对不同的 run进行合并，直到只剩下一个 run。
Original: https://blog.csdn.net/m0_37816922/article/details/127841747
Author: 微小冷
Title: 【Python】Numpy排序函数详解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/761172/
转载文章受原作者版权保护。转载请注明原作者出处！