选择排序是一种非常容易理解的算法。
假设有下面一组数据,需要从小到大升序排列。
选择排序的算法是
1. 创建一个列表或者数组
2. 第一次遍历数组,找出最小的一个数存放在新的数组中。
3. 第二次遍历数组,找出次小的数存放在新的数组。
4. 重复类似操作,直到所有的数据排列完成
def sort(srcArr):
dstArr = []
size = len(srcArr)
while len(dstArr) < size:
temp = srcArr[0]
tempindex = 0
for index in range(0,len(srcArr)):
if srcArr[index] < temp:
temp = srcArr[index]
tempindex = index
srcArr.pop(tempindex)
dstArr.append(temp)
return dstArr
if __name__ == "__main__":
arr = [3,2,8,4,1,6,5]
print("=======================")
print(arr)
result = sort(arr)
print("=======================")
print(result)
运行结果如下:
=======================
[3, 2, 8, 4, 1, 6, 5]
=======================
[1, 2, 3, 4, 5, 6, 8]
可以看到,排序结果正确。
用大 O 表示法,选择排序的时间复杂性度是 O(n2)O(n^2)O(n2).
一个列表有 n 个元素,遍历一次需要 n 次操作,所以一次遍历是 O(n)O(n)O(n).
选择排序要进行 n 次遍历,所以时间复杂性度就是 O(n∗n)O(n*n)O(n∗n)。
有同学可能会问,只有第一次遍历会访问 n 个元素,后面的遍历中,访问的元素数量一次减少,最后一次遍历时,只需要访问一个数据,那么为什么还是 O(n∗n)O(n*n)O(n∗n)?
如果严格按照数学公式,结果应该是
O(n+n−1+n−2+n−3+...+2+1)=O((n+1)∗n/2) O(n+n-1+n-2+n-3+...+2+1)=O((n+1)*n/2) O(n+n−1+n−2+n−3+...+2+1)=O((n+1)∗n/2)
但是,在大O 表示法中,常数项可以被省略,所以最终还是要用O(n2)O(n^2)O(n2)表示,这一结果表示选择排序并不快。