排序

快速排序¶

核心的相似思想：分而治之¶

首先，这三种方案都服务于快速排序的同一个宏伟蓝图——“分而治之” (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 (双路)：通用之选。当你需要一个在各种数据分布下都表现出色的、最快的通用排序算法时。
三路快排：专攻之选。当你明确知道要处理的数据包含大量重复值时，它是不二之选。

三路快排非原地实现¶

In [1]:

Copied!





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}")
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 方案¶

In [22]:

Copied!





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}")
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]

In [30]:

Copied!





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}")
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)。因此，它不是原地排序算法。

现在您已经掌握了数组版归并排序的精髓，再回头看链表排序，就会发现它们背后的思想是完全一致的，只是操作的数据结构不同而已。

In [47]:

Copied!





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}")
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]

In [55]:

Copied!





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}")
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]

排序