Loading... ## 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!,你完全无法精确定位它整个排序过程是啥样的,除非特殊情况吧。 <div class="tip inlineBlock share simple small"> 小插曲儿:大O标记是个抽象的概念,对于不同的语言,同样的算法,时间是不一样的。它不会告诉你实际的运行时间,而是帮你了解增长的关系——随着规模的增大,时间相应的变化“情况” </div> 在选修一涉及了k近邻我是没有想到的,用那嵌套循环排序算法更让我想不到,这让我深刻的意识到,这样的“基础算法”和我学的“python基础”完全是云泥之别。如果题目没要求,我打死也不会这样写。这是python之禅教我的。 <div class="tip inlineBlock info simple small"> 关于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开始。 <p></p></div></div></div> ```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 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 1 如果觉得我的内容对你有用,请随意赞赏