Python 排序+k近邻小记——感受排序之美

Author： Alpha
发布时间：September 10, 2022
267 views
No comments
2410 words
Categories： python 高中知识编程技术

## Python内置的排序算法

有list.sort()和sorted。

list.sort()只有列表才有，sorted接受序列不止列表，元组什么的都可以，但是最终返回列表

排序主要有俩参数，一个key  一个 reverse

在这里我们只讲讲key，reverse应该很熟悉了

key接受一个可调用对象（函数）你可以用key=len进行基于字符串长度的排序

Python自带的排序算法背后是timsort，有兴趣的童鞋可以去看看维基百科。

它是一种自适应算法，按照原始数据的顺序特点交替搞插入排序和归并排序。tim是该算法的开发者，他也是python之禅的编写者。

key参数的这玩意很妙，因为它只会被调用一次。这是其他语言基本上没有的玩意，这也是我觉得应该放到python教学里面的玩意，但是python只能被当做教学的工具。对此，不便多提，以免影响你的做题产生懊恼的情绪。。。。

对于查找算法也是一样，python里面的字典的查找速度，嘎嘎快，用空间换时间的那种。

---

我很讨厌自己去“执行”代码，故我在q群中发了这样一个排序算法

```python
import numpy as np
def bogosort(x):
    while np.any(x[:-1] > x[1:]):
        np.random.shuffle(x)
    return x
```

当序列里面后一个大于前面一个时，相当于排序好了

这样的排序算法完全就是碰运气，除了来做教学，绝对不会真正运用。

按照大O标记法，他的时间复杂度为N*N!，你完全无法精确定位它整个排序过程是啥样的，除非特殊情况吧。

小插曲儿：大O标记是个抽象的概念，对于不同的语言，同样的算法，时间是不一样的。它不会告诉你实际的运行时间，而是帮你了解增长的关系——随着规模的增大，时间相应的变化“情况”
</div>

在选修一涉及了k近邻我是没有想到的，用那嵌套循环排序算法更让我想不到，这让我深刻的意识到，这样的“基础算法”和我学的“python基础”完全是云泥之别。如果题目没要求，我打死也不会这样写。这是python之禅教我的。

关于k近邻划分，np其实非常擅长，如果你对“必修一”不熟悉亦或者是很熟悉可以尝试阅读以下代码

```python
#X是一个10行2列的np数组
dist_sq = np.sum((X[:, np.newaxis, :] - X[np.newaxis, :, :]) ** 2, axis=-1)
#np.newaxis放在哪里就在哪里拓展上新的维度
#我本人也挺讨厌又臭又长的代码，上面的一句主要功能就是计算点点之间的距离方，很神奇，对吧
#我们来尝试阅读一下分步的
differences = X[:, np.newaxis, :] - X[np.newaxis, :, :] 
#上面的一行计算出了每对点的差值，形状为10，10，2
sq_differences = differences ** 2
#之后是平方，越来越易懂了，对吧
dist_sq = sq_differences.sum(-1)
#之后我们做求和工作，形状最终变成10行10列，10个点把自己跟自己的距离也计算进去了
#在这里不需要再做开根号了，这样直接排序就ok
```

numpy自带的排序算法是快速排序，下面是来自知乎的一则评论

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-08a4e5c06ed1bfa8e222fca71c34b85f55" aria-expanded="true"><div class="accordion-toggle"><span style="">快速排序和python自带的排序timsort</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-08a4e5c06ed1bfa8e222fca71c34b85f55" class="collapse collapse-content"><p></p>

TimSort是高度优化的mergesort，它比旧的mergesort稳定且速度更快。

与quicksort相比，它有两个优点：

对于几乎排序的数据序列（包括反向排序的数据），它的速度令人难以置信。
最坏的情况仍然是O（N * LOG（N））。
老实说，我认为＃1并不是优势，但确实给我留下了深刻的印象。

这是QuickSort的优势

QuickSort非常非常简单，即使是高度优化的实现，我们也可以在20行内写下其pseduo代码；
在大多数情况下，QuickSort最快。
内存消耗为LOG（N）。
当前，Java 7 SDK实现了timsort和一个新的quicksort变体：Dual Pivot QuickSort。

如果您需要稳定的排序，请尝试使用timsort，否则请从quicksort开始。

```python
nearest = np.argsort(dist_sq, axis=1)
print(nearest)
```

[[0 3 9 7 1 4 2 5 6 8]
[1 4 7 9 3 6 8 5 0 2]
[2 1 4 6 3 0 8 9 7 5]
[3 9 7 0 1 4 5 8 6 2]
[4 1 8 5 6 7 9 3 0 2]
[5 8 6 4 1 7 9 3 2 0]
[6 8 5 4 1 7 9 3 2 0]
[7 9 3 1 4 0 5 8 6 2]
[8 5 6 4 1 7 9 3 2 0]
[9 7 3 0 1 4 5 8 6 2]]

第一列是每个点自身的位置，毕竟自己跟自己最近，之后的就是最近的点的索引位置了

argsort返回的是排序好的索引值。很方便，对吧。

</div>

Last modification：September 10, 2022

如果觉得我的内容对你有用，请随意赞赏

Python 排序+k近邻小记——感受排序之美

Alpha • 2022 年 09 月 10 日

## Python内置的排序算法

有list.sort()和sorted。

list.sort()只有列表才有，sorted接受序列不止列表，元组什么的都可以，但是最终返回列表

排序主要有俩参数，一个key  一个 reverse

在这里我们只讲讲key，reverse应该很熟悉了

key接受一个可调用对象（函数）你可以用key=len进行基于字符串长度的排序

Python自带的排序算法背后是timsort，有兴趣的童鞋可以去看看维基百科。

它是一种自适应算法，按照原始数据的顺序特点交替搞插入排序和归并排序。tim是该算法的开发者，他也是python之禅的编写者。

对于查找算法也是一样，python里面的字典的查找速度，嘎嘎快，用空间换时间的那种。

---

我很讨厌自己去“执行”代码，故我在q群中发了这样一个排序算法

```python
import numpy as np
def bogosort(x):
    while np.any(x[:-1] > x[1:]):
        np.random.shuffle(x)
    return x
```

当序列里面后一个大于前面一个时，相当于排序好了

这样的排序算法完全就是碰运气，除了来做教学，绝对不会真正运用。

按照大O标记法，他的时间复杂度为N*N!，你完全无法精确定位它整个排序过程是啥样的，除非特殊情况吧。

关于k近邻划分，np其实非常擅长，如果你对“必修一”不熟悉亦或者是很熟悉可以尝试阅读以下代码

numpy自带的排序算法是快速排序，下面是来自知乎的一则评论

TimSort是高度优化的mergesort，它比旧的mergesort稳定且速度更快。

与quicksort相比，它有两个优点：

这是QuickSort的优势

如果您需要稳定的排序，请尝试使用timsort，否则请从quicksort开始。

```python
nearest = np.argsort(dist_sq, axis=1)
print(nearest)
```

第一列是每个点自身的位置，毕竟自己跟自己最近，之后的就是最近的点的索引位置了

argsort返回的是排序好的索引值。很方便，对吧。

</div>

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Python 排序+k近邻小记——感受排序之美

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款