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

選擇排序的原理

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

選擇排序流程圖

我們來進行詳細解析看看

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

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

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

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

第二輪：拿到第一輪排序的值作為初始值[3,6,15,9,12,4,32]，同第一輪一樣，此時6作為標志位minNum=6，minNum和其他比較，只有4比6小，需要交換位置，如下圖所示

第二輪排序結果[3,4,15,9,12,6,32]，本輪最小數(shù)是：4

第三輪：初始值[3,4,15,9,12,6,32],這次標志位15，minNum=15，minIndex=2，minNum先比和9比較，發(fā)現(xiàn)9比15小，minNum=9，minIndex=3，然后minNum和12比較，不需要替換minNum，再和6比較，minNum=6，minIndex=5,后面再比較已經沒有比6小了，那么本輪就是初始標志位15和下標為5，值為6的數(shù)據(jù)換位置。

第三輪排序結果[3,4,6,9,12,15,32]，本輪最小數(shù)是：6

第四、五、六輪：初始值[3,4,6,9,12,15,32]，經過前面的比較我們可以看到數(shù)組已經排序完成，但是程序并不知道，會繼續(xù)比較下去，把下標為4、5、6位置都作為標志位比較一次，發(fā)現(xiàn)都不需要變動位置，那么最終執(zhí)行完成之后就能排序完成

第四、五、六輪排序結果[3,4,6,9,12,15,32]

到這，我們已經清楚了每個步驟做了什么，那么接下來上代碼驗證一下：

Java代碼實現(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ù)的下標
?????????????int?minIndex?=?i;
?????????????//記錄最小數(shù)
?????????????int?minNum?=?arr[i];
?????????????//每次循環(huán)都會找出最小的數(shù)
?????????????for(int?j=i+1;j<arr.length;j++){
?????????????????if(arr[j]<minNum){//如果當前數(shù)比最小數(shù)小，則更新最小數(shù)
?????????????????????minNum?=?arr[j];//更新最小數(shù)
?????????????????????minIndex?=?j;//更新最小數(shù)的下標
?????????????????}
?????????????}
?????????????//將最開始假定的小的數(shù)移動到真實最小的位置
?????????????arr[minIndex]=arr[i];
?????????????arr[i]=minNum;//將標志位放到最小數(shù)原來所在的位置
?????????????
?????????????//打印結果，方便查看
?????????????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("最終結果[");
?????????for(int?i=0;i<arr.length;i++){
?????????????System.out.print(arr[i]+"\t");
?????????}
?????????System.out.println("]");
?????}
?}

輸出結果

  第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
  最終結果[3 4 6 9 12 15 32 ]

時間復雜度

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

到此這篇關于一文帶你了解Java選擇排序的原理與實現(xiàn)的文章就介紹到這了,更多相關Java選擇排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論