选择排序的代码实现,简单选择排序与直接选择排序

　　1.分类原则

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

　　最稳定的排序算法之一，无论输入什么数据，都是o(n2)的时间复杂度，所以在使用时，数据量越小越好。唯一的好处可能就是不占用额外的内存空间。理论上，选择排序也可能是普通人平时最想要的排序方式。

　　2.直接选择和分类N个记录文件的基本过程。经过n-1次直接选择排序，得到排序结果。(1)找出未排序序列中最小(最大)的元素，存储在排序序列的开头。

　　)2)继续从剩余的未排序元素中寻找最小(最大)的元素，并将其放在排序序列的末尾。

　　)3)等等，直到所有元素都被排序。

　　3.python代码定义def select _ sort(s):# foriinrange(len)s)-1)Loop len(s)-only once)I #变量k的原因是什么？需要确定的最小元素是什么？检查是否需要交换s[k]，s[i]=s[i]，s[k]ret。

　　4.算法分析最好的情况：t(n )=o) n2)最坏的情况：t) n )=o) n2)一般情况：t) n )=o) n2))))

　　空间复杂度在o(1)处不稳定。

解释一下不稳定性为何：

　　排序是在每个位置选择最小的当前元素。例如，在第一个位置选择最小的元素，在其余元素中第二个位置选择第二小的元素，依此类推到第n-1个元素。第n个元素可以不选中。因为只剩下一个最大的元素了。那么，在一个选择中，如果当前元素小于一个元素，并且小元素出现在等于当前元素的元素之后，交换后的稳定性就会被破坏。通过对比发现，比如按照5.8-5.2-9的顺序，第一遍选择第一个元素5会切换2，因为两个5的相对顺序会打乱原来的顺序，所以选择顺序不是一个稳定的排序算法。

　　可见直接选择的排序效率并不高。如果你想提高效率，你应该使用堆叠排序！堆叠排序是一种有效的选择性排序算法，将在下一节介绍。