本文主要是介绍数据结构与算法 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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!