选择排序的思想是: 给定一个数组arr,其长度为n; 第一次从 arr[0] 到 arr[n-1] 中选取一个最值(按照需求,可以是最大值,可以是最小值,下同)与arr[0]进行交换; 第二次从arr[1] 到 arr[n-1] 中选取一个最值与arr[1]进行交换; 以此类推,直到arr[n-2]到arr[n-1]中选出最值交换后即完成排序。(只剩下一个元素,前面的都是比它小(或者大)的)。
给定数组 arr 为 [ 300, 50 , 120 , 110 ]; 则其初始状态为:
初始状态
定义两个变量minIndex、min,分别表示最小值元素的索引,和最小值元素的值。 先假定最小值元素为循环开始的第一个元素。 第一次循环将minIndex、min分别赋值为 0和300。 循环变量为当前元素的下一个元素的索引。 由图来演示算法过程: 黄色表示当前循环需要遍历的元素。
第一趟排序
第一趟排序状态1
此时 50 < min当前值300,将minIndex赋值为1,将min赋值为50;
第一趟排序状态2 循环变量向后移动。
第一趟排序状态3
此时 120 > min当前值50,循环变量直接向后移动;
第一趟排序状态4
此时 110 > min当前值50,循环变量无法向后移动,当前循环结束。
minIndex不等于循环开始前的首元素的索引0,发生交换。
第一趟排序状态5
第二趟排序
第二趟排序状态1
此时 120 > min当前值100,循环变量直接向后移动;
第二趟排序状态2
此时 120 > min当前值110,循环变量向后移动则会发生越界,当前循环结束。
minIndex等于循环开始前的首元素的索引1,不发生交换。
第三趟排序
第三趟排序状态1
此时 110 < min当前值120,将minIndex赋值为3,将min赋值为110;
第三趟排序状态2
循环变量再向后移动则会发生越界,当前循环结束。
minIndex不等于循环开始前的首元素的索引2,发生交换。
第三趟排序状态3
因为前n-1个元素均排序完毕,所以原数组排序完毕。
我们由例子可知: 选择排序的趟数为数组长度-1
由上面的讲解知道要写成双重循环,最终代码如下:
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
int [] arr = new int[]{300,50,120,110};
System.out.println("排序前的数组" + Arrays.toString(arr));
selectSort(arr);
System.out.println("排序前的数组" + Arrays.toString(arr));
}
public static void selectSort(int[] arr){
int minIndex;//最小值元素索引
int min;//最小值元素
for (int i = 0; i < arr.length - 1; i++) {
minIndex = i;
min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
//交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
}
比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+…+1=
。为
。
选择排序是不稳定的排序算法。 举个例子来说明: 序列 6 9 6 3 10 在第一趟排序时第一个6会和3交换位置,那么原序列中两个6的相对前后顺序就被破坏了。 所以选择排序是一个不稳定的排序算法。
欢迎大家的关注
扫描下方的二维码或者微信搜一搜即可关注我的微信公众号:code随笔
微信公众号:code随笔