选择排序(Selection sort)是一种简单直观的比较排序算法。
算法原理:每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,知道全部待排序的数据元素排完。
Python代码1:
#Python算法--选择排序1
import random
def main(array):
num = len(array)
for i in range(num-1):
for j in range(i+1,num):
if array[i]>array[j]:
array[i],array[j]=array[j],array[i]
print('选择排序数组:',array)
if __name__ == '__main__':
array = []
for i in range(15):
array.append(random.randint(1,1000))
print('随机生成数组:',array)
main(array)
代码同前一篇的冒泡排序有些类似,但是数组元素的比较顺序确实完全不同,以数组的第一个元素开始,同其后的每一个元素分别做比较,一旦发现比自身小的元素,就就换二者的位置,直到最小的元素排在最前边。
执行效果:
代码1中,每次比较只要发现比自身元素小的元素就要交换位置,直至交换到最小的元素排到最前边,频繁的交换位置将影响到排序的效率,可以在每次比较发现比自身元素小的元素后,记录该元素为自小元素但不交换位置,然后与其他元素进行比较,直到记录的元素为最小元素后,再交换数组元素的位置,这要可提高程序的排序效率。(见代码2)
Python代码2:
#Python算法--选择排序2
import random
def main(array):
num = len(array)
for i in range(num-1):
min = i
for j in range(i+1,num):
if array[min]>array[j]:
min = j
array[i],array[min]=array[min],array[i]
print('选择排序数组:',array)
if __name__ == '__main__':
array = []
for i in range(15):
array.append(random.randint(1,1000))
print('随机生成数组:',array)
main(array)
代码2中借助变量min在每次比较后记录较小元素的位置,待一轮比较结束后,在进行元素位置的调换,提高排序效率。