基本概念

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

動畫演示：

紅色的是當(dāng)次循環(huán)最小值，黃色的是已執(zhí)行完的數(shù)據(jù)，綠色的是當(dāng)前搜索的元素

從上圖我們可以很明顯的看出來選擇排序的執(zhí)行方式，對此我們進(jìn)行總結(jié)了幾點：

1. 讀入數(shù)據(jù)存放在a數(shù)組中

2. 在a[1]~a[n]中選擇值最小的元素與第一位的元素進(jìn)行調(diào)換，則把最小的元素放在a[1]中

3. 在a[2]~a[n]中選擇值最小的元素與第二位元素進(jìn)行調(diào)換，則把最小的元素放在a[2]中

4. 直到第n- 1個元素與第n個元素比較排序為止（重復(fù)執(zhí)行該內(nèi)容）

選擇排序的缺點也很明顯且致命，即

1，時間復(fù)雜度高。

2，不是穩(wěn)定的排序算法，因為每次找到最小的值后會進(jìn)行交換位置的操作。

3，最壞和最好情況都是O(n2)的復(fù)雜度。若有n個元素則都得執(zhí)行n次。

這個排序方法是表現(xiàn)最穩(wěn)定的排序算法之一，因為無論什么數(shù)據(jù)進(jìn)去都是O(n2)的時間復(fù)雜度，所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。這個排序唯一的好處可能就是不占用額外的內(nèi)存空間吧。

程序?qū)崿F(xiàn)

?程序?qū)崿F(xiàn)方法，用兩層循環(huán)完成算法，外層循環(huán)i 控制當(dāng)前序列最小值存放的數(shù)組位置，內(nèi)層循環(huán)j 值控制從i +1到序列中最小的元素所在位置k。

具體操作如下：

好了，選擇排序就講到這里了

在此，部分借鑒了知乎阿杰同學(xué)（https://zhuanlan.zhihu.com/p/449501682）

模板以及部分代碼借鑒了《信息學(xué)奧賽一本（C++）》