选择排序简介
选择排序(Selection Sort)是一种简单直观的排序算法。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
简单选择排序过程
简单排序过程很简单,其具体流程如下图所示:
算法实现
1 | /** |
算法分析
时间复杂度
简单选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。
就交换次数而言,在最好情况下,交换次数为0
;在最坏的情况下,交换次数为n-1
。
无论最好最坏情况,其比较次数都是一样多的,基于最终的排序时间是比较和交换的次数总和,其时间复杂度为$\Theta(n^2)$。
在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
空间复杂度
很明显,其空间复杂度为$\Theta(1)$。
稳定性
选择排序是稳定的。