Python 集合的遍历,推导及 filter/map/reduce 操作 中讲了对集合的 filter, map 和 reduce 操作，那还有 sort 排序呢？像 Java 一样，Python 也提供了 sort() 和 sorted() 方法。
sort() 是 list 的实例方法， sorted() 是一个内置函数。Python 中也是只有 list 才有顺序。
查看 Python 3 中的 list.sort() 方法(help(list.sort))
Help on method_descriptor:
sort(self, /, *, key=None, reverse=False)
Stable sort *IN PLACE*.
Python 的 list.sort() 方法和 Java List.sort() 方法一样的，都是 IN PLACE 排序，没有返回值。实际看下各种排序场景 阅读全文 >>
对于基本的排序算法，前面介绍了冒泡，选择，插入和希尔(增强版本的插入), 还有快速排序，现在还剩下最后一种基本的排序算法，那就是归并排序。归并排序像快速排序一样采用递归算法对列表进行分而治之，每次平均一分为二，分到只有一个元素为止。如果列表为空或只有一个元素时，那么从定义上来说它就是有序的; 当然归并排序的拆分最终不会有空列表的情况。拆分成一个个元素后再往回归并，归并是指将两个较小的有序列表归并为一个有序列表的过程。比如说两个单元素列表归并为两个元素的有序列表，两个双元素的列表归并为四个元素的有充列表，不断往上进行，最后形成一个有序的完整列表。
从维基百科的词条 Merge sort 找到下图，很深刻的描绘了归并排序的完整过程，红色箭头拆分，绿色箭头归并 阅读全文 >>
前面讲过的几种排序多是以排序逻辑来命名的，例如冒泡，选择和插入排序，以及其他如归并排序，当然还有觉得自己足够牛 X 快速排序命名。而本文要学习的排序算法叫做希尔排序是以其设计者 Donlad Shell 命令的排序算法，该算法在 1959 年公布，能以作者来命名的算法应该是很不错的，令设计者引以为傲的。最初写出冒泡和选择排序的就没以作者来命名，可能不好意说，更可能是公共思维。
那么什么是希尔排序呢？它实际上是插入排序算法的增强版本，又称递减增量排序算法。它对待排序列表进行间隔式分段插入 处理，从而总体上减少了元素的移动次数而达到性能的大大提升。那么理解希尔排序之前一定要先了解插入排序。那么为什么说希尔排序既是递减又是增量呢？ 阅读全文 >>
前面说过最原始的复杂度为 O(n2) 的冒泡和选择排序，也跳跃到了复杂度为 O(n log n) 的快速排序，现在又再看一个复杂度同样为 O(n2) 的插入排序。从排序名称结合代码我们理解了为什么叫做冒泡或是选择，快速排序自认高名，那么何以这又谓之插入排序呢？是怎么插入，从左边往右边插，还是从右边往左边插，这得搞清它的排序原理：
它在列表较低的一端维护一个有序的子列表(从最左端一个元素开始)，并逐个将每个新元素(高端的)"插入"这个子列表。插入的时候遍历低端列表，找准位置插入便是，插入点后的元素需后移，当所有高端的元素插入完成了，整个列表就变得有序了。
整个排序操作示意图如下： 阅读全文 >>
冒泡和选择排序的简单粗暴也许在某些人眼里都不能称作算法，现在要进入一种更优雅的排序算法，快速排序。它使用分而治之(Divide and Conquer, D&G) 的策略，要应用到递归调用。快速排序敢说自己快速，也确实比选择排序快很多很多。冒泡和选择排序，尤其是选择排序是非常自然的排序算法，而快速排序就不是一般人会随意想出来的。
快速排序的演绎需要用递归来思考循环的问题，然而我之前总是在及力用循环来避免递归调用，有趣的是诸如 Haskell 等函数式编译语言根本没有循环，只能用递归来编写循环的效果。来看一个简单的例子，比如要从 1 加到 100，我们很自然会用循环从 1 累加到 100，如果换成递归，看下面的代码
|
1 2 3 4 5 6 7 8 |
def summary(arr): if len(arr) == 0: return 0 else: return arr[0] + summary(arr[1:]) print(summary(list(range(1, 101)))) # 5050 |
递归有助于我们把大问题分解为小问题，上面代码的思维是数组的和总是很一个元素加上剩下元素列表的和，直到最后元素列表为空(和为 0)。 阅读全文 >>
这是我自最早接触 Javascript 的排序之日起一直萦绕在脑海中的问题。比如一个简单的 Javascript 数组排序
[3, 2, 4, 6, 5].sort(function(e1, e2) {
return e1 - e2;
});
当然我那时候还不会用 JSON 和无名函数来写上面的代码。 反正经常是搞不清楚想要升序或降序时，是应该 return e1 - e2 还是 return e2 - e1 ?，没把握就试一下，总是二选一。
现在许多语言对集合排序都是使用排序函数的方式，总不想每次都琢磨不定，每次都去试。需要 TDD 时测试用例必须覆盖排序用例，但还是希望以后书写排序函数时心里有个底。当然，比如在 Java 中对集合进行排序我们可以深入到源代码来理解排序函数是如何影响元素顺序的。
简单通俗点，是否有一种浅显的方式来理解排序函数呢？待我把答案慢慢叙来，就我个人理解就两个原则： 阅读全文 >>