算法从入门到精通：选择排序

冷不防 2023-10-06 14:57 23阅读 0赞

### 一、排序和算法 ###

排序是算法中的一部分，也叫排序算法。算法一般用来处理数据，而数据的处理最好是要找到他们的规律，这个规律中有很大一部分就是要进行排序，所以需要有排序算法。本节讲解的是选择排序，从选择排序开始认识排序的一些基础概念。之所以将选择排序作为排序的入门，原因是选择排序算法的逻辑最好理解。

### 二、选择排序 ###

#### 2.1 选择排序算法逻辑 ####

选择排序是一种最简单的排序算法。其排序的逻辑如下：

1、有一个待排序的数组A（以下简称A）。

2、从A中找出最小的元素。

3、将找到的最小元素跟数组A中第一个元素交换位置（如果最小元素就是第一个元素，则自己跟自己交换位置）；如下图：

![ead9cdd1019806a6eef29c49357c5e25.png][]

(如上图，长方形高低代表数字的大小，找到最小的数字，跟第一个位置的数据进行交换）

交换之后，结果如下图所示：

![c8235fa73fe415b31a3892e52b07967c.png][]

4、然后，在剩下的4个数字中再找到最小的那个数字，跟第2个位置的数字交换。如下图：

![d494a3110533dcae665777e9d63a13ce.png][]

交换之后的结果如下如：

![08c79a23db636860c7254cd6bfb2969f.png][]

5、再在剩下的三个数字中，找到最小的那个数字跟第3个位置的数字交换位置。上图中剩下的三个数字中最小的就是第3个位置的数字，所以，它自己跟自己交换位置，就是不变。同理第四个数字也是不变，第5个数字也是不变。（上图中例子第3、4、5个元素正好就是对应的排序，所以不变。如果不是对应的最小数字，同理交换位置就行。）

以上就是选择排序的算法逻辑，非常好理解。（如果有疑问的同学，欢迎下方留言）。

#### 2.2 选择排序算法代码实现 ####

理解了选择排序的逻辑之后，接下来通过java代码实现选择排序算法。步骤如下：

1、找出最小的数字

2、将最小的数字放到第一个位置

3、将第一个位置的数字，放到原本是最小数字的位置。

4、重复上面3个步骤

选择排序java代码如下：

/**
     * 选择排序
     */
    public static void algorithm4(){
        //定义一个整数类型数组，用于排序的原始数据
        int[] array={3,5,1,2,4}; 
        //获取数组的大小
        int length = array.length; 
        //第一个循环用来遍历数组中的所有数字
        for (int i = 0; i < length; i++) { 
            //初始化一个变量，用来记录最小数字的下标。初始默认假设第一个数字就是最小数字
            int minIndex = i; 
            //第二个循环，通过比较获取数组中最小的数字的下标。
            for (int j = i+1; j < length ; j++) { 
                //如果找到更小的数字，
                if (array[minIndex]>=array[j]) {
                    //将minIndex变量的值修改为新的最小数字的下标。
                    minIndex = j;
                }
            }
     
            //所有数字一个个比较结束之后，就能确认那个数字最小了。
            //将最小的数字替换到第一个位置，将第一个位置的数字放到最小数字原来的位置，就是一次交换。
            int temp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=temp;
        }
     
     
        //将排序之后的数组打印出来。
        //下面的输出是不计算时间复杂度的，因为实际开发中这段输出代码会被删掉
        for (int i = 0; i < length; i++) {
            System.out.print(array[i]+"，");
        }
     
    }

以上就是选择排序的代码实现。学习了前面的时间复杂度之后，大家可以计算一下选择排序的时间复杂度是多少呢？

#### 2.3、选择排序的时间复杂度 ####

选择排序总共循环了所少次？

n+(n-1)+(n-2)+(n-3)+…+1

上述这个表达式，反过来写就是1+2+3+4+5+…+n。高斯算法就是（n+1）*n/2=(n^2+n)/2=1/2*n^2+n/2。当n->∞时，利用极限思维1/2\*n^2+n/2可以等于n^2，记作O(n^2)，也就是选择排序的时间复杂度是O(n^2)。

### 总结 ###

选择排序是一种简单的排序算法，适用于数据量较小的情况，因为根据时间复杂度分析，数据量越大，选择排序所花费的时间按照平方倍数增长，会非常慢。但是选择排序也有它的优势，选择排序的优势就是思维逻辑简单。

选择排序还有个特点，就是不论数组的顺序是排好序或者是乱序的，选择排序都需要花费一样的时间来计算。比如，利用选择排序对数组\{1,2,3,4,5\}和数组\{3,1,4,2,5\}排序所花费的时间是一样的。

排序是算法中比较重要的内容，从简单的入手，从易到难学习常见排序算法是一个比较好的方式。如果有疑问的欢迎大家留言讨论。

[ead9cdd1019806a6eef29c49357c5e25.png]: https://img-blog.csdnimg.cn/img_convert/ead9cdd1019806a6eef29c49357c5e25.png
[c8235fa73fe415b31a3892e52b07967c.png]: https://img-blog.csdnimg.cn/img_convert/c8235fa73fe415b31a3892e52b07967c.png
[d494a3110533dcae665777e9d63a13ce.png]: https://img-blog.csdnimg.cn/img_convert/d494a3110533dcae665777e9d63a13ce.png
[08c79a23db636860c7254cd6bfb2969f.png]: https://img-blog.csdnimg.cn/img_convert/08c79a23db636860c7254cd6bfb2969f.png