看到同事偷偷学习选择排序算法
排序算法作为实用且面试常考的算法，虽然各大编程语言都有其相关的API实现。但是通过学习各种排序算法来训练编码能力，锻炼算法思维，入门算法何乐而不为呢？
同时我们知道了定义一个算法优劣的两个指标：
- 时间复杂度
- 空间复杂度
同时又引入了一个排序算法的额外指标：「稳定性」：对于存在相等元素的序列，排序过后，原相等元素的排序结果中的相对位置相比原输入序列不变。
冒泡排序的各项指标是：
- 时间复杂度：O(N2)O(N^2)O(N2)
- 空间复杂度：O(1)O(1)O(1)
- 稳定
接下来我今天就来学习以下另一个较为简单的排序算法「选择排序」。
下面是各大排序算法的时间复杂度和空间复杂度，以及稳定性
| 排序算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性* |
|---|---|---|---|---|---|
| 冒泡 | O(n2)O(n^2)O(n2) | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 稳定 |
| 选择 | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 不稳定 |
| 插入 | O(n2)O(n^2)O(n2) | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 稳定 |
| 希尔 | O(nlogn)O(nlogn)O(nlogn) ~ O(n2)O(n^2)O(n2) | O(nlogn)O(nlogn)O(nlogn) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 不稳定 |
| 希尔 | O(nlog3n)O(nlog_3n)O(nlog3n) ~ O(n32)O(n^\frac{3}{2})O(n23) | O(nlog3n)O(nlog_3n)O(nlog3n) | O(n32)O(n^\frac{3}{2})O(n23) | O(1)O(1)O(1) | 不稳定 |
| 归并 | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(n)O(n)O(n) | 稳定 |
| 快速 | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(n2)O(n^2)O(n2) | O(logn)O(logn)O(logn) | 不稳定 |
| 堆 | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(1)O(1)O(1) | 不稳定 |
| 计数 | O(n+k)O(n + k)O(n+k) | O(n+k)O(n + k)O(n+k) | O(n+k)O(n + k)O(n+k) | O(n+k)O(n + k)O(n+k) | 稳定 |
| 基数 | O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数 | O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数 | O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数 | O(n+k)O(n + k)O(n+k) | 稳定 |
| 桶 | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) or O(nlogn)O(nlogn)O(nlogn) | O(n)O(n)O(n) | 稳定 |
算法描述
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。—— 百度百科
对于一个要排序的数组，设置一个minIdxminIdxminIdx记录最小数字下标。
- 先假设第一个数字最小，即
minIdx=0 - 后将
minIdx与后续数字逐一比较，当遇到更小的数字时，将下标赋值给minIdx - 第一轮比较将找出此时数组中最小的数字，然后将
swap(arr,0,minIdx)minIdx下标的元素与下标为0处的元素进行交换（排序）。 - 然后开始第二轮比较，令
minIdx=1重复上述过程。每一轮的比较将使得当前未排序数字中的最小值排序，未排序数字总数将会减1。所以arr.length-1轮结束排序完成。
稳定性
这里的稳定性是不稳定的。当数组为[51,52,1][5_1,5_2,1][51,52,1]时，按照上述描述进行升序排序操作。
- 第一轮找到的最小值为111，会与数组第一个元素进行交换[1,52,51][1,5_2,5_1][1,52,51]
- 第二轮找到的最小值为525_252，会与数组第二个元素进行交换[1,52,51][1,5_2,5_1][1,52,51]
- 第三轮找到的最小值为535_353，会与数组第三个元素进行交换[1,52,51][1,5_2,5_1][1,52,51]
此时是不符合稳定性定义的。所以是不保证其稳定性的。
代码实现
public static void selectSort(int[] arr) {
int n = arr.length;
// n - 1 轮次执行,当前 n - 1 个元素排好后，最后一个元素无需执行，故 i < arr.length - 1
for (int i = 0; i < n - 1; ++i) {
//最小值下标
int minIndex = i;
//j=i+1 可以减少一次j=i的循环判断
for (int j = i + 1; j < n; ++j) {
//当前元素小于最小值元素
if (arr[j] < arr[minIndex]) 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;
}
代码优化
我们可以发现，我们每一次遍历寻找找到的只是一个最小值，那么其实我们也是可以找到最大值的。当我们进行升序排序的时候同时定义两个值minIdx和maxIdx，双元选择优化。最小值从0开始往右放，最大值从arr.length-1开始左放。这样可以一轮遍历确定两个元素的位置，遍历次数减少了一半，但是每轮的操作变多，因此该优化只能少量提升选择排序的速度。复杂度介于单元选择排序及其一半之间，只有系数的区别。
public static void selectSortOpt(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1 - i; ++i) {
int minIndex = i, maxIndex = i;
//找到本轮中最大、最小值下标
for (int j = i + 1; j < n - i; ++j) {
if (arr[j] < arr[minIndex]) minIndex = j;
if (arr[j] > arr[maxIndex]) maxIndex = j;
}
//本轮最大值已经等于最小值，说明已经有序
if (minIndex == maxIndex) break;
// 若本轮第一个数字不是最小值，则交换位置（与本轮第一个数字交换位置）
if (minIndex != i) Swap.swap(arr, i, minIndex);
//在交换i和minIdx时，有可能出现i即maxIdx的情况，因为上面已经将i和minIndex交换 所以此时需要修改maxIdx为minIdx
if (maxIndex == i) maxIndex = minIndex;
// 若本轮最后一个数字不是最小值，则交换位置（与本轮最后一个数字交换位置）
if (maxIndex != n - 1 - i) swap(arr, n - 1 - i, maxIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
时间空间复杂度
时间复杂度：两层 forforfor 循环，第1轮比较 n−1n - 1n−1 次 ( n = arr.length ) ，最后一轮比较 1 次。总比较次数为 n∗(n−1)/2n*(n - 1) / 2n∗(n−1)/2 次，时间复杂度为 O(n2)O(n^2)O(n2)。 双元选择优化版本也是 O(n2)O(n^2)O(n2)。
同冒泡排序和选择排序的比较次数均为 O(n2)O(n^2)O(n2)，但选择排序的交换次数是 O(n)O(n)O(n)，而冒泡排序的平均交换次数仍然是二次的。
空间复杂度：算法中只有常数项变量，O(1)O(1)O(1)。
选择排序总体而言还是比较简单的，复杂度和冒泡排序也是一样的。不过它们之间的区别，在于是否能够保证「稳定性」上。
- 冒泡排序是能够保证稳定性的。
- 选择排序是不能保证稳定性的。
所以在会这两种算法的前提上，如果要选择一个算法进行排序，那么唯一需要考虑的是需求是否需要保证其「稳定性」上了~
认为本文写的不错的话，请来一个点赞，收藏，关注吧~~~~
