[算法]选择排序

目录

1、选择排序的实现

2、例子

3、代码实现

4、时间复杂度和空间复杂度

5、选择排序的缺点——不稳定性

---

1、选择排序的实现

选择排序就是每一轮选择最小的元素直接交换到左侧。这种排序的最大优势，就是省去了多余的元素交换。

2、例子

原始数组和选择排序的过程如下图所示，紫色方块代表数组的有序区：

3、代码实现

4、时间复杂度和空间复杂度

算法每一轮选出最小值，再交换到左侧的时间复杂度是O(n)，一共 迭代n-1轮，所以总的时间复杂度是O(n^2)。 至于空间复杂度，由于该算法是原地排序，并没有用到额外的存储 空间，所以排序的空间复杂度是O(1)。

5、选择排序的缺点——不稳定性

当 数列包含多个值相等的元素时，选择排序有可能打乱它们原有的顺序。例如：

上图中，黄色的元素5原本排在橙色的元素5之前，但是随着第1轮元素3和黄色5的交换，使得后续操作中，黄色的元素5排在了橙色的元素5之后。