目錄
- 一、視頻講解選擇排序
- 二、選擇排序的思想
- 思想:(注:n為陣列長度)
- 三、選擇排序的影片演示及思路分析
- 影片演示:
- 思路分析:
- 四、選擇排序的代碼+代碼優化+代碼詳解
- 代碼--————多個for回圈分別控制排序:
- 結果:
- 優化代碼--————兩個for回圈嵌套控制排序:
- 優化分析:
- 代碼:
- 結果:
- 代碼詳解(優化版本)
- 代碼--————多個for回圈分別控制排序:
一、視頻講解選擇排序
點擊這里去B站觀看視頻~
二、選擇排序的思想
思想:(注:n為陣列長度)
第一次交換中:
- 假定最小數是arr[0]
- 從arr[1]-arr[n-1]找最小值與arr[0]交換,
- 交換過后arr[0]位置上的數確定
第二次交換中:
- 假定最小數是arr[1],
- 從arr[2]-arr[n-1]找最小值與arr[1]交換,
- 交換過后arr[1]位置上的數確定
以此類推......
三、選擇排序的影片演示及思路分析
影片演示:
- 粉色的數字:假定的最小值,
- 綠色的數字:需與假定最小值比較的數,
- 橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】

思路分析:
以7,3,22,15,8為例:n為陣列長度
1.第一次交換:3的位置被固定
- 粉色的數字:假定的最小值,
- 綠色的數字:需與假定最小值比較的數,
- 橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)假定最小數是arr[0]即min=arr[0]=7
(2) 從arr[1]-arr[n-1]找最小值(即從【3,22,15,8】找最小值)與arr[0]交換,
min=7和arr[1]=3比較: 若min>arr[1],min=arr[1],進行下一次比較
- 因為7>3
- 所以min=arr[1]=3
- 進行下一次比較
7 3 22 15 8 ?7 3 22 15 8
min=3和arr[2]=22比較:若min>arr[2],min=arr[2],進行下一次比較
- 因為3<22
- 所以min=arr[1]=3
- 進行下一次比較
7 3 22 15 8 ?7 3 22 15 8
min=3和arr[3]=15比較:若min>arr[3],min=arr[3],進行下一次比較
- 因為3<15
- 所以min=arr[1]=3
- 進行下一次比較
7 3 22 15 8 ?7 3 22 15 8
min=3和arr[4]=8比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為3<8
- 所以min=arr[1]=3
7 3 22 15 8 ?7 3 22 15 8
此時找到了【3,22,15,8】中的最小值:3
所以arr[0]=7和arr[1]=3交換位置
(3)交換過后arr[0]=3位置上的數確定:7 3 22 15 8 ? 3 7 22 15 8

2.第二次交換:7的位置被固定
-
粉色的數字:假定的最小值,
-
綠色的數字:需與假定最小值比較的數,
-
橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)假定最小數是arr[1]即min=arr[1]=7
(2) 從arr[2]-arr[n-1]找最小值(即從【22,15,8】找最小值)與arr[1]交換,
min=7和arr[2]=22比較:若min>arr[2],min=arr[2],進行下一次比較
- 因為7<22
- 所以min=arr[1]=7
- 進行下一次比較
3 7 22 15 8 ? 3 7 22 15 8
min=7和arr[3]=15比較:若min>arr[3],min=arr[3],進行下一次比較
- 因為7<15
- 所以min=arr[1]=7
- 進行下一次比較
3 7 22 15 8 ? 3 7 22 15 8
min=3和arr[4]=8比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為3<8
- 所以min=arr[1]=3
3 7 22 15 8 ? 3 7 22 15 8
此時因為 【22,15,8】 中的數都大于 min=arr[1]=7
所以最小值:min=arr[1]=7
(3)本輪不發生交換 arr[1]=7位置上的數確定:3 7 22 15 8? 3 7 22 15 8

