Python编程:排序算法之选择排序

选择排序

一趟遍历记录最小的数,放在第一个位置

在一趟遍历记录剩余列表中最小的数,继续放置

代码实现

# -*- coding: utf-8 -*-
# @File    : select_sort_demo.py
# @Date    : 2018-06-11
import random
# 选择排序 O(n^2)
def select_sort(lst):
    count = 0
    for i in range(len(lst)-1):  # 比较次数
        min_loc = i
        for j in range(i+1, len(lst)):
            if lst[min_loc] > lst[j]:
                min_loc= j
            count += 1
        lst[min_loc], lst[i] = lst[i], lst[min_loc]
    print("count: %s"% count)
lst = list(range(10))
random.shuffle(lst)
select_sort(lst)
print(lst)
#count: 45
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]