选择排序算法 Python Code 例如：
陈莎拉
什么是选择排序？
选择排序 是一种比较排序算法，用于按升序对随机项目列表进行排序。比较不需要很多额外空间。它只需要一个额外的内存空间用于时间变量。
这被称为 到位 排序。选择排序的时间复杂度为 O(n2) 其中 n 是列表中的项目总数。时间复杂度衡量对列表进行排序所需的迭代次数。列表分为两个部分：第一个列表包含已排序的项目，而第二个列表包含未排序的项目。
默认情况下，排序列表为空，未排序列表包含所有元素。然后扫描未排序列表以查找最小值，并将其放入排序列表中。重复此过程，直到所有值都已比较和排序。
选择排序如何工作？
将未排序分区中的第一个项与右侧的所有值进行比较，以检查它是否是最小值。 如果不是最小值，则将其位置与最小值交换。
例如：
- 例如，如果最小值的索引是 3，则索引为 3 的元素的值将放置在索引 0 处，而索引为 0 处的值将放置在索引 3 处。如果未排序分区中的第一个元素是最小值，则返回其位置。
- 然后将确定为最小值的元素移动到左侧的分区，即排序列表。
- 分区侧现在有一个元素，而未分区侧有 (n – 1) 个元素，其中 n 是列表中元素的总数。这个过程不断重复，直到所有项目都已根据其值进行比较和排序。
问题定义
需要将一个随机顺序的元素列表按升序排序。请考虑以下列表作为示例。
[21,6,9,33,3]
上述列表应按以下结果进行排序
[3,6,9,21,33]
解决方案（算法）
步骤1） 获取 n 的值，即数组的总大小
步骤2） 将列表划分为已排序和未排序部分。已排序部分最初为空，而未排序部分包含整个列表
步骤3） 从未分区部分中选取最小值并将其放入已排序部分中。
步骤4） 重复该过程 (n – 1) 次，直到列表中的所有元素都已排序。
视觉表现
给定一个包含五个元素的列表，下图说明了选择排序算法在对它们进行排序时如何迭代这些值。
下图显示了未排序的列表
步骤1）
将第一个值 21 与其余值进行比较，以检查它是否是最小值。
3 是最小值，因此 21 和 3 的位置互换。绿色背景的值表示列表的排序分区。
步骤2）
将未排序分区中的第一个元素 6 与其余值进行比较，以找出是否存在较低的值
值 6 是最小值，因此它保持其位置。
步骤3）
将未排序列表中第一个元素的值为 9 与其余值进行比较，以检查它是否是最小值。
值 9 是最小值，因此它在排序分区中保持其位置。
步骤4）
将值 33 与其余值进行比较。
值 21 低于 33，因此交换位置以产生上述新列表。
步骤5）
未分区列表中只剩下一个值。因此，它已经排序了。
最终列表如上图所示。
选择排序程序使用 Python 3
以下代码显示了使用选择排序实现 Python 3
def selectionSort( itemsList ): n = len( itemsList ) for i in range( n - 1 ): minValueIndex = i for j in range( i + 1, n ): if itemsList[j] < itemsList[minValueIndex] : minValueIndex = j if minValueIndex != i : temp = itemsList[i] itemsList[i] = itemsList[minValueIndex] itemsList[minValueIndex] = temp return itemsList el = [21,6,9,33,3] print(selectionSort(el))
运行上述代码产生以下结果
[3, 6, 9, 21, 33]
Code 说明
代码解释如下
这是 Code 解释：
- 定义一个名为selectionSort的函数
- 获取列表中元素的总数。我们需要它来确定比较值时要进行的传递次数。
- 外循环。使用循环迭代列表的值。迭代次数为 (n – 1)。n 的值为 5，因此 (5 – 1) 得出 4。这意味着外迭代将执行 4 次。在每次迭代中，变量 i 的值都会分配给变量 minValueIndex
- 内循环。使用循环将最左侧的值与右侧的其他值进行比较。但是，j 的值不是从索引 0 开始的。它从 (i + 1) 开始。这排除了已排序的值，因此我们专注于尚未排序的项目。
- 在未排序的列表中找到最小值并将其放置在适当的位置
- 交换时更新 minValueIndex 的值ping 条件为真
- 比较索引号 minValueIndex 和 i 的值，看它们是否不相等
- 最左边的值存储在时间变量中
- 右侧较低的值占据第一个位置
- 临时值中存储的值存储在先前最小值所占的位置
- 返回排序后的列表作为函数结果
- 创建一个包含随机数的列表 el
- 调用选择排序函数并传入 el 作为参数后打印排序后的列表。
选择排序的时间复杂度
排序复杂度用于表示对列表进行排序所需的执行次数。该实现有两个循环。
外循环从列表中逐个选择值，执行 n 次，其中 n 是列表中值的总数。
内循环将外循环的值与其余值进行比较，也执行 n 次，其中 n 是列表中元素的总数。
因此执行次数为（n*n），也可以表示为O(n2).
选择排序有三类复杂性，即：
- 最糟糕的情况 – 这是提供的列表按降序排列的地方。该算法执行的最大执行次数表示为 [Big-O] O(n2)
- 最好的情况 – 当提供的列表已经排序时，就会发生这种情况。该算法执行的最小执行次数表示为 [大Ω] Ω(n)。2)
- 平均情况 – 当列表顺序随机时，就会发生这种情况。平均复杂度表示为 [Big-theta] Θ(n2)
选择排序的空间复杂度为 O(1)，因为它只需要一个用于交换的时间变量。ping 值。
何时使用选择排序？
当您想要执行以下操作时，最好使用选择排序：
- 你必须按升序对一小串项目进行排序
- 当交换成本ping 数值微不足道
- 当您需要确保列表中的所有值都已被检查时也会使用它。
选择排序的优点
以下是选择排序的优点
- 它在小列表上表现非常好
- 这是一种就地算法。排序不需要太多空间。只需要一个额外的空间来保存时间变量。
- 它对已经排序的项目表现良好。
选择排序的缺点
以下是选择排序的缺点。
- 处理大型列表时其性能很差。
- 排序过程中进行的迭代次数是 n 平方，其中 n 是列表中元素的总数。
- 其他算法，例如快速排序，与选择排序相比具有更好的性能。
