选择排序的特点

最好、最坏和平均时间复杂度都是 O(n^2) ; 空间复杂度是 O(1) , 它是一个原地排序算法

选择排序不是一个稳定的排序算法，因为每次的交换会改变相等元素之间的相对位置

运行时间与输入无关，因为每次扫描并不能为下一次扫描提供什么有用的信息

数据的移动是最少的，只有 n 次，交换次数等于数组的长度，这种线性性质是很多排序方法做不到的

一组无序数据原理

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似，若a[1]小于a[2]则交换两者的值，否则不变，后面以此类推。 总的来讲，每一轮排序后最大(或最小)的数将移动到数据序列的最后，理论上总共要进行n(n-1)/2次交换。[2]