选择排序

学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟

选择排序是一个简单的排序算法,算法从第一个元素开始,通过不断从右边找到找到最小元素,替换当前元素,直到找到最后一个元素,数组就排序完成。最好的情况是当数组已经有序时,时间复杂度是O(N),最坏的情况是当数组是反序时,时间复杂度是O(N^2),平均时间复杂度是O(N^2)。

算法主要思路是

  1. 第一轮,从数组的第一个元素开始,向右查找最小的元素,然后替换当前元素。
  2. 第一轮查找完成后,数组中第一个元素就是最小的元素。
  3. 第二轮,从第二个元素开始向右查找最小的元素,然后替换当前元素。
  4. 第二轮查找完成后,数组中第二个元素就是第二小的元素。
  5. ...
  6. 直到右边只剩下一个元素,也就是数组中最大的元素,排序就完成。

比如数组[4, 2, 1, 3, 7, 6, 5]选择排序过程如下

加载中...

选择排序算法实现如下。

加载中...

选择排序也是一种效率比较低的排序算法,一般适用于对效率要求不高或者数据规模较小的排序。

排序算法选择排序