数据结构(python)——【06排序: 选择排序】

数据结构——选择排序

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

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_new 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趟排序后的无序区: [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. 法二:

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

第0趟排序记录最小的数，放到第一个位置第1趟排序，记录列表无序区最小的数，放到第二个位置第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)$，但是法一的空间复杂度比法二复杂，因为法一要重开一个列表，所以这里比较推荐法二。