算法理解之排序-选择排序

选择排序是一种简单直观的排序算法, 以当前点为锚点, 向后依次进行比较所有未排序元素, 若比较元素小于锚点元素, 则将锚点重标为小元素位置. 当比较到最后一个元素时, 将锚点位置元素与未排序第一位元素交换.

算法分析

1. 以当前位置元素为锚点.
2. 依次比较未排序的所有元素, 若有小于锚点元素, 则将更小元素标为锚点元素.
3. 将锚点元素与未排序第一元素交换位置.
4. 执行步骤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