八大排序算法的Python实现__2__选择排序

环境

Python 3.5.2

原理

  • 默认最左侧的元素为最小,而后依次将右侧的每个元素与最左侧的元素比较,如果比最左测的元素小,则交换位置
  • 第一遍遍历会将最小的元素放在最左边,而后继续遍历,依次得出第二小、第三小…第二大的元素

源码

def select_sort(l):
    n = len(l)
    for i in range(n-1):
        for j in range(i+1, n):
            # 一开始默认下标为i的值最小
            if l[j] < l[i]:
                l[j], l[i] = l[i], l[j]


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    select_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(n2)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

说点什么

  Subscribe  
提醒