算法篇-排序算法-选择排序

￡神魔★判官ぃ 2024-02-06 00:15 42阅读 0赞

闲言少叙，直接开始。

#### 一、关于排序算法中的选择排序 ####

##### 百度概念： #####

选择排序(Selection sort)是一种简单直观的[排序算法][Link 1]。它的工作原理是每一次从待排序的[数据元素][Link 2]中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

##### 理解概念： #####

选择排序依次循环找出一个最大（或最小）的值，其中找的过程是直接在全数据中找，找到后将位置进行互换。可以类比冒泡排序进行理解，冒泡是相邻的两个数据进行比较，后进行冒泡操作，而选择排序是整体进行比较。

#### 二、选择排序的实现步骤 ####

1、在数据组中选择出最大或最小的数据，符合要求按照所需要的排序顺序进行位置互换

2、不再已经排好序的数据，将从数据往后开始进行第一步操作

3、循环迭代，进行整体数据的选择排序

#### 三、步骤实现 ####

第一步（代码实现）

方法分析：在for里进行循环选择出最大或者最小的值，先排序好一个数据：

import java.util.Arrays;
    
    public class XZDemo02 {
        public static void main(String[] args) {
            //拟定待排序数组
            int arr[] = {45,2,43,23,80,60,56};
            //指定一个初始的位置
            int n =0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[n]>arr[i]){
                    //找到最小值的索引
                    n=i;
                }
            }
            int temp=arr[0];
            arr[0]=arr[n];
            arr[n]=temp;
            //最后遍历完成后的数据为：[2, 45, 43, 23, 80, 60, 56]
        }
    }

通过遍历完成后的数据可以看出，找到了数据中最小的数据，并将位置进行互换，其他数据位置不变。

第二步和第三步（代码实现）

方法分析：可以通过双层for进行循环，外层的循环可以控制循环的次数的同时，方便调节开始转换的位置，用外层的i代替初始位置的变化。

import java.util.Arrays;
    
    public class XZDemo01 {
        public static void main(String[] args) {
            //拟定待排序数组
            int arr[] = {45,2,43,23,80,60,56};
            //使用for配合if操作选择出最大或者最小的数据进行排序
            for (int i = 0; i < arr.length; i++) {
                int n=i;
                for (int j = i+1; j < arr.length; j++) {
                    if (arr[n]>arr[j]){
                        n=j;
                    }
                }
                int temp = arr[i];
                arr[i]=arr[n];
                arr[n]=temp;
                System.out.println("第"+i+"次，循环的结果为："+Arrays.toString(arr));
            }
        }
    }

![610e0d956ac1441da5b0949395f96f69.png][]

#### 四、选择排序算法分析 ####

##### 时间复杂度： #####

最好的情况下，已经排好序，故此不需要进行再度排序，交换的次数为0,；

最坏的情况下，逆序，此时需要交换的次数为n-1；

故此，选择排序算法的平均的时间复杂度为：O(n^2)

##### 算法稳定性分析： #####

在选择排序中，每次选择最小（或最大）的元素放到已排序的部分的末尾。当遇到大小相同的两个元素时，选择排序会将后面的元素放到前面，导致相同元素的相对顺序发生改变，因此**选择排序是不稳定的。**

今天的理解就到这里了，欢迎大家一起交流学习，共勉！！！

[Link 1]: https://baike.so.com/doc/5414131-5652272.html
[Link 2]: https://baike.so.com/doc/6144813-6357989.html
[610e0d956ac1441da5b0949395f96f69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/be50883d0c4b43f0a1c9389029214137.png