愛炒股票短線的人，總是喜歡不斷的買進賣出，想通過價差來實現盈利。但通常這種頻繁操作的人，即使失誤不多，也會因為操作的手續(xù)費和印花稅過高而獲利很少。還有一種做股票的人，他們很少出手，只是在不斷的觀察和判斷，等到時機一到，果斷買進或賣出。他們因為冷靜和沉著，以及交易的次數少，而最終收益頗豐。
冒泡排序的思想就是不斷地在交換，通過交換完成最終的排序，這和做股票短線頻繁操作的人是類似的。我們可不可以像只有在時機非常明確到來時才出手的股票高手一樣，也就是在排序時找到合適的關鍵字再做交換，并且只移動一次就完成相應關鍵字的排序定位工作呢？這就是選擇排序法的初步思想。
選擇排序的基本思想是每一趟在n-i＋1(i=1,2,...,n-1)個記錄中選取關鍵字最小的記錄作為有序序列的第i個記錄。我們這里先介紹的是簡單選擇排序法。
簡單選擇排序算法
簡單選擇排序法（Simple Selection Sort）就是通過n-i次關鍵字間的比較，從n-i＋1個記錄中選出關鍵字最小的記錄，并和第i（1≤i≤n）個記錄交換之。
我們來看代碼。
/* 對順序表L作簡單選擇排序 */
void SelectSort(SqList *L)
{
int i, j, min;
for (i = 1; i < L->length; i++)
{
/* 將當前下標定義為最小值下標 */
min = i;
/* 循環(huán)之后的數據 */
for (j = i + 1; j <= L->length; j++)
{
/* 如果有小于當前最小值的關鍵字 */
if (L->r[min] > L->r[j])
/* 將此關鍵字的下標賦值給min */
min = j;
}
/* 若min不等于i，說明找到最小值，交換 */
if (i != min)
/* 交換L->r[i]與L->r[min]的值 */
swap(L, i, min);
}
}
代碼應該說不難理解，針對待排序的關鍵字序列是{9,1,5,8,3,7,4,6,2}，對i從1循環(huán)到8。當i=1時，L.r[i]=9，min開始是1，然后與j=2到9比較L.r[min]與L.r[j]的大小，因為j=2時最小，所以min=2。最終交換了L.r[2]與L.r[1]的值。如下圖所示，注意，這里比較了8次，卻只交換數據操作一次。
當i=2時，L.r[i]=9，min開始是2，經過比較后，min=9，交換L.r[min]與L.r[i]的值。如下圖所示，這樣就找到了第二位置的關鍵字。
當i=3時，L.r[i]=5，min開始是3，經過比較后，min=5，交換L.r[min]與L.r[i]的值。如下圖所示。
之后的數據比較和交換完全雷同，最多經過8次交換，就可完成排序工作。
簡單選擇排序復雜度分析
從簡單選擇排序的過程來看，它最大的特點就是交換移動數據次數相當少，這樣也就節(jié)約了相應的時間。分析它的時間復雜度發(fā)現，無論最好最差的情況，其比較次數都是一樣的多，第i趟排序需要進行n-i次關鍵字的比較，此時需要比較sigma(i=1, n-1, n-i)=(n-1)+(n-2)+...+1=n(n-1)/2次。而對于交換次數而言，當最好的時候，交換為0次，最差的時候，也就初始降序時，交換次數為n-1次，基于最終的排序時間是比較與交換的次數總和，因此，總的時間復雜度依然為O(n2)。
應該說，盡管與冒泡排序同為O(n2)，但簡單選擇排序的性能上還是要略優(yōu)于冒泡排序。
