选择排序¶
一、算法描述¶
1.1 核心思想¶
- 数据分为已排序区间和未排序区间
- 从未排序区间中找到最小/最大的元素，放到到已排序区间的尾部
- 执行 n 轮后，所有未排序元素都会迁移到已排序区间中
1.2 细节解释¶
比如说，数组 [2, 7, 1, 4, 3, 6, 5]。
首先分成未排序和已排序区间，已排序区间一开始是空的：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 6 | 5 |
首先找到未排序区间的最小值，也就是 1，将 1 迁移到已排序区间中：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | | 7 | 2 | 4 | 3 | 6 | 5 |
继续从未排序区间找最小值，得到 2，然后将 2 移动到已排序区间：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | | 7 | 4 | 3 | 6 | 5 |
以此类推，分别交换得到 3、4、5、6、7 的最终位置：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | | 4 | 7 | 6 | 5 |
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | | 7 | 6 | 5 |
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | | 6 | 7 |
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | | 7 |
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
经过 n 轮交换，数组就排好序了。
二、算法实现¶
public void selectSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找未排序区间内的最小值
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 将最小值插入到已排序区间的末尾
swap(arr, min, i);
}
}
执行过程如下：
===== 初始数组 =====
[0, 3, 1, 6, 2, 5, 4]
=====第 1 轮插入=====
[0, 3, 1, 6, 2, 5, 4]
=====第 2 轮插入=====
[0, 1, 3, 6, 2, 5, 4]
=====第 3 轮插入=====
[0, 1, 2, 6, 3, 5, 4]
=====第 4 轮插入=====
[0, 1, 2, 3, 6, 5, 4]
=====第 5 轮插入=====
[0, 1, 2, 3, 4, 5, 6]
=====第 6 轮插入=====
[0, 1, 2, 3, 4, 5, 6]
=====第 7 轮插入=====
[0, 1, 2, 3, 4, 5, 6]
三、算法分析¶
3.1 时间复杂度¶
- 最好时间复杂度：O(n^2)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
3.2 空间复杂度¶
- 空间复杂度：O(1)
- 原地算法
3.3 稳定性¶
- 不稳定排序算法
附录¶
/**
* 选择排序
* <p>
* 时间复杂度：最好 O(n^2) 最差 O(n^2) 平均 O(n^2)
* <p>
* 空间复杂度：O(1)
* <p>
* 稳定性：不稳定
*
* @author weijiaduo
* @since 2022/7/21
*/
public class SelectSort implements Sort {
@Override
public void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找未排序区间内的最小值
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 将最小值插入到已排序区间的末尾
swap(arr, min, i);
}
}
}