3.第三次交換:8的位置被固定
-
粉色的數字:假定的最小值,
-
綠色的數字:需與假定最小值比較的數,
-
橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)假定最小數是arr[2]即min=arr[2]=22
(2) 從arr[3]-arr[n-1]找最小值(即從【15,8】找最小值)與arr[2]交換,
min=22和arr[3]=15比較:若min>arr[3],min=arr[3],進行下一次比較
- 因為22>15
- 所以min=arr[3]=15
- 進行下一次比較
3 7 22 15 8 ? 3 7 22 15 8
min=15和arr[4]=8比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為15>8
- 所以min=arr[4]=8
3 7 22 15 8 ? 3 7 22 15 8
此時找到了【22,15,8】中的最小值:8
所以arr[2]=22和arr[4]=8交換位置
(3)交換過后arr[2]=8位置上的數確定: 3 7 22 15 8? 3 7 8 15 22

4.第四次交換:15的位置被固定
-
粉色的數字:假定的最小值,
-
綠色的數字:需與假定最小值比較的數,
-
橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)假定最小數是arr[3]即min=arr[3]=15
(2) 從arr[4]-arr[n-1]找最小值(即從【22】找最小值)與arr[3]交換,
min=15和arr[4]=22比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為15<22
- 所以min=arr[3]=15
3 7 8 15 22 ? 3 7 8 15 22
此時因為 【22】 大于 min=arr[3]=15
所以最小值:min=arr[3]=15
(3)本輪不發生交換 arr[3]=15位置上的數確定:3 7 8 15 22? 3 7 8 15 22
四、選擇排序的代碼+代碼優化+代碼詳解
代碼--————多個for回圈分別控制排序:
package Sort;
import java.util.Arrays;
public class SelectionSort {
// 7,3,22,15,8
public static void main(String[] args) {
int arr[] = { 7, 3, 22, 15, 8 };
int min = 0;// 假定最小值
int minIndex = 0;// 假定最小值的下標
int j = 0;
//第一次排序
min=arr[0];//假定最小值為7
minIndex=0;//假定最小值的下標為0
for(j=0+1;j<arr.length;j++) {//從3 22 15 8 中找比7小的數,找到就把這個數變成假定最小值
if(min>arr[j]) {//假定最小值需要替換
min=arr[j];//將假定最小值換為arr[j]
minIndex=j;//將假定最小值下標換為j
}
}
if(minIndex!=0) {//需要交換,就像這里的7和3
arr[minIndex]=arr[0];
arr[0]=min;
}
System.out.println(Arrays.toString(arr));
//第二次排序
min=arr[1];//假定最小值為7
minIndex=1;//假定最小值的下標為1
for(j=1+1;j<arr.length;j++) {//從 22 15 8 中找比7小的數,找到就把這個數變成假定最小值
if(min>arr[j]) {//假定最小值需要替換
min=arr[j];//將假定最小值換為arr[j]
minIndex=j;//將假定最小值下標換為j
}
}
if(minIndex!=1) {//不需要交換,7<22,15,8
arr[minIndex]=arr[1];
arr[1]=min;
}
System.out.println(Arrays.toString(arr));
//第三次排序
min=arr[2];//假定最小值為22
minIndex=2;//假定最小值的下標為2
for(j=1+2;j<arr.length;j++) {//從 15 8 中找比22小的數,找到就把這個數變成假定最小值
if(min>arr[j]) {//假定最小值需要替換
min=arr[j];//將假定最小值換為arr[j]
minIndex=j;//將假定最小值下標換為j
}
}
if(minIndex!=2) {//需要交換,就像這里的22和8
arr[minIndex]=arr[2];
arr[2]=min;
}
System.out.println(Arrays.toString(arr));
//第四次排序
min=arr[3];//假定最小值為15
minIndex=3;//假定最小值的下標為3
for(j=1+3;j<arr.length;j++) {//22 中找比15小的數,找到就把這個數變成假定最小值
if(min>arr[j]) {//假定最小值需要替換
min=arr[j];//將假定最小值換為arr[j]
minIndex=j;//將假定最小值下標換為j
}
}
if(minIndex!=3) {//不需要交換,15<22
arr[minIndex]=arr[3];
arr[3]=min;
}
System.out.println(Arrays.toString(arr));
}
}
結果:

