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

蔚落 2024-03-31 09:36 79阅读 0赞

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

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