数据结构与算法 9.选择排序 SelectionSort

2021/10/30 9:10:09

本文主要是介绍数据结构与算法 9.选择排序 SelectionSort,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

选择排序 SelectionSort

使用三个指针,指针一固定指向未排序部分的第一个元素,指针二向后遍历序列,指针三记录各轮遍历取到的值
    比较指针一和指针二指向的值,用指针三记录每次比较后需要选取的值(大或小)
    一轮遍历结束后,指针三在未排序序列中找到最大/最小元素,将其存放到排序序列的起始位置
    在剩余未排序序列中,指针一和指针二进行新一轮的遍历和比较,并寻找最大/最小元素,然后存放到排序序列的末尾
重复以上步骤,直到所有元素均排序完成

优点:与数据移动有关
    如果某个元素位于正确的最终位置上,则它不会被移动
    选择排序每次交换一对元素,其中至少有一个元素将被移动到最终位置上
    对n个元素的序列进行排序,最多交换(n-1)次
    所有完全依靠交换来移动元素的排序方法中,选择排序是较优的方法

复杂度:最优时间复杂度:O(n^2)
        最差时间复杂度:O(n^2)
        稳定性:不稳定
降序
def selection_sort(varlist):
    n = len(varlist)

    # 第一个指针,从序列开始逐一取值,不用取序列最后一个值
    for j in range(n-1):

        # 第三个指针,起始位置为指针一所在位置,即外层循环开始的位置
        # 记录每轮循环找出的最大/最小值,即需要交换的值
        min_index = j

        # 第二个指针,从指针一的后一个值开始遍历序列,并逐一与指针三指向的值作比较
        for i in range(j+1,n):
            # 若满足排序条件的值是指针二指向的值,则移动指针三记录该位置
            if varlist[i] > varlist[min_index] :
                min_index = i

        # 每轮循环结束后,比较指针三是否移动了位置,移动过则代表找到了更大/更小的值,交换位置完成排序
        if min_index != j :
            varlist[min_index],varlist[j] = varlist[j],varlist[min_index]

varl = [30,2,78,6,818,1,395]
selection_sort(varl)
print(varl)

[818, 395, 78, 30, 6, 2, 1]



这篇关于数据结构与算法 9.选择排序 SelectionSort的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程