[原]08-Python3实用教程-排序算法-选择排序

选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

对于一个长度为N的列表,排序步骤:

分为已排序队列和未排序队列,初识时已排序队列为空和未排序队列为长度为N的列表。

1、用第一个元素依次跟第二个元素到最后一个元素去比较,用第一个元素交换最小的元素,现在已排序队列是第一个元素,未排序队列是第二个元素到最后一个元素。

2、用第二个元素依次跟第三个元素到最后一个元素去比较,用第二个元素交换最小的元素,现在已排序队列是第一个元素到第二个元素,未排序队列是第三个元素到最后一个元素。

。。。

一直到未排序队列就剩下最后一个元素。

代码实现:

def sort(list):
    for i in range(len(list) - 1):
        index = i
        for j in range(i+1, len(list)):
            if list[j] < list[index]:
                index = j
        if index != i:
            list[i], list[index] = list[index], list[i]
    return list

seq_list = [1, 3, 5, 6, 8, 10, 3]

print(sort(seq_list))
#[1, 3, 3, 5, 6, 8, 10]
分享 提问
comments powered by Disqus