逻辑的必然——再谈选择排序
前文列举了一些选择排序的变种。简单来说就是
- 基本思想：选出最小的，交换到最左边
- 更进一步，每次选出最小的同时，也选出最大的
- 对于重复的值，可以节省比较操作
- 可以利用特定的数据结构，更容易地找出最小值
具体内容参见 排序 - 选择排序 / Selection Sort
讨论排序，似乎是关于程序算法的问题，是只对程序员有用的话题。
而实际上，讨论程序算法的演化，更多的是对其中的方法论的探讨。
第一个吃螃蟹的人
第一个吃螃蟹的人是不是最勇敢的人？
可以说是，因为那显然需要勇气。但也可以说不是，因为实际上总归会有第一个人站出来去吃螃蟹。
第一个想出某种选择排序算法变种的人，是不是很聪明的人？
可以说是，非够聪明不足以有所发明。但也可以说不是，因为那是逻辑推理可以到达之处。
一心二用
同时选出最小的和最大的值的选择排序算法被称为 cocktail sort 或者 double selection sort。
Cocktail 是鸡尾酒的意思。鸡尾酒是一种混合物。Cocktail Sort 的关键思路在于把两种不同的操作混合到一起。
如果站在选择排序的基本想法面前，试着往前再走一步，可以说这是一个比较容易想到的思路。
共享复用
一心二用的实质，是两个不同的操作共享了一部分操作，进而节省了资源。
而对共享复用这个理念的运用，在人类社会中可以说比比皆是。
比如近年来谈论不断的「共享经济」。这事提高资源利用效率的好办法。
专心致志
在知道了同时选出最小的和最大的这个思路的基础上，我们可以进一步追问：如果可以同时选出第二小的那个，又会怎样呢。
同时选出最小的和第二小的，实质上就是一个排序问题。这和我么最初要解决的排序问题，具有相同的形式。
为了找出这个第二小的，如果需要引入其他形式的逻辑，还不如复用当前的逻辑。这只需要暂时忘掉第二，专注在第一上就好。
这个时候，反而与其一心二用，不如专心致志。
学以致用
把不熟悉的东西变熟悉的过程，称之为「学」。「学」的目的是为了「用」。
对于选择排序，通过一次选择，可以学习到哪个数值是当前的最小值。再下一回合中，如果不利用已经学到的这点东西，就有点太可惜了。
基于这个思路，bingo sort 思路的关键点，就是利用上一回合的结论，可以对相同的元素直接做出结论。
物以类聚
逻辑思维里最重要的能力，也许是对事物和概念进行分类的能力。
一旦人们把一个概念或事物归类为某个已知的类别，就可以按照那个类别对应的信息或说明来理解和操作这个概念或事物。
随着逐步地把未知事物划入某个分类，也逐渐减少了未知事物的数量。
排序算法，也可以看作是不断分类的过程。
对于最基本选择排序来说，每个回合的操作，相当于把未知的元素划分为最小的和未知的两大类。
Cocktail Sort 增加了一个分类，把未知元素划分为最小的、最大的和未知的三大类。
Bingo Sort 则把问题划分为已知最小的、本回合即将知道的最小的和未知的三大类。
融合变异
将两种不同的事物融合到一起，可以有机会变成新的事物。
融合变异的绝佳例子是生命体 DNA 的融合变异。
对选择排序来说，我们完全可以把 Bingo Sort 和 Cocktail Sort 也融合在一起。