【视频+图文+动画】详解选择排序(轻松易理解系列)
一、视频讲解选择排序
二、选择排序的思想
思想:(注：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
-
粉色的数字：假定的最小值，
-
绿色的数字：需与假定最小值比较的数，
-
橘色的数字：位置固定的数字【位置一旦固定，不参与下次排序】
（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
-
粉色的数字：假定的最小值，
-
绿色的数字：需与假定最小值比较的数，
-
橘色的数字：位置固定的数字【位置一旦固定，不参与下次排序】
（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
-
粉色的数字：假定的最小值，
-
绿色的数字：需与假定最小值比较的数，
-
橘色的数字：位置固定的数字【位置一旦固定，不参与下次排序】
（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
-
粉色的数字：假定的最小值，
-
绿色的数字：需与假定最小值比较的数，
-
橘色的数字：位置固定的数字【位置一旦固定，不参与下次排序】
（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
-
粉色的数字：假定的最小值，
-
绿色的数字：需与假定最小值比较的数，
-
橘色的数字：位置固定的数字【位置一旦固定，不参与下次排序】
（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
-
粉色的数字：假定的最小值，
-
绿色的数字：需与假定最小值比较的数，
-
橘色的数字：位置固定的数字【位置一旦固定，不参与下次排序】
（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
到此选择排序讲解完啦~~
