本文共 2458 字，大约阅读时间需要 8 分钟。

数据结构——选择排序

    选择排序与前面介绍的冒泡排序要简单一点，不管是思路还是代码。

1. 思路:

    将整个列表分为两个区域: 有序区和无序区，每次找出无序区中的最小值，放在有序区，直到无序区里没有值。

    具体算法思想放在下面的算法讲解再仔细介绍。

2. 代码

1. 法一:

具体思路:

    这一算法的思路非常简单，我们开出了一个新的列表用于储存每次选出的无序区的最小值，作为有序区。每次选出无序区的最小值后，就把无序区的这个最小值移除掉，可以保证每次选的都是无序区的最小值，且该最小值大于有序区目前的最大值！

def select_sort(li):    li_new = []    for i in range(len(li)):        min_val = min(li)        li_new.append(min_val)        li.remove(min_val)        print("第%d趟排序后的无序区:" % i)        print(li)        print("第%d趟排序后的有序区:" % i)        print(li_new)    return li_newli = [3, 4, 2, 1, 5, 7, 9, 6, 8]print(li)select_sort(li)

结果为:

[3, 4, 2, 1, 5, 7, 9, 6, 8]第0趟排序后的无序区:[3, 4, 2, 5, 7, 9, 6, 8]第0趟排序后的有序区:[1]第1趟排序后的无序区:[3, 4, 5, 7, 9, 6, 8]第1趟排序后的有序区:[1, 2]第2趟排序后的无序区:[4, 5, 7, 9, 6, 8]第2趟排序后的有序区:[1, 2, 3]第3趟排序后的无序区:[5, 7, 9, 6, 8]第3趟排序后的有序区:[1, 2, 3, 4]第4趟排序后的无序区:[7, 9, 6, 8]第4趟排序后的有序区:[1, 2, 3, 4, 5]第5趟排序后的无序区:[7, 9, 8]第5趟排序后的有序区:[1, 2, 3, 4, 5, 6]第6趟排序后的无序区:[9, 8]第6趟排序后的有序区:[1, 2, 3, 4, 5, 6, 7]第7趟排序后的无序区:[9]第7趟排序后的有序区:[1, 2, 3, 4, 5, 6, 7, 8]第8趟排序后的无序区:[]第8趟排序后的有序区:[1, 2, 3, 4, 5, 6, 7, 8, 9]

算法复杂度：

    min函数和remove的时间复杂度都是$O(n)$，而这两个函数又是放在一个遍历的下面，所以时间复杂度$O(n^2)$

2. 法二:

具体思路:

    不开新列表，直接在原列表中进行操作，将原列表分为有序区和无序区两个区域。刚开始整个列表都是无序区，然后选取第一个值为最小值，并取得该值的索引，然后遍历第一个值后面的值，选出后面的值的最小值，再交换第一个值和后面选出的最小值的位置，依次下去。 简单来说:

1. 第0趟排序记录最小的数，放到第一个位置
2. 第1趟排序，记录列表无序区最小的数，放到第二个位置
3. 第2趟排序，记录列表无序区最小的数，放到第三个位置
   …

def select_sort(li):    for i in range(len(li) - 1):    # 只需要n-1趟, i是第几趟        min_location = i        for j in range(i+1, len(li)):            if li[j] < li[min_location]:                min_location = j        li[i], li[min_location] = li[min_location], li[i]        print("第%d趟排序后的列表: " % i)        print(li)li = [3, 4, 2, 1, 5, 7, 9, 6, 8]print(li)select_sort(li)

结果为:

[3, 4, 2, 1, 5, 7, 9, 6, 8]第0趟排序后的列表: [1, 4, 2, 3, 5, 7, 9, 6, 8]第1趟排序后的列表: [1, 2, 4, 3, 5, 7, 9, 6, 8]第2趟排序后的列表: [1, 2, 3, 4, 5, 7, 9, 6, 8]第3趟排序后的列表: [1, 2, 3, 4, 5, 7, 9, 6, 8]第4趟排序后的列表: [1, 2, 3, 4, 5, 7, 9, 6, 8]第5趟排序后的列表: [1, 2, 3, 4, 5, 6, 9, 7, 8]第6趟排序后的列表: [1, 2, 3, 4, 5, 6, 7, 9, 8]第7趟排序后的列表: [1, 2, 3, 4, 5, 6, 7, 8, 9]

第0趟排序:

先选索引值为0的3作为最小值，在3后面的值中进行比较，选出后面值中的最小值，再做交换，结果为3和1进行交换，所以此时有序区为1，并且1在列表第一个位置。 第1趟排序: 选索引值为1的4作为最小值(这样子也可以避免选择到有序区的值，现在有序区只有一个值，放在最前面，所以索引为1的时候刚好从有序区后面开始)，在4后面的值中进行比较，再做交换，结果为4和2进行交换，所以此时有序区为[1, 2]，并且2在列表第二个位置。 $...........$ 算法复杂度：     时间复杂度为$O(n^2)$。

3. 总结:

    上述介绍了两种不同方法，两种方法的时间复杂度均为$O(n^2)$，但是法一的空间复杂度比法二复杂，因为法一要重开一个列表，所以这里比较推荐法二。

转载地址：http://ofiwi.baihongyu.com/