Python 排序算法入门指南158

在 Python 编程中，排序是一个基本的数据处理操作，用于将列表中的元素按特定顺序排列。Python 提供了多种内置的排序算法，每种算法都有自己的优缺点，适用于不同的场景。本文将介绍 Python 中常用的排序算法，包括它们的复杂度分析和代码示例。

1. 内置排序算法* sorted() 函数：最简单的排序方法，返回一个新的已排序列表，而不会改变原始列表。该函数使用归并排序算法，时间复杂度为 O(n log n)。
* () 方法：直接对列表进行原地排序，返回 None。它使用 Timsort 算法，该算法是对归并排序和插入排序的优化，时间复杂度为 O(n log n)。
* () 和 () 函数：使用堆排序算法，该算法通过构建二叉堆并不断弹出最小的元素来进行排序。时间复杂度为 O(n log n)。

2. 冒泡排序* 算法描述：反复比较相邻元素，如果顺序不正确，则交换它们。如此重复，直到没有更多交换需要进行。
* 时间复杂度：O(n^2)
```python
def bubble_sort(nums):
for i in range(len(nums)):
for j in range(0, len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
```

3. 选择排序* 算法描述：在剩余元素中找到最小的元素，并将其与当前未排序的第一个元素交换。重复此过程，直到所有元素都被排序。
* 时间复杂度：O(n^2)
```python
def selection_sort(nums):
for i in range(len(nums)):
min_idx = i
for j in range(i + 1, len(nums)):
if nums[min_idx] > nums[j]:
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i]
return nums
```

4. 插入排序* 算法描述：将元素逐个插入到已排序的子列表中，从第一个元素开始。将当前元素与已排序的子列表中的元素进行比较，并将其插入到正确的位置。
* 时间复杂度：O(n^2)
```python
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and key < nums[j]:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
return nums
```

5. 希尔排序* 算法描述：类似于插入排序，但使用步长来增加比较元素之间的距离。步长逐渐减小，直到达到 1，此时算法退化为插入排序。
* 时间复杂度：最好情况为 O(n)，平均情况为 O(n log^2 n)，最坏情况为 O(n^2)
```python
def shell_sort(nums):
gap = len(nums) // 2
while gap > 0:
for i in range(gap, len(nums)):
temp = nums[i]
j = i
while j >= gap and nums[j - gap] > temp:
nums[j] = nums[j - gap]
j -= gap
nums[j] = temp
gap //= 2
return nums
```

6. 快速排序* 算法描述：使用分治策略。选择一个枢纽元素，将列表划分为比枢纽元素小和大的两个子列表。递归地对子列表进行快速排序，然后将排序后的子列表连接起来。
* 时间复杂度：平均情况为 O(n log n)，最坏情况为 O(n^2)
```python
def quicksort(nums):
if len(nums) pivot]
return quicksort(left) + middle + quicksort(right)
```

7. 归并排序* 算法描述：同样使用分治策略。将列表分为两个子列表，递归地对子列表进行归并排序，然后通过合并两个排序后的子列表得到最终的排序列表。
* 时间复杂度：O(n log n)
```python
def merge_sort(nums):
if len(nums)

2025-02-02

上一篇：iPhone 编程学习 Python 指南

下一篇：Python编程入门：如何上手Python？