介绍

排序虽然是一项基本操作，但却是计算机应执行的最重要的操作之一。它是许多其他算法和过程(例如搜索和合并)的基础。了解不同的排序算法可以帮助您更好地理解不同算法背后的思想，并帮助您提出更好的算法。

在选择排序算法排序通过找到未排序部分的最小值，然后与所述第一未排序的元件交换它的阵列。它是就地算法，这意味着您不需要分配其他列表。尽管速度很慢，但在内存有限的系统中，它仍被用作主要的排序算法。

在本文中，我们将解释选择排序的工作原理并在Python中实现它。然后，我们将分解算法的动作，以了解其时间复杂度。

选择排序

那么选择排序如何工作？选择排序将输入列表分为两部分，已排序的部分最初为空，未排序的部分最初包含所有元素的列表。该算法然后选择所有未排序文件的最小值，并将其与第一个未排序值交换，然后将排序部分增加一个。

此类的高级实现如下所示：

在上面的伪代码中，argmin()是一个返回最小值索引的函数。该算法使用变量i来跟踪已排序列表的结束位置和未排序列表的开始位置。由于我们从没有排序的项目开始并取最小值，因此，总是存在未排序部分的每个成员大于已排序部分的任何成员的情况。

第一行增加的值i，第二行找到最小值的索引，第三行交换这些值。交换之所以有效，是因为Python在将任何内容分配给左侧之前先计算了右侧，因此我们不需要任何临时变量。

让我们来看看它是如何工作的行动，包含以下元素的列表：[3, 5, 1, 2, 4]。

我们从未排序的列表开始：

3 5 1 2 4

未排序的部分包含所有元素。我们仔细检查每个项目，并确定这1是最小的元素。所以，我们换1用3：

15 3 2 4

在其余未排序的元素中[5, 3, 2, 4]，2是最低的数字。现在2，我们交换5：

1 23 5 4

此过程将继续进行，直到对列表进行排序：

1 2 35 4

1 2 3 45

1 2 3 4 5

让我们看看如何在Python中实现它！

实现

实现此算法的技巧是跟踪最小值并交换列表的两个元素。sort.py在您最喜欢的编辑器中打开一个名为的文件，然后在其中输入以下代码：

现在，将一些代码添加到文件中以测试算法：

然后，您可以打开一个终端并运行以查看结果：

该列表已正确排序！我们知道它是如何工作的，并且可以在Python中实现选择排序。让我们进入一些理论，看看它在时间方面的表现。

时间复杂度计算

那么，选择排序对列表进行排序需要多长时间？给定一个size数组，我们将采用一种方法并精确计算选择排序算法所花费的时间n。代码的第一行是：

这行不应该花费太多，因为它只是设置函数堆栈。我们说这是一个常数-输入的大小不会改变此代码运行的时间。假设c1执行此行代码需要执行操作。接下来，我们有：

这个有点棘手。首先，我们有两个函数调用len()和range()，它们在for循环开始之前执行。len()CPython 的成本也与CPython的大小无关，CPython是Windows，Linux和Mac上的默认Python实现。的初始化也是如此range()。让我们把这两个叫做c2。

接下来，我们有for，即运行n - 1时间。这不是一个常数，输入的大小确实会影响执行的时间。因此，我们必须将完成一个循环所需的时间乘以n - 1。

可以in说，评估运营商的成本是恒定的c3。这涵盖了外部for循环。

变量分配也可以在恒定时间内完成。我们称这个为c4：

现在，我们遇到内部for循环。它具有两个常量函数调用。假设他们采取c5行动。

请注意，c5它与有所不同c2，因为range这里有两个参数，并且这里要执行加法运算。

到目前为止，我们已经有了c1 + c2 + (n - 1) * (c3 + c4 + c5)操作，然后我们的内循环开始，将所有内容乘以…？好吧，这很棘手，但是如果仔细观察，它会n - 2在第一个循环中花费时间，n - 3在第二个循环中花费时间，最后一次则花费1。

我们需要将所有内容乘以1到之间的所有数字的总和n - 2。数学家告诉我们，总和为(n - 2) * (n - 1) / 2。随时x在这里阅读有关1和任何正数之间的整数之和的更多信息。

内循环的内容也将在固定时间内完成。让我们把它需要的Python做的时候in，if，赋值语句和变量交换占用的任意固定时间c6。

大家一起得到c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2。

我们可以简化这个到：a * n * n + b * n + c，其中a，b和c代表评估常量的值。

这称为O(n2)。那是什么意思？总而言之，我们算法的性能基于输入列表的平方大小。因此，如果我们将列表大小加倍，则将其排序所需的时间将乘以4！如果我们将输入的大小除以3，则时间将减少9！

结论

在本文中，我们研究了选择排序的工作原理并在Python中实现了它。然后，我们逐行分解代码以分析算法的时间复杂度。

0

相关文章:Python中的语句、缩进和注释 语句 用源代码编写的用于执行的指令称为语句。Python编程语言中有不同类型的语句，例如Assignment语 […]...

在C / C++，Python，PHP和Java中交换两个变量 如何在不使用库函数的情况下交换两个变量？ Python：在Python中，有一个简单且语法简洁的结构来交换变量 […]...

Python中的生成器Generator 先决条件: 迭代器 我们讨论生成器时涉及两个术语。 Generator-Function： generator […]...

使用Python中的元类进行元编程 元编程看起来很时髦，但如果你曾经合作过的装饰器或元类，你其实做过元编程。简而言之，我们可以说元编程是操纵代码的 […]...

使用Python进行鼠标和键盘自动化 本文说明了如何使用Python中的pyautogui模块自动执行鼠标和键盘的移动。该模块未预装Python。因 […]...

用Python导入模块 Python中的导入类似于C/C++中的#include header_file。通过使用import导入文件 […]...

Numpy中的N维数组 ndarray Numpy中的N维数组(ndarray) Numpy中的Array是元素表(通常是数字)，所有元素都是相同类型 […]...

线性回归(Python实现) 本文讨论了线性回归的基础知识及其在Python编程语言中的实现。 线性回归是一种统计方法，用于对因变量与给定的 […]...