今天來給大家介紹一下排序算法之選擇排序

選擇排序：（Selection sort）是一種簡單直觀的排序算法，也是一種不穩(wěn)定的排序方法。

選擇排序的原理：

一組無序待排數(shù)組，做升序排序，我們先假定第一個位置上的數(shù)據(jù)就是最小的，我們用一個參數(shù)記錄這個最小的數(shù)，然后依次把后面的每個位置的數(shù)據(jù)和這個最小的比較，如果比這個數(shù)小就替換兩個位置數(shù)據(jù)，等到第一輪比較完成就能確定最小的數(shù)據(jù)排在第一位了，然后第二輪從第二個位置開始，相同的方式比較，每次都能找到本輪最小的值，直至全部待排元素個數(shù)為0的時候，數(shù)組就排好順序了。

選擇排序流程圖

我們來進(jìn)行詳細(xì)解析看看

首先我們給個無序數(shù)組[4,6,15,9,12,3,32]進(jìn)行升序排序，因?yàn)樾枰_定每個數(shù)組的長度，所以需要比較數(shù)組長度-1輪，當(dāng)前面的元素都排好了之后，那么數(shù)組最后一個元素自然就確定了位置。

我們定義兩個值，minIndex，minNum用來分別表示每一輪的找到的最小值的下標(biāo)和值，后面未排序的值都和minNum比較，從而找出每一輪的最小值。

第一輪我們以下標(biāo)為1的第一位作為標(biāo)志位（也就是把第一個值當(dāng)做最小值），那么此時minIndex=0，minNum=4，經(jīng)過和 minNum 比較發(fā)現(xiàn)后面只有3比4小，那么3和4交換位置，minIndex=5，minNum=3，把4換到下標(biāo)為5的位置，如下圖所示：

第一輪我們得到的結(jié)果是[3,6,15,9,12,4,32]，本輪最小數(shù)是：3，所以3放到本輪標(biāo)志位，也就是第一位

第二輪：拿到第一輪排序的值作為初始值[3,6,15,9,12,4,32]，同第一輪一樣，此時6作為標(biāo)志位minNum=6，minNum和其他比較，只有4比6小，需要交換位置，如下圖所示第二輪排序結(jié)果[3,4,15,9,12,6,32]，本輪最小數(shù)是：4第三輪：初始值[3,4,15,9,12,6,32],這次標(biāo)志位15，minNum=15，minIndex=2，minNum先比和9比較，發(fā)現(xiàn)9比15小，minNum=9，minIndex=3，然后minNum和12比較，不需要替換minNum，再和6比較，minNum=6，minIndex=5,后面再比較已經(jīng)沒有比6小了，那么本輪就是初始標(biāo)志位15和下標(biāo)為5，值為6的數(shù)據(jù)換位置。第三輪排序結(jié)果[3,4,6,9,12,15,32]，本輪最小數(shù)是：6第四、五、六輪：初始值[3,4,6,9,12,15,32]，經(jīng)過前面的比較我們可以看到數(shù)組已經(jīng)排序完成，但是程序并不知道，會繼續(xù)比較下去，把下標(biāo)為4、5、6位置都作為標(biāo)志位比較一次，發(fā)現(xiàn)都不需要變動位置，那么最終執(zhí)行完成之后就能排序完成第四、五、六輪排序結(jié)果[3,4,6,9,12,15,32]

到這，我們已經(jīng)清楚了每個步驟做了什么，那么接下來上代碼驗(yàn)證一下：

Java代碼實(shí)現(xiàn) public class selectionSort { public static void main(String[] args){ int[] arr = new int[]{4,6,15,9,12,3,32}; for(int i=0;i<arr.length-1;i++){//每次循環(huán)都會找出最小的數(shù) //記錄最小數(shù)的下標(biāo) int minIndex = i; //記錄最小數(shù) int minNum = arr[i]; //每次循環(huán)都會找出最小的數(shù) for(int j=i+1;j<arr.length;j++){ if(arr[j]<minNum){//如果當(dāng)前數(shù)比最小數(shù)小，則更新最小數(shù) minNum = arr[j];//更新最小數(shù) minIndex = j;//更新最小數(shù)的下標(biāo) } } //將最開始假定的小的數(shù)移動到真實(shí)最小的位置 arr[minIndex]=arr[i]; arr[i]=minNum;//將標(biāo)志位放到最小數(shù)原來所在的位置 //打印結(jié)果，方便查看 System.out.print("第"+(i+1)+"輪["); for(int a=0;a<arr.length;a++){ System.out.print(arr[a]+"\t"); } System.out.println ("]，本輪最小數(shù)是："+minNum); } System.out.print("最終結(jié)果["); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+"\t"); } System.out.println("]"); } }

輸出結(jié)果

第1輪[3 6 15 9 12 4 32 ]，本輪最小數(shù)是：3 第2輪[3 4 15 9 12 6 32 ]，本輪最小數(shù)是：4 第3輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：6 第4輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：9 第5輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：12 第6輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：15 最終結(jié)果[3 4 6 9 12 15 32 ]時間復(fù)雜度

我們通過上面的細(xì)節(jié)拆分發(fā)現(xiàn)，無論是否是已經(jīng)排好的還是沒排好的情況，我們都需要每個數(shù)字都比較到，那么就出現(xiàn)N個元素的數(shù)組，第一輪是n次比較，第二輪是從第二個位置開始，那么就是n-1，第三輪就是n-2次... 最后是1，那么就出現(xiàn)了n+(n-1)+(n-2)+(n-3)...1,這是一個等差數(shù)列，求和為一個二次型多項(xiàng)式，因?yàn)榈炔顢?shù)列求和會出現(xiàn)二次型；我們?nèi)∽罡唠A就是n^2,所以時間復(fù)雜度就是O(n^2),而且最好和最壞的情況時間復(fù)雜度都是O(n^2)