什么是选择排序
选择排序是一种简单直观的排序算法,其主要是每次从待排序数组中选择最大(最小)的数据进行排序。
算法原理
1、获取排序数组中最大(最小) 的元素放在起始位置
2、循环待排序数组中选择最大(最小)元素放在已排序序列末尾
3、循环数组长度N-1次,重复执行第二步则获取到满足规则的序列
时间复杂度
由于运用了双层循环,综合时间复杂度为O(N2)。但是选择排序交换次数比冒泡排序较少,且交换比选择需要更多的CPU,故选择排序比冒泡排序性能更高。
算法稳定性
由于选择排序是选择待排序数组中大于(小于)已排序末尾的元素,如果序列中有多个相同元素可能会破坏相互顺序(比如序列 8 4 9 8 3,如果是升序则第一次会将8和3位置交换,那么两个元素8的顺序就已经和原序列不一致),则选择排序算法不稳定。
小试牛刀
1、定义选择排序的升序降序算法
/**
* 选择排序
* @author senfel
* @version 1.0
* @date 2022/11/21 9:39
*/
@Slf4j
public class SelectionSort {
/**
* 选择排序-升序
* @param array 排序数组
* @author senfel
* @date 2022/11/21 9:40
* @return void
*/
public static void sort(int[] array){
if(null == array || array.length < 1){
return;
}
log.error("选择排序>> 升序,当前待排序数组长度:{},预计循环排序次数:{}次。",array.length,array.length-1);
//比较N-1次,首先确定第一位元素,后续从第二位开始比较,故只会循环N-1
for(int i= 0;i< array.length-1;i++){
//定义未排序初始位置索引
int minIndex = i;
//从待排序(j=i+1)中选择数据比较,找出元素待排序中最小元素索引
for(int j = i+1;j<array.length;j++){
//有小于当前最小索引元素的元素则替换当前最小索引
if(array[minIndex] > array[j]){
minIndex=j;
}
}
//最小索引位置与原始不一致,需要交换元素位置满足升序
if(i!=minIndex){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
log.error("第{}次排序,当前数组顺序为:{}",i+1, Arrays.toString(array));
}
log.error("排序完成,数组最终序列为:{}",Arrays.toString(array));
}
/**
* 选择排序-降序
* @param array 待排序数组
* @author senfel
* @date 2022/11/21 9:59
* @return void
*/
public static void invertedSort(int[] array){
if(null == array || array.length < 1){
return;
}
log.error("选择排序>> 降序,当前待排序数组长度:{},预计循环排序次数:{}次。",array.length,array.length-1);
//比较N-1次,首先确定第一位元素,后续从第二位开始比较,故只会循环N-1
for(int i=0;i<array.length-1;i++){
//定义未排序初始位置索引
int minIndex = i;
//从待排序(j=i+1)中选择数据比较,找出元素待排序中最大元素索引
for(int j = i+1;j<array.length;j++){
//有元素大于缓存索引元素则交换位置
if(array[minIndex] < array[j]){
minIndex = j;
}
}
//未排序索引与缓存索引不一致,则交换元素位置以满足降序规则
if(i!=minIndex){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
log.error("第{}次排序,当前数组顺序为:{}",i+1, Arrays.toString(array));
}
log.error("排序完成,数组最终序列为:{}",Arrays.toString(array));
}
}
2、分别测试选择排序升序、降序算法
public static void main(String[] args) {
//待排序数据
int[] array = {5,3,4,1,9,4,2};
//选择升序
sort(array);
int[] array2 = {5,3,4,1,9,4,2};
//选择降序
invertedSort(array2);
}
3、查看测试结果
10:11:52.690 - 选择排序>> 升序,当前待排序数组长度:7,预计循环排序次数:6次。
10:11:52.693 - 第1次排序,当前数组顺序为:[1, 3, 4, 5, 9, 4, 2]
10:11:52.693 - 第2次排序,当前数组顺序为:[1, 2, 4, 5, 9, 4, 3]
10:11:52.693 - 第3次排序,当前数组顺序为:[1, 2, 3, 5, 9, 4, 4]
10:11:52.693 - 第4次排序,当前数组顺序为:[1, 2, 3, 4, 9, 5, 4]
10:11:52.693 - 第5次排序,当前数组顺序为:[1, 2, 3, 4, 4, 5, 9]
10:11:52.693 - 第6次排序,当前数组顺序为:[1, 2, 3, 4, 4, 5, 9]
10:11:52.693 - 排序完成,数组最终序列为:[1, 2, 3, 4, 4, 5, 9]
10:11:52.693 - 选择排序>> 降序,当前待排序数组长度:7,预计循环排序次数:6次。
10:11:52.693 - 第1次排序,当前数组顺序为:[9, 3, 4, 1, 5, 4, 2]
10:11:52.693 - 第2次排序,当前数组顺序为:[9, 5, 4, 1, 3, 4, 2]
10:11:52.693 - 第3次排序,当前数组顺序为:[9, 5, 4, 1, 3, 4, 2]
10:11:52.693 - 第4次排序,当前数组顺序为:[9, 5, 4, 4, 3, 1, 2]
10:11:52.693 - 第5次排序,当前数组顺序为:[9, 5, 4, 4, 3, 1, 2]
10:11:52.693 - 第6次排序,当前数组顺序为:[9, 5, 4, 4, 3, 2, 1]
10:11:52.693 - 排序完成,数组最终序列为:[9, 5, 4, 4, 3, 2, 1]