《恋上数据结构与算法》排序（二）：选择排序

红太狼 2022-12-29 14:06 109阅读 0赞

# 一、经典十大排序算法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

## 选择排序（Selection Sort） ##

### 1、概念 ###

*  从序列中`找出最大/最小的那个元素`，然后与最`后面/前面的元素交换位置`。**`执行完一轮后，最后面/前面的那个元素就是最大的元素。`**
    
     *  下面代码中, 通过将`索引为0`位置的元素当做`最大元素`, 然后进行循环比较, 如果发现`有元素比0位置的元素要大`, 此时就将`该元素的索引`赋值给`最大元素索引(maxIndex)`即可
 *  **忽略上一步中曾经找到的最大元素(比较的范围就要减1)，重复执行上一步。**

![请添加图片描述][20201222231757490.gif]

### 2、代码实现 ###

> 关于 `if (array[maxIndex] <= array[begin])` 代码中, 比较符号使用`<`和`<=`的说明:
> 
>  *  为了实现我们写的`选择排序`是稳定的排序算法, 此时比较的时候要使用`<=`符号
>  *  比如有序列 (0)10, (1)8, (2)10, (3)9 前面的括号表示它们的索引。
>  *  假如说我们的比较符号使用的是 `<` 号, 当(0)10作为最大元素进行比较的时候, 和(2)10进行比较时,判断就不会通过,所以第一轮循环之后, 最大的元素依然是(0)10。此时就要`和末尾元素(3)9交换位置`, 此时`(0)10`就跑到序列的最后了(变为(3)10). 之后的循环`它`也不会参与, 所以下轮循环(2)10就在`它`的前面了。之前(0)10在(2)10的前面; 排完序之后, (0)10变(3)10, 跑到了(2)10的前面. 此时显然不符合排序的稳定性。
>  *  使用 `<=` 号, 当第一轮循环(0)10与(2)10比较, 它们相等, 此时要将(2)10的索引2变为`maxIndex`, 接着比较, 第一轮比较完(2)10就跑到序列的最后了; 第一轮比较后的顺序: 0(10), (1)8, (2)(9), (3)10. 下次循环比较之后, 0(10)就会和2(9)交换位置, 变为(0)9, (1)8, (2)10, 3(10). 排序之前(0)10就在(2)10的前面, 排序之后它们的顺序还是一致的. 此时的选择排序就是稳定的

static void selectionSort(Integer[] array) { 
        for (int end = array.length - 1; end > 0; end--) { 
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) { 
                if (array[maxIndex] <= array[begin]) { 
                    maxIndex = begin;
                }
            }
            int tmp = array[maxIndex];
            // 此时的end就是下一轮循环的最后索引
            array[maxIndex] = array[end];
            array[end] = tmp;
        }
    }

*  选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序。
 *  最好，最坏，平均时间复杂度：`O(n^2)`，空间复杂度：`O(1)`。
 *  属于`不稳定`排序。

### 3、算法优化 ###

*  选择排序每次循环中都需要找出最小（大）的元素与开始（最后）位置的元素进行交换，可以使用大顶堆来实现查找最大元素，可以将查找元素的时间复杂度由O(n)降低为O(logn)，其实就是`堆排序`。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/0186eddded5043828c429f694047d46c.png
[20201222231757490.gif]: /images/20221120/a56a6221414e4c53854692390e783f33.png