優化代碼--————兩個for回圈嵌套控制排序:
優化分析:
由下表可以看出:
- 我們可以再用一個for回圈
- 嵌套在原有的for回圈外,來回圈表格中紅色數字部分
- 此回圈范圍是【0-3】
| 假定最小值 | 與假定最小值比較的范圍 | |
|---|---|---|
| 第一次交換 | arr[0]=7 | arr[0+1]-arr[4] |
| 第二次交換 | arr[1]=7 | arr[1+1]-arr[4] |
| 第三次交換 | arr[2]=22 | arr[2+1]-arr[4] |
| 第四次交換 | arr[3]=15 | arr[3+1] |
代碼:
package Sort;
import java.util.Arrays;
public class SelectionSort {
// 7,3,22,15,8
public static void main(String[] args) {
int arr[] = { 7, 3, 22, 15, 8 };
int min = 0;// 假定最小值
int minIndex = 0;// 假定最小值的下標
int j = 0;
int i = 0;
for (i = 0; i < arr.length - 1; i++) {//控制需與假定最小值比較的數的范圍
min = arr[i];// 第一次:(1)假定最小值為7
minIndex = i;// 第一次:(1)假定最小值的下標為0
for (j = i + 1; j < arr.length; j++) {//第一次:(1) 從3 22 15 8 中找比7小的數,找到就把這個數變成假定最小值
if (min > arr[j]) {// 假定最小值需要替換
min = arr[j];// 將假定最小值換為arr[j]
minIndex = j;// 將假定最小值下標換為j
}
}
if (minIndex != i) {// 第一次:(1)需要交換,就像這里的7和3
arr[minIndex] = arr[i];
arr[i] = min;
}
System.out.println(Arrays.toString(arr));
}
}
}
結果:

代碼詳解(優化版本)
以7,3,22,15,8為例:n為陣列長度
1.第一次交換:3的位置被固定
- 粉色的數字:假定的最小值,
- 綠色的數字:需與假定最小值比較的數,
- 橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)
- 假定最小數是arr[0]即min=arr[0]=7
- i=0,minIndex=0,j=0+1
(2) 從arr[1]-arr[n-1]找最小值(即從【3,22,15,8】找最小值)與arr[0]交換,
min=7和arr[1]=3比較: 若min>arr[1],min=arr[1],進行下一次比較
- 因為7>3
- 所以min=arr[1]=3
- i=0,minIndex=1
- 進行下一次比較
7 3 22 15 8 ?7 3 22 15 8
min=3和arr[2]=22比較:若min>arr[2],min=arr[2],進行下一次比較
- 因為3<22
- 所以min=arr[1]=3
- i=0,minIndex=1
- 進行下一次比較
7 3 22 15 8 ?7 3 22 15 8
min=3和arr[3]=15比較:若min>arr[3],min=arr[3],進行下一次比較
- 因為3<15
- 所以min=arr[1]=3
- i=0,minIndex=1
- 進行下一次比較
7 3 22 15 8 ?7 3 22 15 8
min=3和arr[4]=8比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為3<8
- 所以min=arr[1]=3
- i=0,minIndex=1
7 3 22 15 8 ?7 3 22 15 8
(3)
-
因為i=0,minIndex=1, i ! = minIndex
-
進入if條件分支陳述句
if (minIndex != i) {// 第一次:(1)需要交換,就像這里的7和3
arr[minIndex] = arr[i];
arr[i] = min;
}
所以arr[0]=7和arr[1]=3交換位置
(4)交換過后arr[0]=3位置上的數確定:7 3 22 15 8 ? 3 7 22 15 8

