选择排序：算法解释 Python 代码示例

什么是选择排序？

选择排序 是一种比较排序算法，用于按升序对随机项目列表进行排序。比较不需要很多额外空间。它只需要一个额外的内存空间用于时间变量。

这被称为到位排序。选择排序的时间复杂度为 O(n²) 其中 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]

代码说明

代码解释如下

以下是代码解释：

定义一个名为selectionSort的函数
获取列表中元素的总数。我们需要它来确定比较值时要进行的传递次数。
外循环。使用循环迭代列表的值。迭代次数为 (n – 1)。n 的值为 5，因此 (5 – 1) 得出 4。这意味着外迭代将执行 4 次。在每次迭代中，变量 i 的值都会分配给变量 minValueIndex
内循环。使用循环将最左侧的值与右侧的其他值进行比较。但是，j 的值不是从索引 0 开始的。它从 (i + 1) 开始。这排除了已排序的值，因此我们专注于尚未排序的项目。
在未排序的列表中找到最小值并将其放置在适当的位置
当交换条件为真时更新 minValueIndex 的值
比较索引号 minValueIndex 和 i 的值，看它们是否不相等
最左边的值存储在时间变量中
右侧较低的值占据第一个位置
临时值中存储的值存储在先前最小值所占的位置
返回排序后的列表作为函数结果
创建一个包含随机数的列表 el
调用选择排序函数并传入 el 作为参数后打印排序后的列表。

选择排序的时间复杂度

排序复杂度用于表示对列表进行排序所需的执行次数。该实现有两个循环。

外循环从列表中逐个选择值，执行 n 次，其中 n 是列表中值的总数。

内循环将外循环的值与其余值进行比较，也执行 n 次，其中 n 是列表中元素的总数。

因此执行次数为（n*n），也可以表示为O(n²).

选择排序有三类复杂性，即：

最糟糕的情况 – 这是提供的列表按降序排列的地方。该算法执行的最大执行次数表示为 [Big-O] O(n²)
最好的情况 – 当提供的列表已经排序时，会发生这种情况。该算法执行的执行次数最少，表示为 [Big-Omega] ?(n²)
平均情况 – 当列表按随机顺序排列时，会发生这种情况。平均复杂度表示为 [Big-theta] ?(n²)

选择排序的空间复杂度为 O(1)，因为它需要一个用于交换值的时间变量。

何时使用选择排序？

当您想要执行以下操作时，最好使用选择排序：

你必须按升序对一小串项目进行排序
当交换价值的成本微不足道时
当您需要确保列表中的所有值都已被检查时也会使用它。

选择排序的优点

以下是选择排序的优点

它在小列表上表现非常好
这是一种就地算法。排序不需要太多空间。只需要一个额外的空间来保存时间变量。
它对已经排序的项目表现良好。

选择排序的缺点

以下是选择排序的缺点。

处理大型列表时其性能很差。
排序过程中进行的迭代次数是 n 平方，其中 n 是列表中元素的总数。
其他算法，例如快速排序，与选择排序相比具有更好的性能。

总结

选择排序是一种就地比较算法，用于将随机列表排序为有序列表。它的时间复杂度为 O(n²)
该列表分为两个部分：已排序部分和未排序部分。从未排序部分中选取最小值，并将其放入已排序部分。
重复此过程，直到所有项目都已排序。
实现伪代码 Python 3 涉及使用两个 for 循环和 if 语句来检查是否需要交换
时间复杂度衡量对列表进行排序所需的步骤数。
最坏情况的时间复杂度发生在列表按降序排列时。它的时间复杂度为 [Big-O] O(n²)
最佳时间复杂度发生在列表已经按升序排列时。它的时间复杂度为 [Big-Omega] ?(n²)
平均时间复杂度发生在列表按随机顺序排列时。它的时间复杂度为 [Big-theta] ?(n²)
当您需要排序的项目列表很少、交换值的成本无关紧要且必须检查所有值时，最好使用选择排序。
选择排序在大型列表上表现不佳
与选择排序相比，其他排序算法（例如快速排序）具有更好的性能。

你可能会喜欢：