选择排序是一种简单直观的排序算法。它的工作原理如下：在未排序序列中找到最小(大)元素,交换到起始位置,该元素为已排序序列的起始元素，继续在剩余未排序元素中找到最小(大)元素,交换到未排序序列起始位置，重复第二步,直到所有元素均排序完毕。
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
简单来说：就是在每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
思路总结：
在一个有n个元素中，进行排序，下标范围是，然后我们要在，中找到最小的数与0下标的数进行交换，接着在1 ~ n - 1下标中找最小值与1下标交换，然后下次就是2 ~ n - 1找最小值与2交换，每次找到最小值丢到最前面，接着交换，随即下标3,4，5…直到n - 1次选择都排完序，前n-1之前有序了，最后一个也有序。
特性总结：
时间复杂度:
外层for循环从0到n-2,共执行n-1次。内层for循环每次从i+1到n,共执行n-i-1次。所以总时间复杂度为:T(n) = Σ(n-1)(n-i-1) = Θ(n^2)选择排序的时间复杂度是O(n ^ 2)。
空间复杂度:
该算法只使用了一个临时变量mini来记录每次循环找到的最小元素的下标。且不需要额外的数组空间。所以空间复杂度为O(1)。
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
🌠选择排序优化
🌠优化方法
以上算法是每次找出最小的值放在指定位置，一共要找n-1次。如果我们每次不仅找到最小的值，还找到最大的值，将最小的与左端交换，最大的与右端交换，那么就少了一半的遍历次数，从而提高效率。
🌉排序优化后问题
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
通过不断地将当前元素插入到已经排好序的有序序列中,直到全部元素排完,即完成整个排序过程。
时间复杂度：
最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
元素集合越接近有序，直接插入排序算法的时间效率越高
空间复杂度：O(1)，它是一种稳定的排序算法