三、选择排序
选择排序是从待排序的区间中选择出具有最小排序码的元素，并将该元素与该区间的第1个元素交换位置。这样通过 n-1次选择未排序部分的最小元素，将其放在正确位置从而达到对整个序列进行排序的效果。对于长度为n的序列，选择排序算法的主要步骤如下：
(1) 扫描序列n-1次；
(2) 第i(1≤i≤n-1)次扫描，找到待排序区间a[i]，a[i+1]，···，a[n]中的最小元素a[m]。
(3)交换a[i]与a[m]。这样a[1]，a[2]，···，a[i]储存的恰好依次是序列中的第1，2，···，i 项元素。
选择排序进行n-1次扫描，第 i 次扫描 n-i+1个元素，扫描结束进行一次交换，总共扫描n+(n-1)+···+2=
-1个元素，故时间复杂度为
。
选择排序本身只需要维护一个pos变量存储每次扫描的最小(或最大)元素的位置，故额外空间复杂度为O(1)。
与冒泡排序不同，选择排序并不是稳定的排序，因为其涉及不相邻位置的元素的交换。如序列(2，2，1)，在第一次扫描后1与第一个2交换，那么在最终序列中，原始序列中的第一个2被换到第二个2后面了，因此选择排序并不稳定。
选择排序代码实现如下： 