选择排序Python版

117 3月之前 Python 算法

答案

  1. 首先在待排序序列中找到最小元素,存放到序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾
  3. 以此类推,直到所有元素均排序完毕。
def selection_sort(lst):
    n = len(lst)

    for i in range(n):
        min_pos = i
        for j in range(i + 1, n):
            if lst[j] < lst[min_pos]:
                min_pos = j

        lst[i], lst[min_pos] = lst[min_pos], lst[i]

    return lst

时间复杂度:

  • 最坏:O(n2)
  • 平均:O(n2)
  • 最好:O(n2)