数据结构与算法-选择排序

什么是选择排序
选择排序是一种简单直观的排序算法，其主要是每次从待排序数组中选择最大（最小）的数据进行排序。

算法原理
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]