排序算法之详解选择排序
引入
- 选择排序顾名思义是需要进行选择的,那么就要问题了,选择到底是选择什么呢?
- 选择排序的选择是选择数组中未排序的数组中最小的值,将被选择的元素放在未排序数组的首位
如果你对 ‘未排序数组’ , ‘选择’ 的概念不理解,那么你可以看看下面的图
思路
- 有了上面的一些基础之后,我们再来说说选择排序算法的思路
- 不断的选择未排序数组中最小的值,将其与未排序数组的首位元素进行换位
- 选择完一个最小值,未排序的数组长度就要减一,且是从下标为0处开始减
- 当未排序数组就剩两个数时,就是最后一次选择,完成此次排序,算法结束,数组排序完成
- 乍一看,选择排序算法有点像冒泡排序,只不过冒泡排序是选择大的数往后走,选择排序是选择小的数往前走
- 其实并不是这样的,数往前后走并没有关系
- 冒泡排序是经过不断的相邻换位,来完成排序的
- 而选择排序,只需选择(保存)最大或最小的数及这个数的下标,遍历完未排序数组之后,再进行一次换位
- 冒泡排序是通过数去找位置,选择排序是给定位置去找数
- 如果你还不明白,那么就再看看下面这张图,说明:该图转载于菜鸟教程
具体实现过程
- 下面我们就以 [ -8 , 10 , 30 ,6 , 9 , 10 , 100 , 76 ] 为例,讲解选择排序的具体过程
第一次排序
- 我们先进行选择,将未排序数组的第一个元素作为被选则的元素 【value = -8 ,index = 0】
- 用一个指针从未排序数组的第一个元素往后逐渐遍历 ,如果有小于当前 value 的 ,就将 value 和 index 的值替换为更小的元素的 值 和 下标
- 遍历完成,由于没有小于 -8 的元素 ,所以value 和 index 不做改动 【即不交换】
- 完成第一次排序之后,未排序的数组(逻辑意义上的数组)就变成了 [ 10 , 30 ,6 , 9 , 10 , 100 , 76 ] ,前面已排序的数组 [-8 ]
第二次排序
- 我们先进行选择,将未排序数组的第一个元素作为被选则的元素 【value = 10 ,index = 1】
- 用一个指针从未排序数组的第一个元素往后逐渐遍历 ,如果有小于当前 value 的 ,就将 value 和 index 的值替换为更小的元素的 值 和 下标
- 先找到了 value1 = 6 , index1 = 3 ,改变 value 与 index的值 value= 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 = 100
- 通过指针遍历未排序数组 ,试着寻找 比 value小的数
- 找到则交换 ,交换后进行下次寻找 ,直至数组遍历完成
- 最终 ,index = 7 , value = 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;
}
春去秋来,岁岁平安