什么是选择排序

选择排序 Selection sort 是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

选择排序思路

先将数组中最小（大）的元素找到并且标记，即记录最小（大）数据的下标，将找到的最小元素移动到最左侧，也就是目前的下标最小（大）的位置，下次比较就除去上次找到并且移动的最小（大）值，对剩下数据继续重复上述操作，直到排序结束。

选择排序其实可以算是对冒泡排序的一个优化，区别就是冒泡排序每次比较完立刻将大小不对数据进行交换，选择排序跟冒泡的对比时间复杂度是一样的，只是每次内循环都将数据最小的角标标记，一轮比较结束之后再交换数据，所以选择排序的数据交换时间复杂度是低于冒泡排序。

图解

  1. 这是第二轮的比较流程图解（升序），黄色表示已排序，也就是说第一轮已经结束，最小的 10 已经被找出来了。
  2. 第二轮排序比较，首先红色的就是本轮起始元素，去掉已排序的 10，从 20 开始，所以 20 用红色表示当前最小值（由于是做升序排序，所以要找出最小的数放前面），与下一个元素 15 比较大小，下一个元素 15 用绿色表示.
  3. 15 比 20 小，所以红色（当前最小值）由 20 变成 15 （此时并未交换位置，只是记录索引，用于表示当前最小值）下次比较就不再使用 20 而是 使用 15, 而下一个比较的数则是 15 后面的 30，所以 30 变绿色。
  4. 以此类推，最后得出最小值是 12，则把 12 替换到未排序的第一位。
图片替换文本

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 *  @title  选择排序
 *  @auhor  Liu Kun
 *  @date   2021/08/26
 *  @param  array 需要做排序的源数组
 *  @param  sort 排序方式 true = 升序  false = 降序，默认升序
 *  @return 排序之后的数组
 **/
function selectionSort (array, sort = true) {
    const length = array.length
    for (let i = 0; i < length; i++){
        // 每一轮找出来的最大值（升序）或者最小值（降序）的索引
        let index = i
        for (let j = i + 1; j < length; j++){
            // 根据参数判断是做升序比较还是降序比较
            const compare = sort ? array[index] > array[j] : array[index] < array[j]
            if(compare) index = j
        }
        // 将每一轮的最大值（升序）或者最小值（降序）替换到未排序的首位
        [array[i], array[index]] = [array[index], array[i]]
    }
    return array
}

应用场景

适用于大多数排序场景，虽然他的对比次数较多，但是数据量大的时候，他的效率明显优于冒泡，而且数据移动是非常耗时的，选择排序移动次数少。

算法稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第 n-1 个元素，第 n 个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列 5 8 5 2 9，我们知道第一遍选择第 1 个元素 5 会和 2 交换，那么原序列中两个 5 的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。