04《算法入门教程》选择排序

1. 前言

本节内容是排序算法系列之一：选择排序，主要讲解了选择排序的主体思路，选取了一个待排序的数字列表对选择排序算法进行了演示，给出了选择排序算法的 Java 代码实现，帮助大家可以更好的理解选择排序算法。

2. 什么是选择排序？

选择排序（Select Sort），是计算机科学与技术领域中较为简单的一种排序算法。

假设我们按照从小到大的顺序进行排序。选择排序会首先从待排序序列中选择一个最小的元素放入排序好的序列中，然后依次在从未排序好的序列中选择最小的元素，直到最后需要选择的待排序序列中只有一个元素，只需要将这个元素放在最后位置，就完成了整个排序过程。

选择排序的算法名称的由来就是因为在排序的过程中，按照排序规则（升序或者降序），依次从待排序的序列中选择出需要排列的元素。越小或者越大的元素会先选择出来，直至完成整个排序。

3. 选择排序过程

在介绍完选择排序之后，我们一起来看一下选择排序的实现步骤具体是什么样的吧。这里我们假设待排序的序列为 [9,2,11,7,12,5]，我们按照从小到大的序列进行排序。

3.1 算法步骤

1. 步骤 1：

在待排序的序列中找到最小的元素，将最小元素与排序序列中首位元素交换位置；

伪代码实现如下：

//待排序的序列记为A，寻找最小元素的伪代码如下：
min = A[0]
for(int i=1;i<A.length;i++){
   if(A[i] < min){
     min = A[i]
   }
}

1. 步骤 2：

从剩余的未排序序列中，继续找出一个最小元素，将最小元素与排序好的序列的下一个位置进行交换；

1. 步骤 3：

重复步骤 2 的工作，直至排序完成。

其实，选择排序主要是靠步骤 2 的重复执行，他会每次把最小的元素先选择出来，然后放在排序好的序列的尾部。接下来，让我们用上面的待排序数字序列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

3.2 算法演示

按照 2.1 节的排序步骤，首先我们会找出排序数字序列 [9,2,11,7,12,5] 中的最小元素 2，将 2 看作是排序好的元素，放在排序好的序列首位，如下：

[9,2,11,7,12,5]   -->  [2,9,11,7,12,5]   //找出待排序序列中最小元素2，放在首位，所以与9交换了位置
代码块1

接着，步骤 2，步骤 3 的描述，我们重复进行最小元素的选择工作，整个过程如下：

[2,9,11,7,12,5]   -->  [2,5,11,7,12,9]   //找出[9,11,7,12,5]中最小元素5，然后与9交换位置
[2,5,11,7,12,9]   -->  [2,5,7,11,12,9]   //找出[11,7,12,9]中最小元素7，然后与11交换位置
[2,5,7,11,12,9]   -->  [2,5,7,9,12,11]   //找出[11,12,9]中最小元素9，然后与11交换位置
[2,5,7,9,12,11]   -->  [2,5,7,9,11,12]   //找出[12,11]中最小元素11，然后与12交换位置
[2,5,7,9,11,12]   -->  [2,5,7,9,11,12]   //最后一个元素12，已经在排序好的位置上，排序完成

5f151708090494a909550616.jpg

步骤 2 会依次从待排序的序列中选择一个最小的元素出来，然后将最小元素与排序好的序列的下一个位置的元素进行互换。重复整个 步骤 2，直至最后待排序序列只剩下一个元素，最后一个元素已经排序好，说明整个排序过程结束。

Tips: 步骤 2 中每次执行选择一个最小的元素时，都会在未排序序列的内部进行一次比较筛选，记录下最小元素的位置，当遍历完成整个待排序序列之后，就可以确定最小元素的位置，将最小元素与已排序好序列的下一个元素进行位置互换，就完成了一个选择最小元素的过程。

从上面的示例可以看出，其实整个选择排序的过程，每次都会去在未排序序列的内部进行一次选择，找出最小的元素，将未排序序列中最小元素放在排序好的序列的下一位置。重复执行这个过程，就可以完成排序。

4. Java 代码实现

在说明选择排序的整个过程之后，接下来，我们看看如何用 Java 代码实现选择排序算法。

import java.util.Arrays;

public class SelectSort {

    public static void main(String[] args) {
        //初始化需要排序的数组
        int array[] = {9, 2, 11, 7, 12, 5};

        //依次进行选择排序，每次找出最小的元素，放入待排序的序列中
        for(int i=0;i<array.length;i++){
            
            //记录最小元素min和最小元素的数组下标索引minIndex
            int min = array[i];
            int minIndex = i;

            //在未排序的序列中找出最小的元素和对应数组中的位置
            for(int j=i+1;j<array.length;j++){
                if(array[j] < min){
                    min = array[j];
                    minIndex = j;
                }
            }
            
            //交换位置
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }

        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

运行结果如下：

[2, 5, 7, 9, 11, 12]

代码中的第 7 行初始化一个需要排序的数组，后面按照从小到大的排序规则，实现了数组的排序。第 10 行是外层 for 循环，不断地重复选择排序工作。第 17 行是内层循环，不断地实现每一次 “选择 “，在未排序的序列中找出最小的元素和对应数组中的位置。第 24 至第 27 行实现了将未排序好的序列中的最小元素与需要排序的位置的元素进行交换的功能。第 31 行打印出排序好的数组。

5. 小结

本节主要学习了选择排序算法，在学完本节课程之后，需要熟悉选择排序的算法流程，知道选择排序算法的实现思路，可以自己用代码实现选择排序算法。至此，我们已经学习了排序算法中的冒泡排序、插入排序、选择排序，希望大家可以比较一下不同排序算法的实现思路，自己多总结思考。