选择排序（Selection Sort）
（1）算法思想
给定待排序序列A[1..n]，首先找出A中最小的元素，将其与A[1]交换；然后找出A中次最小元素，将其与A[2]交换......以此类推，进行n-1次循环，即可找到A中最小的n-1个元素并将其放在对应的位置，最后一个元素自然是最大的元素。由于查找到相应大小的一个元素后就将其放到对应顺序的位置上，因此，查找元素可以按照以下方式进行搜索：查找A中最小元素在A[1..n]中查找最小元素，查找第2小的元素则在A[2..n]中查找最小元素，查找第3小的最小元素在A[3..n]中进行搜索……查找第n-1小的元素在A[n-1,n]查找最小元素。具体过程如下所示：
（2）伪代码
SELECTION-SORT(A)
1 n ← length[A]
2 for i ← 1 to n-1
3 dokey ← A[i] //key记录要查找的最小值
4 index ← i //index记录下标
5 for j ← i+1 to n
6 do if A[j] < key
7 then key ← A[j]
8 index ← j
9 if k ≠ i
10 then A[i] ↔ A[index]
（3）代码实现
void SelectionSort(int A[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
int key=A[i];
int index=i;
for(j=i+1;j<n;j++)
{
if(A[j]<key)
{
key=A[j];
index=j;
}
}
if(index!=i)
{
A[index]=A[i];
A[i]=key;
}
}
}
（4）算法分析
a.选择排序的时间复杂度：Θ(n^2)。
b.选择排序是原地排序。
c.选择排序不是稳定排序。