欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]

 

相关标签: 选择排序