Java算法：选择排序

﹏ヽ暗。殇╰゛Y 2024-04-20 12:25 80阅读 0赞

### 一、选择排序 ###

选择排序（Selection sort）是一种简单直观的 ***[排序算法][Link 1]*** 。

工作原理：第一次从待排序的 ***[数据元素][Link 2]*** 中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择 ***[排序][Link 3]*** 是不稳定的排序方法。

### 二、选择排序步骤 ###

1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。  
2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。  
3、重复第二步，直到所有元素均排序完毕。

### 三、java实现选择排序 ###

public static void main(String[] args) {
    
            //数组数据
            Integer[] arr = getData();
            System.out.println(Arrays.toString(arr));
    
            //选择排序
            selectSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        /**
         * 数组进行排序
         *
         * @param arr
         * @return
         */
        private static Integer[] selectSort(Integer[] arr) {
            //循环
            for (int i = 0; i < arr.length; i++) {
                //默认第一个最小值
                int min = arr[i];
                //默认第一个最小值索引
                int min_index = i;
                //循环比较
                for (int j = i + 1; j < arr.length; j++) {
                    //比较找出最小值
                    if (arr[j] < min) {
                        min = arr[j]; //最小值
                        min_index = j; //对应索引
                    }
                }
     
                //判断最小索引不等于i索引，就交换值；
                if (min_index != i) {
                    arr[min_index] = arr[i]; //将查找到最小值与第i个值交换位置
                    arr[i] = min; //将最小值赋给对应的位置
                }
    
            }
            return arr;
    
        }
    
        /**
         * （1） 生成1-100范围的随机数20个
         */
        private static Integer[] getData() {
            Set<Integer> sets = new HashSet<>();
            Random random = new Random();
            while (true) {
                //生成1-100的随机数
                int ran = random.nextInt(100) + 1;
                //添加
                sets.add(ran);
                //判断生成20个数据
                if (sets.size() >= 20) {
                    break;
                }
            }
            // 将Set转换成数组
            Integer[] arr = sets.toArray(new Integer[sets.size()]);
            return arr;
        }

**效果：**

![849aaf8aa8dd48e8a51cc42c3c26053d.png][]

### 四、性能分析 ###

**时间复杂度**:  
最好最差情况,选择排序的数据之间的比较次数都是固定的,  
而最好情况:数组有序时,需要交换0次,最坏情况:数组无序时,交换n-1次  
总体的排序时间是比较+交换的总和,所以时间复杂度为**O(N^2)**

> 选择排序理解和实现起来都比较简单,但效率比较低,一般很少使用选择排序

?**空间复杂度** :  
 没有额外空间的开销,只有常数个记录的辅助空间,空间复杂度为**O(1)**

[Link 1]: https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E6%258E%2592%25E5%25BA%258F%25E7%25AE%2597%25E6%25B3%2595/5399605
[Link 2]: https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E6%2595%25B0%25E6%258D%25AE%25E5%2585%2583%25E7%25B4%25A0/715313
[Link 3]: https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E6%258E%2592%25E5%25BA%258F/1066239
[849aaf8aa8dd48e8a51cc42c3c26053d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d8845fdb912b463d831b06f0a9b8c74a.png