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)\)。

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