python实现选择排序(selection sort)
程序员文章站
2022-05-12 22:04:01
...
选择排序将一组数据(包含n个元素)看成两个部分:无序部分和有序部分,一共做最多n-1轮选择,每一轮都把无序部分中最小(大)值选出来,放到有序部分中。因为每一轮选出来的都是最小(大)值,因此之后的每一轮选出来的都为次小(大)值,直接排在上一轮选出的元素后面即可。
举例,按从大到小排序:
第一轮选择开始:因为刚开始有序部分没有元素,先认为无序部分中的第0位元素就是当前最小值,给她一个索引:min_index,表示这是当前的最小值,放入有序部分中,然后进入无序部分,寻找当前无序部分里的最小值,如果找到比第0号更小的,就先把min_index和找到的第i号元素的下标交换,即互换min_index和i,这样min_index就指向了目前找到的最小值,然后继续往后找,找到更小的就把min_index和当前的i再交换,这样始终保持min_index是给到最小的元素上的,但注意到目前为止都只是min_index在和下标交换,元素本身还没动过,等遍历过一次无序部分之后,就可以出这一轮循环了,也就是找到了这一轮无序部分中的最小值,这时再把min_index指向的元素和第0号元素交换位置,就成功把最小值找出来并放到有序部分中了。第二轮选择再从剩下的无序部分中找到次小值,放到有序部分的最小值的后面,以此类推。
- 最优时间复杂度:O(n2)
- 最坏时间复杂度:O(n2)
- 稳定性:不稳定(考虑升序每次选择最大的情况)
代码实现:
def selection_sort(alist):
n = len(alist)
for j in range(n-1): # j: 0 ~ n-2,一开始整个列表都看做右边的无序部分
min_index = j # 先认为第j个元素为当前最小值,放到左边的有序部分中
for i in range (j+1, n): #i: j+1 ~ n-1,在右边的无序部分中(第j+1个到最后一个元素)
if alist[min_index] > alist[i]: #如果当前认为的最小元素比当前比较的右边无序部分中的元素要大
min_index = i # 那就令当前的min_index指向这个比它更小的元素的下标
alist[j], alist[min_index] = alist[min_index], alist[j] # 千万注意是出了寻找min_index的循环之后,再交换两个元素的位置
测试:
if __name__ == "__main__":
li = [54,26,93,17,77,31,44,55,20]
print(li)
selection_sort(li)
print(li)
运行一下:
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
下一篇: 选择排序