选择排序及其优化

选择排序

复杂度：O（n**2)

一、思路

index 0 1 2 3 4 ... n-1 n value 3 1 2 5 4 ... 8

• 思考过程：

1、在整个数组[0,n)内寻找最小值1，将其与list[0]交换位置：1 3 2 5 4 8，此时index=0的位置已排序完成

2、在[1,n)内寻找最小值，将最小值与list[1]交换位置，此时index=1的位置排序完成

3、迭代下去，直到[i,n]长度为1，原地不动即可

二、实现

from random import randint from timeit import Timer from timeit import timeitdef selectionsort1(myarr):for i in range(len(myarr)):#求子数组[i,n)中的最小值对应的indexmin_index = ifor j in range(i,len(myarr)):if myarr[j] < myarr[min_index]:min_index = j#交换list[i]与list[min_index]myarr[i], myarr[min_index] = myarr[min_index],myarr[i]return myarrif __name__ == "__main__":array = [randint(0, 1000) for i in range(0,1000)]timer = Timer('selectionsort1(array)','from __main__ import selectionsort1,array')print(timer.timeit(number=10))

• 借助魔法函数，实现运算符重载，类似于c++模板

可以比较任意对象，只要实现了魔法函数

from random import randint,choice from timeit import Timer from timeit import timeitclass Student():def __init__(self,name,age):self.name = nameself.age = agedef __lt__(self,other):return self.age < other.agedef __eq__(self,other):return self.age == other.agedef selectionsort1(myarr):for i in range(len(myarr)):#求子数组[i,n)中的最小值对应的indexmin_index = ifor j in range(i,len(myarr)):if myarr[j] < myarr[min_index]:min_index = j#交换list[i]与list[min_index]myarr[i], myarr[min_index] = myarr[min_index],myarr[i]return myarrif __name__ == "__main__":name_bank = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'array = [Student(choice(name_bank),randint(1,100)) for _ in range(1000)]timer = Timer('selectionsort1(array)','from __main__ import selectionsort1,array')print(timer.timeit(number=10))

__lt__ __gt__ __eq__ ,三个里面实现两个即可，剩余操作符的定义取余即可；当仅实现一个时，无法补全剩余运算符（但也合法）

• 重载时的改进：两个对象的大小关系不仅取决于年龄，还取决于姓名首字母

from random import randint,choice from timeit import Timer from timeit import timeitclass Student():def __init__(self,name,age):self.name = nameself.age = agedef __lt__(self,other):#小于的定义：年龄相同时还要比较首字母大小；年龄不同时以年龄为准return self.name < other.name if self.age == other.age else self.age < other.agedef __eq__(self,other):return self.age == other.agedef selectionsort1(myarr):for i in range(len(myarr)):#求子数组[i,n)中的最小值对应的indexmin_index = ifor j in range(i,len(myarr)):if myarr[j] < myarr[min_index]:min_index = j#交换list[i]与list[min_index]myarr[i], myarr[min_index] = myarr[min_index],myarr[i]print([(i.age,i.name) for i in myarr])if __name__ == "__main__":name_bank = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'array = [Student(choice(name_bank),randint(1,100)) for _ in range(1000)]timer = Timer('selectionsort1(array)','from __main__ import selectionsort1,array')print(timer.timeit(number=1))

结果符合预期，注意，必须在函数内print,因为timeit处于不同命名空间

三、排序算法练习常用辅助函数

from random import randint from time import timedef random_array(n, left, rught):return [randint(left,right) for _ in rnage(n)]def is_sorted(array):sorted = Truefor i in range(len(array)-1):if array[i] > array[i+1]:sorted = Falsebreakreturn sorteddef test_sort(sort_name, sort,array):start = time()sort(array)spend = time() - start#不正确时会抛出异常assert(is_sorted(array))print(sort_name + ' : '+ str(spend) + ' seconds')

总结

以上是生活随笔为你收集整理的选择排序及其优化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。