时间复杂度:O(N^2)
额外空间复杂度:O(1)
是否可实现稳定性:否
思路:
初始化一个变量minIndex用来存储最小数值的下标,每次循环找出最小下标minIndex,然后和当前外层循环最前面的数交换,就能做到每次把本次循环中的最小数值放到最前面
例子:
比如一组数{2,5,1,9}
每次初始化minIndex为当前外循环的最前面的数字,第一次minIndex=0
比较2和5,2<5所以minIndex值不变,再比较2和1,2>1所以minIndex的值变成2
再比较1和9,1<9,minIndex不变,此时所有数值比较完毕,然后交换minIndex和i的值,i代表外层循环的位置
第二次循环,minIndex=1,过程和第一次一样,依次执行下去得到结果
代码:
public static void selectionSort(int[] arr){
if (arr==null||arr.length<2){
return;
}
/*
* 选择排序的思想: 遍历数组 初始化一个变量,代表每次循环找到的最小的数的下标
* 内循环,每一次找的都是最小数的下标,然后每次用当前最小下标的元素和arr[j]比较,
* 看看当前的下表是否是最小下标 循环结束,minIndex就是这一次循环找到的最小的数的下标
* 然后交换i和minIndex的下标
* i代表每次开始的位置也就是每次循环最小的位置
**/
for (int i = 0;i<arr.length;i++){
int minIndex = i;
for (int j = i+1;j<arr.length;j++){
minIndex = arr[minIndex] < arr[j]?minIndex:j;
}
swap(arr,i,minIndex);
}
}
public static void swap(int[]arr,int i ,int j){
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
在这里注意,选择排序是不稳定的,举个例子序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了。