DSA 选择排序

选择排序

选择排序算法查找数组中的最小值，并将其移到数组的前面。

该算法一遍又一遍地查找数组，将下一个最小值移到前面，直到数组被排序。

继续阅读，以完全理解选择排序算法以及如何自己实现它。

手动演练

在用编程语言实现选择排序算法之前，让我们只进行一次手动遍历一个短数组，以获得一些想法。

步骤 1：我们从一个未排序的数组开始。

步骤 2：逐个遍历数组。哪个值是最小的？ 3，对吗？

步骤 3：将最小值 3 移到数组的前面。

步骤 4：查看剩余的值，从 7 开始。 7 是最小的值，并且已经放在了数组的前面，所以我们不需要移动它。

步骤 5：查看数组的其余部分：12、9 和 11。 9 是最小值。

步骤 6：将 9 移到前面。

步骤 7：查看 12 和 11，11 是最小的。

步骤 8：将其移到前面。

最后，数组已排序。

运行下面的模拟，以动画形式查看以上步骤。

手动运行：发生了什么？

我们必须理解上面发生了什么，才能完全理解该算法，以便用编程语言实现该算法。

您能看出最小值 3 发生了什么吗？在步骤 3 中，它已被移到数组的开头，这是它应在的位置，但在该步骤中，数组的其余部分仍未排序。

因此，选择排序算法必须一遍又一遍地遍历数组，每次都将下一个最小值移到未排序部分的前面，移到其正确的位置。排序一直进行到最大值 12 留在数组末尾。这意味着我们需要遍历数组 4 次，以对 5 个值的数组进行排序。

每次算法遍历数组时，数组中剩余的未排序部分都会变短。

现在，我们将使用我们学到的知识来实现编程语言中的选择排序算法。

选择排序实现

要在编程语言中实现选择排序算法，我们需要

1. 一个包含待排序值的数组。
2. 一个内循环，遍历数组，找到最小值，并将其移到数组的前面。此循环每次运行时必须少循环一个值。
3. 一个外循环，控制内循环需要运行多少次。对于具有 \(n\) 个值的数组，此外循环必须运行 \(n-1\) 次。

生成的代码如下：

my_array = [64, 34, 25, 5, 22, 11, 90, 12]

n = len(my_array)
for i in range(n-1):
    min_index = i
    for j in range(i+1, n):
        if my_array[j] < my_array[min_index]:
            min_index = j
    min_value = my_array.pop(min_index)
    my_array.insert(i, min_value)

print("Sorted array:", my_array)

选择排序移动问题

选择排序算法可以进一步改进。

在上面的代码中，移除了最小值的元素，然后将其插入到数组的前面。

每次删除下一个最小值的数组元素时，所有后续元素都必须向下移动一个位置以弥补删除。

这些移动操作花费了大量时间，而且我们还没有完成！找到并移除了最小值（5）之后，将其插入到数组的开头，导致所有后续值移动一个位置以腾出新值空间，如下图所示。

解决方案：交换值！

而不是所有的移动，而是像下图所示那样，将最小值（5）与第一个值（64）进行交换。

我们可以像上图所示那样交换值，因为最小值最终会到达正确的位置，而我们与之交换的其他值的位置并不重要，因为它还没有排序。

这是一个模拟，显示了这种改进的选择排序如何通过交换工作

这是改进的选择排序的实现，使用了交换

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n):
    min_index = i
    for j in range(i+1, n):
        if my_array[j] < my_array[min_index]:
            min_index = j   
    my_array[i], my_array[min_index] = my_array[min_index], my_array[i]

print("Sorted array:", my_array)

选择排序时间复杂度

有关时间复杂度的一般性解释，请访问此页面。

有关选择排序时间复杂度的更全面、更详细的解释，请访问此页面。

选择排序对 \(n\) 个值的数组进行排序。

平均而言，大约 \(\frac{n}{2}\) 个元素需要进行比较才能在每次循环中找到最小值。

并且选择排序大约需要运行 \(n\) 次循环来查找最小值。

我们得到时间复杂度

\[ O( \frac{n}{2} \cdot n) = \underline{\underline{O(n^2)}} \]

选择排序算法的时间复杂度可以在图表中显示如下

正如您所见，运行时间与冒泡排序相同：当数组大小增加时，运行时间增加得非常快。

为不同大小的数组运行下面的模拟。

红色虚线代表理论时间复杂度 \(O(n^2)\)。

蓝色十字出现在您运行模拟时。蓝色十字显示了对给定大小的数组进行排序所需的运算次数。

与冒泡排序相比，我们在此模拟中注意到的最显著的区别是，对于选择排序，最佳情况和最坏情况实际上几乎相同（\(O(n^2)\)），但对于冒泡排序，最佳情况的运行时间仅为 \(O(n)\)。

选择排序的最佳情况和最坏情况之间的差异主要是交换次数。在最佳情况下，选择排序不必交换任何值，因为数组已经排序。而在最坏情况下，数组已经排序，但顺序错误，因此选择排序必须进行与数组中值一样多的交换。