【21天学习经典算法】直接选择排序（附Python完整代码）

前言

博主一头小山猪目前已开放文章如下： 一文学懂经典算法系列之：顺序查找（附讲解视频）

一文学懂经典算法系列之：直接插入排序（附讲解视频）

一文学懂经典算法系列之：直接选择排序（附讲解视频）

活动地址：CSDN21天学习挑战赛

列表的分类与顺序查找

• 前言
• 概念
  • 直接选择排序
• 代码实现
• • 直接选择排序
• 参考资料

概念

直接选择排序

对于直接选择排序的数组，该数组大概率是无序的，若该数组是有序的（且该数组是用户的目标顺序），那么就不用通过算法来进行排序了。 直接选择排序的定义 通过比较最小值，得到每一个循环中的最小值的索引，并得到对应值后，将其与循环后的次位交换。 直接选择排序的工作方式 在原数组中选出序列中最小元素放在首位，依次从剩下的数组元素中选出最小元素放于次位，直至所有元素都选择完毕，排序结束。 伪代码 Straight_Select

1 for i = 1 to n - 1
2 		k = i
3		for j = i + 1 to n
4			if A[j] < A[k]
5				k = j
6		if k != i
7        	exchange A[i] with A[k]

伪代码解析 对于直接选择排序，本文将其伪代码过程命名为Straight_Select_Sorting，其中的参数是一个数组

，包含长度为

的要排序的一个序列。在Python代码中，

中元素的数目

来表示。该算法原址排序输入的数之后，算法在数组

中重排这些数，在任何时候，最多只有其中的常数个数字存储在数组外面。在过程Straight_Select结束时，输出数组

包含排序好的输出序列。

对于直接选择排序的个人理解 假设数组

中有

个元素，采用

函数在数组

找到最小的一个数，取出后与排序为首位的数字交换。那么此时原数组变为

，我们暂且不管原先排首位的数字去了哪里。称右侧的

为数组1，对右侧的

的数组即数组

再次进行上一步的操作，即采用

函数在数组

里找到最小的一个数，取出后与排序为首位的数字交换。注意，此时的数组

的首位是原数组的次位。如此往复循环，最终都将最小的一个数按次序排列下去。

代码实现

对于直接选择排序的代码实现，有两种方式可以实现，第一种在【21天学习经典算法】插入排序（附Python完整代码） 中Python代码实现插入排序的空数组排序已经实现，因此本文只讲述在原数组

中实现直接选择的排序的代码过程。

直接选择排序

沿用之前创建的数组

A = [41, 54, 95, 32, 11, 5, 7, 10, 21, 9, 85, 12, 13, 15, 64, 84]
for i in range(len(A)):
    # a是原数组的首位，b是不断缩小的数组中的最小值，c是不断缩小的数组中的最小值的索引值
    a, b, c = A[i], min(A[i:len(A)]), A.index(min(A[i:len(A)]))
    # 将原数组的首位数字与原数组的最小值进行交换
    A[i], A[c] = b, a
print(A)

以上就是个人在直接选择排序中的理解，如果错误之处，还望指正。

参考资料

1. 小山猪——经典算法专栏
2. 数据结构教程 第5版
3. 直接选择排序 - python实现