选择排序（Selection Sort）

一、算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1.2 算法复杂度

1.3 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

2.2 动图演示

2.3 排序过程

下面以数列{20,40,30,10,60,50}为例，演示它的选择排序过程(如下图)。

排序流程

• 第1趟：i=0。找出a[1...5]中的最小值a[3]=10，然后将a[0]和a[3]互换。 数列变化：20,40,30,10,60,50 -- > 10,40,30,20,60,50
• 第2趟：i=1。找出a[2...5]中的最小值a[3]=20，然后将a[1]和a[3]互换。 数列变化：10,40,30,20,60,50 -- > 10,20,30,40,60,50
• 第3趟：i=2。找出a[3...5]中的最小值，由于该最小值大于a[2]，该趟不做任何处理。
• 第4趟：i=3。找出a[4...5]中的最小值，由于该最小值大于a[3]，该趟不做任何处理。
• 第5趟：i=4。交换a[4]和a[5]的数据。 数列变化：10,20,30,40,60,50 -- > 10,20,30,40,50,60

2.4 代码实现

/**
 * @author: huangyibo
 * @Date: 2021/11/17 16:17
 * @Description: 选择排序
 * 文字描述(以升序为例)
 * 1、将数组分为两个子集, 排序的和未排序的, 每一轮从未排序的子集中选出最小的元素, 放入排序子集
 * 2、重复以上步骤, 直到整个数组有序
 *
 * 优化方式:
 * 1、为减少交换次数, 每一轮可以先找最小的索引, 在每一轮最后交换元素
 *
 * 与冒泡排序比较:
 * 1、二者平均时间复杂度都是O(n²)
 * 2、选择排序一般都要快于冒泡, 因为其交换次数少
 * 3、但如果集合有序度高, 冒泡优于选择
 * 4、冒泡属于稳定排序算法, 而选择属于不稳定排序算法
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {5, 9, 7, 4, 1, 3, 2, 8};

        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        //i代表每轮选择最小元素要交换到的目标索引
        for (int i = 0; i < arr.length - 1; i++) {
            //代表最小元素的索引
            int minIndex = i;
            for (int j = minIndex + 1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            //在每一轮最后交换元素
            if(minIndex != i){
                swap(arr, i, minIndex);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2.5 泛型方式实现

public class SelectionSort {

    public static void main(String[] args) {
        Integer[] arr = {5, 9, 7, 4, 1, 3, 2, 8};

        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static <E extends Comparable<E>> void selectionSort(E[] arr){
        //i代表每轮选择最小元素要交换到的目标索引
        for (int i = 0; i < arr.length - 1; i++) {
            //代表最小元素的索引
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[minIndex].compareTo(arr[j]) > 0){
                    minIndex = j;
                }
            }
            //在每一轮最后交换元素
            if(minIndex != i){
                swap(arr, i, minIndex);
            }
        }
    }

    public static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2.6 算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

2.7 与冒泡排序比较

• 1、二者平均时间复杂度都是O(n²)
• 2、选择排序一般都要快于冒泡, 因为其交换次数少
• 3、但如果集合有序度高, 冒泡优于选择
• 4、冒泡属于稳定排序算法, 而选择属于不稳定排序算法

参考： https://www.cnblogs.com/onepixel/articles/7674659.html

https://www.cnblogs.com/skywang12345/p/3597641.html