Python中的选择排序

在本教程中，我们将用 Python 实现选择排序算法。这是一个相当直接的算法，它使用了较少的交换操作。

在这个算法中，我们在每次遍历时从未排序的数组中选择最小的元素，并将其与未排序数组的开头交换。这个过程将持续进行，直到所有元素都放好。它是一种简单且原地进行的比较排序算法。

选择排序的工作原理

以下步骤解释了 Python 中选择排序的工作原理。

让我们取一个未排序的数组来应用选择排序算法。

[30, 10, 12, 8, 15, 1]

步骤 1：获取数组的长度。

length = len(array) → 6

步骤 2：首先，我们将第一个元素设置为最小元素。

步骤 3：现在将最小值与第二个元素进行比较。如果第二个元素小于第一个，则将其设置为最小值。

再次将第二个元素与第三个元素进行比较，如果第三个元素小于第二个，则将其设置为最小值。这个过程将一直进行，直到找到最后一个元素。

步骤 4：每次迭代后，最小值都会与未排序数组的开头进行交换。

步骤 5：第二步到第三步会重复进行，直到得到排序后的数组。

选择排序算法

选择排序算法如下。

算法

Python 选择排序程序

以下代码片段展示了使用 Python 实现的选择排序算法。

代码 -

输出

The sorted array is:  [3, 6, 9, 21, 33]

解释 -

让我们来理解上面的代码 -

• 首先，我们定义了 selection_sort() 函数，该函数接受一个数组作为参数。
• 在函数中，我们获取数组的长度，该长度用于确定进行值比较的遍历次数。
• 正如我们所见，我们使用了两个循环 - 外循环和内循环。外循环用于遍历列表中的值。此循环将从 0 迭代到 (length-1)。因此，第一次迭代将执行 (5-1) 或 4 次。在每次迭代中，变量 i 的值将被赋给变量
• 内循环用于将右侧每个元素的值与左侧元素上的另一个值进行比较。因此，第二个循环从 i+1 开始迭代。它只会选取未排序的值。
• 在未排序的列表中找到最小元素并更新 minIndex 位置。
• 将该值放在数组的开头。
• 一旦迭代完成，将返回排序后的数组。
• 最后，我们创建一个未排序的数组并将其传递给 selection_sort()。它会打印排序后的数组。

选择排序的时间复杂度

时间复杂度是算法排序所需时间的一个重要指标。在选择排序中，有两个循环。外循环运行 n 次（n 是元素的总数）。

内循环也执行 n 次。它将其余值与外循环值进行比较。因此，执行次数为 n*n 次。因此，归并排序算法的时间复杂度为 O(n²)。

时间复杂度可以分为三个类别。