《算法基础》——3.6 链表的选择排序
本节书摘来自华章计算机《算法基础》一书中的第3章，第3.6节，作者：（美）罗德·斯蒂芬斯（Rod Stephens）著，更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.6 链表的选择排序
该选择排序算法背后的基本思想是：搜寻输入链表中所包含的最大项，然后将其添加到一个不断增长的有序链表的前面。
下面的伪代码显示了选择排序算法的单向链表实现方法（默认其中的项是整数类型）：
如果将寻找输入链表中最大单元格的代码抽取出来，作为一个新的算法，然后在原有算法中调用该新算法，则可以使得上面的算法变得更加简化。
若输入链表包含K个项，则寻找链表中的最大项需要花费K步。在算法进行的过程中，输入链表将会缩小规模。因此，如果它最初拥有N个项，步骤的总数是N＋(N－1)＋(N－2)＋…＋2＋1＝N×(N＋1)÷2＝O(N2)，这和插入排序的运行时间相同。