2.第二次交換:7的位置被固定
-
粉色的數字:假定的最小值,
-
綠色的數字:需與假定最小值比較的數,
-
橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)
- 假定最小數是arr[1]即min=arr[1]=7
- -i=1,minIndex=1,j=1+1
(2) 從arr[2]-arr[n-1]找最小值(即從【22,15,8】找最小值)與arr[1]交換,
min=7和arr[2]=22比較:若min>arr[2],min=arr[2],進行下一次比較
- 因為7<22
- 所以min=arr[1]=7
- i=1,minIndex=1
- 進行下一次比較
3 7 22 15 8 ? 3 7 22 15 8
min=7和arr[3]=15比較:若min>arr[3],min=arr[3],進行下一次比較
- 因為7<15
- 所以min=arr[1]=7
- i=1,minIndex=1
- 進行下一次比較
3 7 22 15 8 ? 3 7 22 15 8
min=3和arr[4]=8比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為3<8
- 所以min=arr[1]=3
- i=1,minIndex=1
3 7 22 15 8 ? 3 7 22 15 8
(3)
-
因為i=1,minIndex=1, i == minIndex
-
不進入if條件分支陳述句
-
所以最小值:min=arr[1]=7
(4)本輪不發生交換 arr[1]=7位置上的數確定:3 7 22 15 8? 3 7 22 15 8

3.第三次交換:8的位置被固定
-
粉色的數字:假定的最小值,
-
綠色的數字:需與假定最小值比較的數,
-
橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)
- 假定最小數是arr[2]即min=arr[2]=22
- i=2,minIndex=2 j=2+1
(2) 從arr[3]-arr[n-1]找最小值(即從【15,8】找最小值)與arr[2]交換,
min=22和arr[3]=15比較:若min>arr[3],min=arr[3],進行下一次比較
- 因為22>15
- 所以min=arr[3]=15
- i=2,minIndex=3
- 進行下一次比較
3 7 22 15 8 ? 3 7 22 15 8
min=15和arr[4]=8比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為15>8
- 所以min=arr[4]=8
- i=2,minIndex=4
3 7 22 15 8 ? 3 7 22 15 8
(3)
-
因為i=2,minIndex=4, i ! = minIndex
-
進入if條件分支陳述句
if (minIndex != i) {// 第一次:(1)需要交換,就像這里的7和3
arr[minIndex] = arr[i];
arr[i] = min;
}
所以arr[2]=22和arr[4]=8交換位置
(3)交換過后arr[2]=8位置上的數確定: 3 7 22 15 8? 3 7 8 15 22

4.第四次交換:15的位置被固定
-
粉色的數字:假定的最小值,
-
綠色的數字:需與假定最小值比較的數,
-
橘色的數字:位置固定的數字【位置一旦固定,不參與下次排序】
(1)
- 假定最小數是arr[3]即min=arr[3]=15
- i=3,minIndex=3 ,j=3+1
(2) 從arr[4]-arr[n-1]找最小值(即從【22】找最小值)與arr[3]交換,
min=15和arr[4]=22比較: 若min>arr[4],min=arr[4],結束第一輪比較
- 因為15<22
- 所以min=arr[3]=15
- i=3,minIndex=3
3 7 8 15 22 ? 3 7 8 15 22
(3)
-
因為i=3,minIndex=3, i == minIndex
-
不進入if條件分支陳述句
所以最小值:min=arr[3]=15
(3)本輪不發生交換 arr[3]=15位置上的數確定:3 7 8 15 22? 3 7 8 15 22
到此選擇排序講解完啦~~
歡迎大家來公號 “小喬的編程內容分享站” 來找小喬玩~
一起學習Java基礎+演算法~
還有更多資源等你來拿哦~
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/63661.html
標籤:其他
上一篇:【學習筆記】SICP讀書筆記&&UCB CS61A學習筆記(學習中。。。)
下一篇:2-從尾到頭列印鏈表
