Python中的排序算法

排序是指以特定顺序排列数据的过程。数据（通常是数值）被组织起来，涉及按升序或降序排列算法。它是一种更合理地表示数据的方法。它是软件工程中一个至关重要的部分。如果我们用来排序数据的方法效率低下，那么对大量数据进行排序可能需要大量的计算资源。算法的效率与它所处理的项目的数量成正比。复杂的排序方法对于少量数据来说可能得不偿失。另一方面，我们的目标是最大化大量数据的效率和速度。将讨论各种排序方法，并分析其时间复杂度。

以下是一些排序的实际应用示例：

• 电话簿：这本书列出了人们的姓名、电话号码和地址。
• 字典：这是一个包含按字母顺序组织的单词及其定义的庞大数据库。
• 联系人列表：联系人列表是手机上每个人的联系信息的按字母顺序排列的列表。

在介绍用于排序数据的各种方法之前，我们应该考虑可能用于评估排序过程的任务。需要一种有组织的方法来比较值，以确定它们是否都已排序。首先，我们应该比较值，以确定哪个更小，哪个更大，以便可以将它们按顺序排列。

排序的各种变体包括：

• 升序：当后面的每个元素都大于前面的元素时，一组值被认为是升序。例如：1、2、3、4、5。这里是按升序排列的序列。
• 降序：当一组值中的一个元素总是小于它前面的元素时，这些值被认为是降序。例如：5、4、3、2、1。这里，列表的顺序是降序的。
• 非递增顺序：如果一个值序列中的每个 i-th 元素大于或等于其 (i-1)-th 元素，则这些值被认为是“非递增顺序”。当存在重复数字时，它们会出现在此序列中，例如：1、2、2、3、4、5。此处，2 重复了两次。
• 非递减顺序：如果一个值序列中的每个 i-th 元素小于或等于其 (i-1)-th 元素，则该值集被认为是“非递减顺序”。当存在重复数字时，它们会出现在此序列中。例如：5、4、3、2、1 等。此处，2 重复了两次。

排序技术

Python 实现的各种排序方法包括：

• 冒泡排序
• 选择排序
• 插入排序

冒泡排序

冒泡排序是一种直接的排序算法。这种排序技术反复检查两个相邻元素的位置，如果需要则交换它们。它也称为沉降排序。在平均和最坏情况下，其时间复杂度为 O(n²)，而在最佳情况下为 O(n)。在数组中，冒泡排序中的元素可以通过相互交换位置来自己排序，以便它们都可以按升序排列其级别。

换句话说，我们比较两个相邻的元素，以确定它们的顺序是否不正确，如果不正确，我们就交换它们。如果数组要按升序排列，那么 arr[i] > arr[j]，反之亦然，其中 s 是数组的大小。

示例

在这里，我们使用冒泡排序来排序以下列表。

序列：5、18、3、14

第一次迭代

(5,18,3,14) -> (5,18,3,14)，前两个元素在此处进行比较，但由于它们已按升序排列，因此保持不变。

(5,18,3,14) -> (5,3,18,14)。此处，第二和第三个元素按升序比较并交换（10 小于 23）。

(5,18,3,14) -> (5,3,14,18)。此处，第三和第四个元素按升序比较并交换（1 小于 23）。

第一轮迭代后，最大且已正确排序的元素位于最右边的位置。

第二次迭代

(5,3,14,18) -> (5,3,14,18)。再次，由于它们已按升序排列，因此比较前两个元素并保持不变。

第一轮迭代后，其余元素已排序。第二轮迭代后，给定数组按升序排序。因此，最终结果是 3、5、14、18。

第三次迭代

(3,5,14,18) -> (3,5,14,19)。在此情况下，前两个元素按升序比较并交换。

第一轮和第二轮迭代已对剩余元素进行了排序。第三轮迭代后，给定的数组按升序排序。结果是 3,5,14,18。

冒泡排序实现

输出

Sorted array is:
3
5
14
18

• 时间复杂度：O(n^2)
• 辅助空间： O(1)

选择排序

这种排序方法重复查找最小元素并按升序排列。冒泡排序不需要额外的 RAM。在此方法执行期间，维护两个子数组，一个子数组已排序，另一个子数组未排序。每次选择排序迭代时，将未排序子数组中的最小成员放入已排序子数组中。选择排序比冒泡排序更有效。排序的平均、最坏和最佳情况时间复杂度均为 O(n²)。

示例

在这里，我们使用选择排序来排序以下序列。

序列：9、4、3、8

(9, 4, 3, 8) -> (3, 9, 4, 8)，在第一次遍历中找到最小元素 3，并将其放在首位。

(3, 9, 4, 8) -> (3, 4, 9, 8)，在第二次遍历中找到第二小的元素 4，并将其分配给第二个位置。

(3, 4, 9, 8) -> (3, 4, 8, 9)，在第三次遍历中找到下一个最小元素 8，并将其放在第三个位置。

上述迭代后，最终数组按排序顺序排列，即 3、4、8、9。

代码

输出

Sorted Array in Ascending Order is :
[3, 4, 8, 9]

• 时间复杂度：O(n^2)
• 辅助空间： O(1)

插入排序

这种排序方法始终维护一个已排序的子数组。将数组未排序部分的值正确地放置在已排序部分中。与冒泡排序或选择排序等算法相比，它在实践中更有效。插入排序的平均和最坏情况时间复杂度为 O(n²)，而最佳情况时间复杂度为 O(n)。

示例

在这里，我们使用插入排序来排序以下序列。

序列：7、2、1、6

(7, 2, 1, 6) -> (2, 7, 1, 6)，第一次迭代比较前两个元素；在这种情况下，2 小于 7，因此将 2 放在 7 前面。

(2, 7, 1, 6) -> (2, 1, 7, 6)，第二次迭代比较第二个和第三个元素；在这种情况下，1 小于 7，将 1 放在 7 前面。

(2, 1, 7, 6) -> (1, 2, 7, 6)。由于第二次重复后元素 (1, 7) 不按升序排列，因此将它们放在前面。因此，将 1 放在 2 前面。

(1, 2, 7, 6) -> (1, 2, 6, 7)，在本次循环中交换所有前面的元素后，将比较并交换最后两个元素。

插入排序实现

输出

The unsorted list is: [7, 2, 1, 6]
The sorted new list is: [1, 2, 6, 7]

• 时间复杂度：O(n^2)
• 辅助空间： O(1)