排序
快速排序¶
核心的相似思想:分而治之¶
首先,这三种方案都服务于快速排序的同一个宏伟蓝图——“分而治之” (Divide and Conquer)。它们是“分”这个步骤的具体执行者。它们的共同使命是:
- 选择一个基准 (Pivot):在数组中选定一个“标杆”元素。
- 执行分区 (Partition):以基准为中心,重新排列数组。
- 创建子问题 (Create Subproblems):分区完成后,原始的大问题就变成了两个或多个更小的、可以独立解决的子问题。
它们的根本区别,在于如何执行分区,以及分区后产生了什么样的子问题。
三种方案的深度剖析与对比¶
1. Lomuto 方案:单向构建者¶
核心思想:可以想象成一个“构建者”或“扫雪车”。它从数组的一头开始,维护一个“已确认的小于基准的区域”。然后,它一路扫描过去,一旦发现新的“小元素”,就把它扔进这个区域并扩大区域的边界。这是一种单向、扩张式的分区思想。
应用场景:
- 教学与理解:它的逻辑最简单、最直观,是理解快速排序分区思想的最佳入门方案。
- 简单实现:在对性能要求不是极致,但要求代码清晰、不易出错的场合,它是一个不错的选择。
思想上的优缺点:
- 优点:思路清晰,一步一步地构建“小于区”,非常稳健。分区结束后,基准元素的位置被唯一确定下来。
- 缺点:思想略显“僵硬”。它对等于基准的元素处理不佳,会将它们与大于基准的元素混在一起,在有大量重复元素时,这会导致分区严重不平衡。
2. Hoare 方案 (双路快排):双向协作者¶
核心思想:可以想象成两个“相向而行的工人”。一个从左边出发,寻找“不该在左边”的元素(即大元素);另一个从右边出发,寻找“不该在右边”的元素(即小元素)。一旦两人都找到了目标,就把这两个元素交换位置。这是一种双向、协作式的分区思想。
应用场景:
- 通用高性能排序:在不确定数据分布,尤其是重复元素不极端的情况下,Hoare 方案通常是性能最高的。它的交换次数更少,实际运行速度最快。
- 标准库实现:很多语言和库中的快速排序实现都基于 Hoare 方案的思想。
思想上的优缺点:
- 优点:非常高效。通过双向查找,它能更快地将数组整理成两个大致平衡的部分。对于等于基准的元素,它能自然地将它们分散在两个分区中,表现比 Lomuto 稳定。
- 缺点:思想更精妙,但也更复杂。分区结束后,基准元素本身不一定在最终分割点上,只是保证了分割点左右两边元素的相对大小关系,这给递归的边界处理带来了一些需要注意的细节。
3. 三路快排:精准分类器¶
核心思想:它认为世界不只是“大”和“小”二元对立的,还有“相等”这一重要状态。它的思想是“精准分类”。它不像前两者那样只找一个分割点,而是试图找到两个分割点,从而将数组完美地划分为“小于”、“等于”、“大于”三个区域。
应用场景:
- 处理大量重复元素:这是它的“杀手锏”应用。当数组中只有少数几种不同的值时(例如,排序一个只包含0, 1, 2三种数字的数组),三路快排的性能会远超前两者。
- 特定数据结构:在某些场景,如排序字符串或复杂对象时,判断“相等”的成本较低,利用这一点可以获得很好的优化。
思想上的优缺点:
- 优点:思想最精细,直击重复元素这个痛点。通过一次性把所有“等于”基准的元素“请出”后续的排序过程,极大地减少了递归的规模,从根本上避免了因重复元素导致的最坏情况。
- 缺点:思想最复杂。对于一个几乎没有重复元素的数组,它为了维护三个区域而做的额外判断和指针操作,可能会带来微小的性能开销,使其略慢于精简的 Hoare 方案。
时间复杂度分析¶
| 方案 | 平均情况 | 最坏情况 | 最坏情况说明 |
|---|---|---|---|
| Lomuto | O(n log n) | O(n²) | 由有序数组或大量重复元素触发。 |
| Hoare | O(n log n) | O(n²) | 由有序数组触发,但对重复元素的处理比Lomuto好。 |
| 三路快排 | O(n log n) | O(n) | 在只有常数个不同值的数组中,复杂度接近线性O(n)。其 O(n²) 最坏情况仅由传统有序数组触发。 |
关键点:所有方案都依赖随机化基准来避免被有序或逆序数组“针对”,从而在实践中无限接近 O(n log n) 的平均性能。三路快排的优势在于,它在随机化的基础上,还从算法结构上“免疫”了大量重复元素带来的性能退化。
总结与选择建议¶
- Lomuto:教学之选。当你想要最清晰地展示快排思想时。
- Hoare (双路):通用之选。当你需要一个在各种数据分布下都表现出色的、最快的通用排序算法时。
- 三路快排:专攻之选。当你明确知道要处理的数据包含大量重复值时,它是不二之选。
三路快排非原地实现¶
import random
def quick_sort_basic(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
right = [x for x in arr if x > pivot]
middle = [x for x in arr if x == pivot]
return quick_sort_basic(left) + middle + quick_sort_basic(right)
# --- 示例 ---
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort_basic(list(arr))
print(f"原始数组: {arr}")
print(f"排序后数组: {sorted_arr}")
原始数组: [10, 7, 8, 9, 1, 5] 排序后数组: [1, 5, 7, 8, 9, 10]
快速排序的原地实现¶
Lomuto 方案¶
import random
class QuickSort:
"""
分块一:使用Lomuto分区方案的快速排序。
代码结构清晰,分为入口和递归辅助两个方法。
"""
# --- 第 1 个逻辑块:公共入口 ---
def sort(self, nums: list) -> list:
"""
排序的公共入口方法,负责启动递归流程。
"""
if not nums:
return []
# 调用内部递归函数来处理整个列表
self._sort_recursive(nums, 0, len(nums) - 1)
return nums
# --- 第 2 个逻辑块:递归与分区 ---
def _sort_recursive(self, nums: list, left: int, right: int):
"""
内部递归函数,负责“分而治之”。
"""
if left >= right: # 递归的终止条件
return
# “分”:找到基准点
pivot_index = self._partition(nums, left, right)
# “治”:分别处理左右两个子数组
self._sort_recursive(nums, left, pivot_index - 1)
self._sort_recursive(nums, pivot_index + 1, right)
def _partition(self, nums: list, left: int, right: int) -> int:
"""
Lomuto分区方案:将小于基准的元素移动到左边。
"""
rand_pivot_index = random.randint(left, right)
pivot_value = nums[rand_pivot_index] # 提前记录基准值
# 将基准换到最右边,方便处理
nums[rand_pivot_index], nums[right] = nums[right], nums[rand_pivot_index]
i = left - 1
for j in range(left, right):
if nums[j] < pivot_value:
i += 1
nums[i], nums[j] = nums[j], nums[i]
# 将基准放回正确位置
nums[i + 1], nums[right] = nums[right], nums[i + 1]
return i + 1
# --- 使用示例 ---
sorter = QuickSort()
arr1 = [10, 7, 8, 9, 1, 5]
sorter.sort(arr1)
print(f"随机输入排序后: {arr1}")
arr2 = [1, 2, 3, 4, 5, 6]
sorter.sort(arr2)
print(f"有序输入排序后: {arr2}")
arr3 = [6, 5, 4, 3, 2, 1]
sorter.sort(arr3)
print(f"逆序输入排序后: {arr3}")
随机输入排序后: [1, 5, 7, 8, 9, 10] 有序输入排序后: [1, 2, 3, 4, 5, 6] 逆序输入排序后: [1, 2, 3, 4, 5, 6]
class QuickSort():
def sort(self, nums):
if len(nums) <= 1:
return nums
self.sort_recursive(nums, 0, len(nums)-1)
return nums
def sort_recursive(self, nums, left, right):
if left >= right:
return #原地排序的辅助函数通常不返回值
pivot = self.partition(nums, left, right)
self.sort_recursive(nums, left, pivot-1)
self.sort_recursive(nums, pivot+1, right)
def partition(self, nums, left, right):
pivot_index = random.randint(left, right)
pivot_value = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
i = left-1
for j in range(left, right):
if nums[j] < pivot_value: #严格分区
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1], nums[right] = nums[right], nums[i+1]
return i+1
arr = [11, 4, 10, 3, 100]
quicksort = QuickSort()
sorted_arr = quicksort.sort(arr)
print(f"排序后:{sorted_arr}")
排序后:[3, 4, 10, 11, 100]
归并排序¶
下面,我将用“三步走”的方式,带您彻底理解的思想、步骤,并亲手实现它。
第一步:核心思想与比喻¶
归并排序是**“分而治之” (Divide and Conquer)** 思想的完美体现。它处理问题的思路就像一位从容不迫的将军:
面对一个庞大而混乱的军队(一个无序的数组),将军并不直接试图去整理整个队伍。他会说:
- “分!” (Divide):把军队一分为二。然后对每个小分队下达同样的命令:“你们也去一分为二!”。这个过程一直持续下去,直到每个士兵都自成一队。
- “治!” (Conquer):一个士兵的队伍,还需要排序吗?完全不用,他天然就是有序的。这是最简单的“已解决”状态。
- “合!” (Merge):将军现在开始“合并”。他找到任意两个已经排好序的小队(最开始是两个单兵),让他们合并成一个更大的、依然有序的队伍。合并的规则很简单:每次从两个队伍的排头兵里挑出个子更矮的那个出列,站到新队伍里。这个过程不断重复,直到所有小队都合并回最初那个庞大且有序的军队。
核心: 归并排序的精髓不在于“排序”,而在于高效地“合并”两个已经有序的数组。
第二步:图解步骤 (以数组 [38, 27, 43, 3] 为例)¶
1. 分割 (Divide) 阶段¶
这个过程像一棵树一样向下展开,不断地对半分裂。
[38, 27, 43, 3]
/ \
[38, 27] [43, 3]
/ \ / \
[38] [27] [43] [3] <-- 分割到底,每个数组都只有一个元素,天然有序
2. 合并 (Merge) 阶段¶
现在,我们从底层开始,将有序的子数组两两合并,像爬树一样向上汇总。
[38] [27] [43] [3]
\ / \ /
合并-> [27, 38] 合并-> [3, 43]
\ /
合并-> [3, 27, 38, 43] <-- 最终得到完全有序的数组
合并 [27, 38] 和 [3, 43] 的过程:
- 比较
27和3,3更小,取出3。新数组:[3] - 比较
27和43,27更小,取出27。新数组:[3, 27] - 比较
38和43,38更小,取出38。新数组:[3, 27, 38] - 左边数组空了,直接把右边剩下的
43接上。新数组:[3, 27, 38, 43]。合并完成!
第三步:简洁易懂的代码实现¶
我们将这个逻辑拆分成两个函数:
merge_sort: 负责“分割”和“递归”。_merge: 负责“合并”两个有序数组。
性能分析¶
时间复杂度: O(n log n)
log n:来自“分割”的次数。一个长度为 n 的数组,每次对半切,总共要切log n次才能切成单个元素。n:来自“合并”的开销。在每一层合并中,我们都需要对总共n个元素进行一次处理。- 它非常稳定,无论是最好、最坏还是平均情况,都是 O(n log n)。
空间复杂度: O(n)
- 这是归并排序的主要“缺点”。在合并时,我们需要一个额外的
result数组来存储合并后的结果。在递归的每一层,都需要临时空间,总的空间开销是 O(n)。因此,它不是原地排序算法。
- 这是归并排序的主要“缺点”。在合并时,我们需要一个额外的
现在您已经掌握了数组版归并排序的精髓,再回头看链表排序,就会发现它们背后的思想是完全一致的,只是操作的数据结构不同而已。
from typing import List
def _merge(left_sorted: List[int], right_sorted: List[int]) -> List[int]:
"""
辅助函数:合并两个已经排好序的列表。
这是归并排序的核心所在。
"""
# 结果列表
result = []
# 分别指向 left 和 right 列表的当前比较位置的指针
i, j = 0, 0
left_len = len(left_sorted)
right_len = len(right_sorted)
# 像拉拉链一样,交替比较两个列表的元素
while i < left_len and j < right_len:
# 如果左边的元素更小,就把它放入结果列表
if left_sorted[i] <= right_sorted[j]:
result.append(left_sorted[i])
i += 1
# 否则,把右边的元素放入结果列表
else:
result.append(right_sorted[j])
j += 1
# 循环结束后,其中一个列表必然还有剩余元素
# 直接把剩下的部分全部接到结果列表的末尾
if i < left_len:
result.extend(left_sorted[i:])
if j < right_len:
result.extend(right_sorted[j:])
return result
def merge_sort(arr: List[int]) -> List[int]:
"""
归并排序的主函数。
"""
# --- 递归的终止条件 (Conquer) ---
# 如果数组只有一个或零个元素,它本身就是有序的
if len(arr) <= 1:
return arr
# --- 分割 (Divide) ---
# 找到数组的中点
mid = len(arr) // 2
# 将数组一分为二
left_half = arr[:mid]
right_half = arr[mid:]
# --- 递归调用 ---
# 分别对左右两个子数组进行排序
sorted_left = merge_sort(left_half)
sorted_right = merge_sort(right_half)
# --- 合并 (Merge) ---
# 将排序好的两个子数组合并并返回
return _merge(sorted_left, sorted_right)
# --- 使用示例 ---
if __name__ == "__main__":
my_array = [38, 27, 43, 3, 9, 82, 10]
print(f"原始数组: {my_array}")
sorted_array = merge_sort(my_array)
print(f"排序后数组: {sorted_array}")
# 验证原数组没有被修改(因为这不是原地排序)
print(f"原数组是否改变: {my_array}")
原始数组: [38, 27, 43, 3, 9, 82, 10] 排序后数组: [3, 9, 10, 27, 38, 43, 82] 原数组是否改变: [38, 27, 43, 3, 9, 82, 10]
def sort_merge(nums):
n = len(nums)
if n <= 1:
return nums
mid = n//2
left = nums[:mid]
right = nums[mid:]
left_sort = sort_merge(left)
right_sort = sort_merge(right)
return merge(left_sort, right_sort)
def merge(left, right):
result = []
left_len = len(left)
right_len = len(right)
i, j = 0, 0
while i < left_len and j < right_len:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i < left_len:
result += left[i:]
if j < right_len:
result += right[j:]
return result
# --- 使用示例 ---
if __name__ == "__main__":
my_array = [38, 27, 43, 3, 9, 82, 10]
print(f"原始数组: {my_array}")
sorted_array = sort_merge(my_array)
print(f"排序后数组: {sorted_array}")
# 验证原数组没有被修改(因为这不是原地排序)
print(f"原数组是否改变: {my_array}")
原始数组: [38, 27, 43, 3, 9, 82, 10] 排序后数组: [3, 9, 10, 27, 38, 43, 82] 原数组是否改变: [38, 27, 43, 3, 9, 82, 10]