如何選擇排序及其優化

這篇文章主要講解了“如何選擇排序及其優化”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何選擇排序及其優化”吧！

我們先來看看最原始的版本

for (int i = 0; i < beg.length - 1; i++) {for (int j = i + 1; j < beg.length; j++) {if (beg[i] >= beg[j]) {int temp = beg[j];beg[j] = beg[i];beg[i] = temp;
        }
    }
}for (int k = 0; k < beg.length; k++) {
    System.out.print(beg[k] + ",");
}

我們可以發現外面的循環每次都是第i個數和剩下的length-i-1個數做比較

如下圖

優化：

每次遍歷找出最大值和最小值，那么我們循環的次數就會少1/2

for (int i = 0; i < (beg.length - 1) / 2; i++) {int min = i;int max = i;for (int j = i + 1; j < beg.length - i; j++) {
        min = beg[i] >= beg[j] ? j : min;
        max = beg[i] >= beg[j] ? max : j;
    }if (min + max == beg.length - 1) {int temp3 = beg[beg.length - 1 - i];beg[beg.length - 1 - i] = beg[i];beg[i] = temp3;
    } else {int temp = beg[min];int temp2 = beg[max];beg[min] = beg[i];beg[max] = beg[beg.length - 1 - i];beg[i] = temp;beg[beg.length - 1 - i] = temp2;
    }
}for (int k = 0; k < beg.length; k++) {
    System.out.print(beg[k] + ",");
}

最外層遍歷少了1/2 而里層遍歷又少隨著最大值和最小值的縮小而縮小區間

這里需要考慮一下極值的情況即最大值和最小值剛好交換的情況，如圖中1和9剛好是最大值與最小值

感謝各位的閱讀，以上就是“如何選擇排序及其優化”的內容了，經過本文的學習后，相信大家對如何選擇排序及其優化這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！