选择排序
- 选择排序(Selection sort)是一种简单直观的排序算法。
- 第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
- 我们认为列表的第一个元素是最小元素,从后面元素依次与首元素比较
- 当存在元素比目标元素小时,最小值更新,直到访问至列表最后的元素
- 将最小值与目标值进行位置交换
- 目标位置向后移动一位并将其认定为最小元素,重复以上步骤依次进行比较
- 会将所有小的元素选择出来,排序完毕
- 选择排序的交换操作介于 0 和 (n - 1) 次之间。
- 选择排序的比较操作为 n (n - 1) / 2 次之间。
- 选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。
- 比较次数 O (