前面我们已经一起学习了冒泡排序(Python 实现经典算法之冒泡排序),这篇文章,大家与好奇心就一起再来看看选择排序吧。
选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾(这里注意,是已排序好的末尾,不是数组末尾!)。以此类推,直到全部待排序的数据元素的个数为零。可以理解为 一个 0 到 n-1 的迭代,每次向后查找选择一个最小的元素。选择排序是不稳定的排序方法。
###
# author: 今日头条:技术好奇心
###
# 选择排序例子
def selection_sort(arr):
# 按数组总长度来,依次遍历
for i in range(len(arr) - 1):
# 存储最小下标值(这里默认假设数组第一个为最小值)
min_index = i
# 以 j 为下标,i+1为起始位置,再次对数组进行遍历
# (因为之前的以及是最小值排序好了,所以起始为i+1)
for j in range(i + 1, len(arr)):
# 如果这个数小于之前记录的最小数,则更新最小数的下标
if arr[j] < arr[min_index]:
min_index = j
# 将 i 位置的数(前面已排序序列的末尾的数)和最小数进行交换
arr[i], arr[min_index] = arr[min_index], arr[i]
# 这里为了方便大家对比参考,所以每次比较完了就打印一次
print(arr)
# 执行
if __name__ == '__main__':
# 建立演示数组
arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
# 执行排序方法
selection_sort(arr)
# 看看比较完之后数组的样子
print('-------------------- 技术好奇心 -------------------')
print(arr)
运行结果:
[2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
-------------------- 技术好奇心 -------------------
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
从上面的结果来看,排序是成功的。
里面为了方便大家观看对比,我将每次的执行结果也打印出来了。
从过程中可以看出,排序是从数组第一个开始的,然后逐渐通过遍历比较往后替换排序。