算法理解之排序-选择排序
选择排序是一种简单直观的排序算法, 以当前点为锚点, 向后依次进行比较所有未排序元素, 若比较元素小于锚点元素, 则将锚点重标为小元素位置. 当比较到最后一个元素时, 将锚点位置元素与未排序第一位元素交换.
算法分析
- 以当前位置元素为锚点.
- 依次比较未排序的所有元素, 若有小于锚点元素, 则将更小元素标为锚点元素.
- 将锚点元素与未排序第一元素交换位置.
- 执行
步骤1``步骤2``步骤3直到元素遍历完成.
动图效果
选择排序.gif
时间复杂度与空间复杂度与稳定性
稳定性: 不稳定
时间复杂度: O(N^2)
空间复杂度: O(1)
稳定性分析: 锚点位置永远要新于已排序位置, 而无论选择元素是否为原锚点元素, 锚点标记循环完成时, 都要与未排序的第一个元素交换(可能是自身交换自身).
时间复杂度解析: 选择排序一共有两次迭代, 外层确保所有元素均会被遍历, 内层迭代来选择未排序的元素与锚点间关系. 所以时间为O(N^2).
空间复杂度解析: 所有排序均在当前列表中完成, 不存在额外使用内存情况. 所以空间复杂度为O(1).
代码示例
def select_sort(li):
# 获取链表长度
li_len = len(li)
# 外层循环, 确保所有元素被便利
for i in range(0, li_len - 1):
# 锚点标记
anchor = i
# 第二层循环, 重新定位锚点
for j in range(i, li_len -1 ):
# 确认锚点是否需要变更
if li[anchor] > li[j + 1]:
anchor = j + 1
# 变更锚点, 这句话证明其为不稳定
li[anchor], li[i] = li[i], li[anchor]
return li
