选择排序🌟🌟🌟🌟🌟
目标：会手写
这篇文章主要带大家来了解什么是选择排序，选择排序可以说是最简单的一种排序算法了。
虽然比较简单，但是在讲解完选择排序的最后也给大家留了一道思考题，大家可以尝试实现，拓展自己的思路。
还记得我们上篇文章讲冒泡排序的原理吗？
算法的核心是在排序的过程中将数组分成有序和无序的两部分，并在排序的过程中不断的让无序的部分变得有序。
其实选择排序的核心思路也是如此。
那选择排序算法是怎么逐渐的将数组变有序的？
我们通过遍历从数组的无序部分中选择最小的元素，并放到数组的有序部分的最后一个位置（升序）。并重复这个过程。
选择排序算法流程分析
我们通过一个对有 n 个元素的数组进行选择排序的具体例子，来演示这个过程。
排序之前
8 4 2 6 9 6
排序之前整个数组从 [0, n - 1] 这个范围都是无序的。
第一轮选择
我们从第一个元素开始，依次遍历数组的无序部分（目前也就是整个数组），发现最小的元素是 2，此时将其放到数组的有序的部分的最后一个位置（即整个数组的第一个位置）。
结果：
2 8 4 6 9 6
此时，数组从 [0, 0] 这个范围是有序的，从 [1, n - 1] 这个范围是无序的。
接下来，我们只需要对 [1, n - 1] 这个范围重复上面的操作。
第二轮选择
我们从第二个元素开始，依次遍历，发现最小的元素是 4。
接下来希望大家自己按照这个比较的方法，自己推演体会这个过程。
结果：
2 4 8 6 9 6
经过第二轮选择之后，数组从 [0, 1] 这个范围是有序的，从 [2, n - 1] 这个范围是无序的。
接下来，我们只需要对 [2, n - 1] 这个范围重复上面的操作进行排序。
继续选择
依次类推，我们可以顺利推出下面几次选择的结果，并在最后得到有序的数组。
第三轮选择结果
2 4 6 8 9 6
第四轮选择结果
2 4 6 6 8 9
第五轮选择结果
2 4 6 6 8 9
代码实现
public void selectSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int minIndex = i;
for (int j = i; j < nums.length; j++) {
minIndex = nums[j] < nums[minIndex] ? j : minIndex;
}
swap(nums, i, minIndex);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
时间复杂度
选择排序的时间复杂度是 ${O(n^2)}$。
仔细想想其实是没有啥优化空间了，因为我们不得不通过遍历数组的无序部分才能选择出最小的元素。
空间复杂度
选择排序和冒泡排序一样，也属于典型的原地排序算法，空间复杂度为 ${O(1)}$，因为只需要常数级别的额外空间来存储临时变量。
稳定性
选择排序 不是一种稳定的排序算法。在我们的算法实现中，在交换元素时，相同元素的相对位置会发生改变。
写在最后
总的来说，选择排序虽然可以说是最简单的排序算法，我们在前文也给出了迭代算法的实现，不过大家可以尝试下用递归的方法，去实现选择排序，同一个问题可以多尝试不同的方法，这样才能打开自己解决问题的思维。
为今后学习更复杂的算法问题提供帮助，毕竟罗马不是一天建成的。
好了，今天的学习比较轻松，我们下篇文章再见。