选择排序
选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
常用的选择排序方法有简单选择排序和堆排序。
简单选择排序
简单选择排序(simple selection sort)也是直接选择排序。此方法在一些高级语言课程中做过介绍，是一种较为容易理解的方法。
1.算法思想
对于一组关键字{A1,A2,…,An}， 首先(第1趟）从A1,A2,…,An中选择最小值，假如它是 Az，则将Az与 A1对换；然后（第2趟）从A2，A3，… ，An中选择最小值 Az，再将Az与A2对换。如此进行选择和调换n-2趟。
第(n-1)趟，从An-1、An中选择最小值 Az将Az与An-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。
【例】是一个有5个关键字{3,4,1,5,2}的简单选择排序过程:
|
|3
|
4
|
1
|
5
|
2
|
|
1
|
|4
|
3
|
5
|
2
|
|
1
|
2
|
|3
|
5
|
4
|
|
1
|
2
|
3
|
|5
|
4
|
|
1
|
2
|
3
|
4
|
|5
|
ALGORITHM SelectionSort(A[0...n-1])
//Sorts a given array by selection sort
//Input: An Array A[0...n-1] of orderable elements
//Output: Array A[0...n-1] sorted in ascending order
for i←0 to n-2 do
min←i
for j←i+1 to n-1 do
if A[j]<A[min] min←j
swap A[i] and A[min]
算法时间复杂度θ(n^2)，空间复杂度θ(1)。
该排序算法稳定。