選擇排序也是一種簡(jiǎn)單直觀的排序算法。它的工作原理很容易理解：首先在未排序序列中找到最蟹莸睢（大）元素，存放到排序序列的起始位置嗽交；然后卿嘲，再從剩余未排序元素中繼續(xù)尋找最小（大）元素夫壁，放到已排序序列的末尾拾枣。以此類推，直到所有元素均排序完畢。
// 分類 -------------- 內(nèi)部比較排序
// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
// 最差時(shí)間復(fù)雜度 ---- O(n^2)
// 最優(yōu)時(shí)間復(fù)雜度 ---- O(n^2)
// 平均時(shí)間復(fù)雜度 ---- O(n^2)
// 所需輔助空間 ------ O(1)
// 穩(wěn)定性 ------------ 不穩(wěn)定
選擇排序是不穩(wěn)定的排序算法梅肤，不穩(wěn)定發(fā)生在最小元素與A[i]交換的時(shí)刻司蔬。比如序列：{5, 8,5,2, 9 }，一次選擇的最小元素是2姨蝴，然后把2和第一個(gè)5進(jìn)行交換俊啼，從而改變了兩個(gè)元素5的相對(duì)次序。
#include
usingnamespacestd;
voidexchange(intA[],inti,intj)//交換A[i]和A[j]
{
inttemp = A[i];
A[i] = A[j];
A[j] = temp;
}
intmain()
{
intA[] = {8,5,2,6,9,3,1,4,0,7};//從小到大選擇排序
intn =sizeof(A) /sizeof(int);
inti, j, min;
for(i =0; i <= n -2; i++)//已排序序列的末尾
{
min = i;
for(j = i +1; j <= n -1; j++)//未排序序列
{
if(A[j] < A[min])//依次找出未排序序列中的最小值,存放到已排序序列的末尾
{
min = j;
}
}
if(min != i)
{
exchange(A, min, i);//該操作很有可能把穩(wěn)定性打亂,所以選擇排序是不穩(wěn)定的排序算法
}
}
printf("選擇排序結(jié)果：");
for(i =0; i < n; i++)
{
printf("%d ",A[i]);
}
printf("\n");
return0;
}
