引入
- 選擇排序顧名思義是需要進行選擇的，那么就要問題了，選擇到底是選擇什么呢?
- 選擇排序的選擇是選擇陣列中未排序的陣列中最小的值，將被選擇的元素放在未排序陣列的首位
如果你對 ‘未排序陣列’ ， ‘選擇’ 的概念不理解，那么你可以看看下面的圖
思路
- 有了上面的一些基礎之后，我們再來說說選擇排序演算法的思路
- 不斷的選擇未排序陣列中最小的值，將其與未排序陣列的首位元素進行換位
- 選擇完一個最小值，未排序的陣列長度就要減一，且是從下標為0處開始減
- 當未排序陣列就剩兩個數時，就是最后一次選擇，完成此次排序，演算法結束，陣列排序完成
- 乍一看，選擇排序演算法有點像冒泡排序，只不過冒泡排序是選擇大的數往后走，選擇排序是選擇小的數往前走
- 其實并不是這樣的，數往前后走并沒有關系
- 冒泡排序是經過不斷的相鄰換位，來完成排序的
- 而選擇排序，只需選擇(保存)最大或最小的數及這個數的下標，遍歷完未排序陣列之后，再進行一次換位
- 冒泡排序是通過數去找位置，選擇排序是給定位置去找數
- 如果你還不明白，那么就再看看下面這張圖，說明：該圖轉載于菜鳥教程
具體實作程序
- 下面我們就以 [ -8 , 10 , 30 ,6 , 9 , 10 , 100 , 76 ] 為例，講解選擇排序的具體程序
第一次排序
- 我們先進行選擇，將未排序陣列的第一個元素作為被選則的元素 【value = https://www.cnblogs.com/fzdkx/p/-8 ，index = 0】
- 用一個指標從未排序陣列的第一個元素往后逐漸遍歷 ，如果有小于當前 value 的 ，就將 value 和 index 的值替換為更小的元素的 值 和 下標
- 遍歷完成，由于沒有小于 -8 的元素 ，所以value 和 index 不做改動 【即不交換】
- 完成第一次排序之后，未排序的陣列(邏輯意義上的陣列)就變成了 [ 10 , 30 ,6 , 9 , 10 , 100 , 76 ] ，前面已排序的陣列 [-8 ]
第二次排序
- 我們先進行選擇，將未排序陣列的第一個元素作為被選則的元素 【value = https://www.cnblogs.com/fzdkx/p/10 ，index = 1】
- 用一個指標從未排序陣列的第一個元素往后逐漸遍歷 ，如果有小于當前 value 的 ，就將 value 和 index 的值替換為更小的元素的 值 和 下標
- 先找到了 value1 = 6 ， index1 = 3 ，改變 value 與 index的值 value= https://www.cnblogs.com/fzdkx/p/value1 ， index = index1
- 遍歷完成，由于index經過了改變 ，所以需要進行換位 ， 未排序陣列第一個元素 與 index下標元素進行換位
- 完成第二次排序之后，未排序的陣列(邏輯意義上的陣列)就變成了 [ 30 ,10 , 9 , 10 , 100 , 76 ] ，前面已排序的陣列 [-8 , 6]
......
- 就這樣不斷地重復，選擇未排序陣列中最小的值，將其與未排序陣列的首位元素進行換位
最后一次排序
- 不斷地進行排序之后，陣列變成了個樣子 [ -8 , 6 , 9 ,10 , 10 ,30 , 100 ,76 ]
- 此時已排序的陣列變成了 [ -8 , 6 , 9 ,10 , 10 ,30 ] , 未排序的陣列為 [ 100 ,76 ]
- 我們只需進行最后一次排序，就可以完成整個陣列的排序
- 選擇未排序陣列的第一個元素 ， index = 6 ， value = https://www.cnblogs.com/fzdkx/p/100
- 通過指標遍歷未排序陣列 ，試著尋找 比 value小的數
- 找到則交換 ，交換后進行下次尋找 ，直至陣列遍歷完成
- 最終 ，index = 7 ， value = https://www.cnblogs.com/fzdkx/p/76
- 由于此時 index已經改變 ，所以需要進行換位 ，未排序陣列第一個元素 與 index下標元素進行換位
代碼實作
// 選擇排序演算法
public static int[] selectSort(int[] array){
// for回圈 ，i表示需要正在選擇 第 i 個 最小值 ，從0開始
// 一共需要找 array.length-1個最小值
for (int i = 0; i < array.length-1; i++) {
// val用于存盤被選則的值 ，即最小值
// 默認選擇未排序陣列的第一個元素 ，如果有更小的則更新
int val = array[i];
// index用于存盤當前最小值對應的陣列下標
// 默認選擇未排序陣列的第一個元素的下標 ，最小值更新，i也隨之更新
int index = i;
// 遍歷未選擇的陣列
for (int j = i+1; j < array.length; j++) {
// 試圖尋找比被選擇的值 更小 的元素 ，如果有 ，則對 val 和 index 進行更新
if (val > array[j]){
val = array[j];
index = j;
}
}
// 如果 i == index ，則代表被選則的值并未改變，即還是未排序陣列的第一個元素，所以不用交換
if (i != index){
array[index] = array[i];
array[i] = val;
}
}
return array;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551197.html
標籤：其他
上一篇：牛客小白月賽71
下一篇：返回列表