10.1 冒泡排序、选择排序、插入排序

冒泡排序、选择排序和插入排序是三种最基础的排序算法，虽然它们的时间复杂度都是 O(n²)，但在理解排序思想和处理小规模数据时仍有其价值。

冒泡排序通过重复遍历数组，比较相邻元素并交换位置，使得较大的元素逐渐"冒泡"到数组末尾。

选择排序每次从未排序部分找到最小元素，将其放到已排序部分的末尾。

插入排序将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
冒泡排序	bubble_sort(arr)	通过相邻元素比较和交换实现排序，稳定排序，时间复杂度O(n²)，空间复杂度O(1)
选择排序	selection_sort(arr)	每次选择最小元素放到前面，不稳定排序，时间复杂度O(n²)，空间复杂度O(1)
插入排序	insertion_sort(arr)	将元素插入到已排序部分的正确位置，稳定排序，时间复杂度O(n²)，空间复杂度O(1)

def bubble_sort(arr):
    """
    冒泡排序实现
    输入: arr - 待排序的列表
    输出: 排序后的列表（原地修改）
    """
    # 获取数组长度
    n = len(arr)
    
    # 外层循环控制排序轮数
    for i in range(n):
        # 标记本轮是否发生交换，用于优化
        swapped = False
        
        # 内层循环进行相邻元素比较
        # 每轮后最大元素已到位，所以范围逐渐缩小
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素，则交换
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 如果本轮没有发生交换，说明数组已有序
        if not swapped:
            break
    
    return arr

def selection_sort(arr):
    """
    选择排序实现
    输入: arr - 待排序的列表
    输出: 排序后的列表（原地修改）
    """
    # 获取数组长度
    n = len(arr)
    
    # 遍历数组的每个位置
    for i in range(n):
        # 假设当前位置是最小值的位置
        min_idx = i
        
        # 在未排序部分寻找真正的最小值
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 将找到的最小值与当前位置交换
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

def insertion_sort(arr):
    """
    插入排序实现
    输入: arr - 待排序的列表
    输出: 排序后的列表（原地修改）
    """
    # 从第二个元素开始（第一个元素视为已排序）
    for i in range(1, len(arr)):
        # 保存当前要插入的元素
        key = arr[i]
        # 已排序部分的最后一个位置
        j = i - 1
        
        # 在已排序部分中找到合适的插入位置
        # 从右向左比较，同时移动元素
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 插入当前元素到正确位置
        arr[j + 1] = key
    
    return arr

# 测试代码
if __name__ == "__main__":
    try:
        # 测试冒泡排序
        test_arr1 = [64, 34, 25, 12, 22, 11, 90]
        print("原始数组:", test_arr1)
        bubble_sort(test_arr1.copy())
        print("冒泡排序结果:", bubble_sort(test_arr1.copy()))
        
        # 测试选择排序
        test_arr2 = [64, 34, 25, 12, 22, 11, 90]
        print("选择排序结果:", selection_sort(test_arr2.copy()))
        
        # 测试插入排序
        test_arr3 = [64, 34, 25, 12, 22, 11, 90]
        print("插入排序结果:", insertion_sort(test_arr3.copy()))
        
    except Exception as e:
        print(f"排序过程中发生错误: {e}")

注意事项：

• 这三种排序算法都是原地排序，空间复杂度为 O(1)
• 冒泡排序和插入排序是稳定排序，选择排序是不稳定排序
• 对于小规模数据（n < 50），插入排序通常表现最好
• 冒泡排序可以通过提前终止优化，在最好情况下达到 O(n) 时间复杂度
• 插入排序在处理部分有序的数据时效率很高

这节介绍了三种基础排序算法的原理和实现，它们虽然效率不高，但是理解更高级排序算法的基础，也是面试中的常客。

10.2 快速排序：分区（partition）与递归

快速排序是一种高效的分治排序算法，平均时间复杂度为 O(n log n)，是实际应用中最常用的排序算法之一。它的核心思想是选择一个基准元素（pivot），将数组分为两部分：小于基准的部分和大于基准的部分，然后递归地对这两部分进行排序。

快速排序的关键在于分区（partition）操作，它负责将数组重新排列，使得基准元素左侧的元素都小于等于基准，右侧的元素都大于等于基准。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
快速排序	quick_sort(arr, low, high)	基于分治思想的高效排序算法，平均时间复杂度O(n log n)，最坏情况O(n²)，空间复杂度O(log n)
分区操作	partition(arr, low, high)	将数组分为小于基准和大于基准的两部分，返回基准元素的最终位置

import random

def partition(arr, low, high):
    """
    分区函数：将数组分为小于基准和大于基准的两部分
    输入: arr - 待分区的数组, low - 起始索引, high - 结束索引
    输出: 基准元素的最终位置索引
    """
    # 选择最后一个元素作为基准
    pivot = arr[high]
    
    # i 指向小于基准区域的最后一个位置
    i = low - 1
    
    # 遍历从low到high-1的所有元素
    for j in range(low, high):
        # 如果当前元素小于等于基准
        if arr[j] <= pivot:
            # 扩展小于基准的区域
            i += 1
            # 交换元素
            arr[i], arr[j] = arr[j], arr[i]
    
    # 将基准元素放到正确位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    
    # 返回基准元素的位置
    return i + 1

def quick_sort(arr, low, high):
    """
    快速排序主函数
    输入: arr - 待排序的数组, low - 起始索引, high - 结束索引
    输出: 排序后的数组（原地修改）
    """
    # 递归的基本条件：当low >= high时，子数组长度<=1，无需排序
    if low < high:
        # 进行分区操作，获取基准元素的正确位置
        pi = partition(arr, low, high)
        
        # 递归排序基准左边的子数组
        quick_sort(arr, low, pi - 1)
        
        # 递归排序基准右边的子数组
        quick_sort(arr, pi + 1, high)
    
    return arr

def randomized_quick_sort(arr):
    """
    随机化快速排序包装函数
    输入: arr - 待排序的数组
    输出: 排序后的数组
    """
    # 处理空数组或单元素数组的情况
    if len(arr) <= 1:
        return arr
    
    # 调用快速排序主函数
    return quick_sort(arr, 0, len(arr) - 1)

# 测试代码
if __name__ == "__main__":
    try:
        # 测试快速排序
        test_arr = [64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42]
        print("原始数组:", test_arr)
        
        # 创建副本避免修改原数组
        sorted_arr = randomized_quick_sort(test_arr.copy())
        print("快速排序结果:", sorted_arr)
        
        # 测试边界情况：空数组
        empty_arr = []
        print("空数组排序结果:", randomized_quick_sort(empty_arr))
        
        # 测试边界情况：单元素数组
        single_arr = [42]
        print("单元素数组排序结果:", randomized_quick_sort(single_arr))
        
    except Exception as e:
        print(f"快速排序过程中发生错误: {e}")

注意事项：

• 快速排序的最坏情况发生在每次分区都极不平衡时（如数组已有序），此时时间复杂度退化为 O(n²)
• 通过随机选择基准元素可以避免最坏情况，使期望时间复杂度保持在 O(n log n)
• 快速排序是不稳定的排序算法，相同元素的相对位置可能改变
• 递归实现的快速排序在最坏情况下可能导致栈溢出，对于大数据集可以考虑迭代实现
• Python 的内置 sort() 方法使用的是 Timsort 算法，不是快速排序

这节讲解了快速排序的核心思想和实现方式，通过分区操作和递归调用实现了高效的排序，是理解分治算法的经典案例。

10.3 归并排序：分治与稳定排序

归并排序是另一种经典的分治排序算法，它将数组分成两半，递归地对每一半进行排序，然后将两个有序的半部分合并成一个完整的有序数组。归并排序的最大特点是它是稳定的排序算法，且时间复杂度始终为 O(n log n)，不受输入数据分布的影响。

归并排序的核心在于合并（merge）操作，它负责将两个已排序的子数组合并成一个更大的已排序数组。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
归并排序	merge_sort(arr)	基于分治思想的稳定排序算法，时间复杂度始终为O(n log n)，空间复杂度O(n)
合并操作	merge(left, right)	将两个已排序的数组合并成一个有序数组，保持稳定性

def merge(left, right):
    """
    合并两个已排序的数组
    输入: left - 左侧已排序数组, right - 右侧已排序数组
    输出: 合并后的有序数组
    """
    # 初始化结果数组
    result = []
    
    # 初始化左右数组的指针
    i = j = 0
    
    # 比较两个数组的元素，将较小的添加到结果中
    while i < len(left) and j < len(right):
        # 使用 <= 保证稳定性：相等元素保持原有顺序
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 添加剩余元素（如果有的话）
    # 左数组可能还有剩余元素
    while i < len(left):
        result.append(left[i])
        i += 1
    
    # 右数组可能还有剩余元素
    while j < len(right):
        result.append(right[j])
        j += 1
    
    return result

def merge_sort(arr):
    """
    归并排序主函数
    输入: arr - 待排序的数组
    输出: 排序后的数组（新数组，不修改原数组）
    """
    # 递归的基本条件：数组长度<=1时已经有序
    if len(arr) <= 1:
        return arr
    
    # 找到数组中点，分割数组
    mid = len(arr) // 2
    
    # 递归排序左半部分
    left = merge_sort(arr[:mid])
    
    # 递归排序右半部分
    right = merge_sort(arr[mid:])
    
    # 合并两个已排序的部分
    return merge(left, right)

# 优化版本：原地归并排序（减少内存分配）
def merge_sort_inplace(arr, temp_arr, left, right):
    """
    原地归并排序实现（使用临时数组减少内存分配）
    输入: arr - 待排序数组, temp_arr - 临时数组, left - 左边界, right - 右边界
    输出: 无（原地修改arr）
    """
    if left < right:
        # 找到中点
        mid = (left + right) // 2
        
        # 递归排序左半部分
        merge_sort_inplace(arr, temp_arr, left, mid)
        
        # 递归排序右半部分
        merge_sort_inplace(arr, temp_arr, mid + 1, right)
        
        # 合并两个部分
        merge_inplace(arr, temp_arr, left, mid, right)

def merge_inplace(arr, temp_arr, left, mid, right):
    """
    原地合并函数
    输入: arr - 主数组, temp_arr - 临时数组, left - 左边界, mid - 中点, right - 右边界
    输出: 无（原地修改arr）
    """
    # 将需要合并的数据复制到临时数组
    for i in range(left, right + 1):
        temp_arr[i] = arr[i]
    
    # 初始化指针
    i = left      # 左子数组起始位置
    j = mid + 1   # 右子数组起始位置
    k = left      # 主数组写入位置
    
    # 合并过程
    while i <= mid and j <= right:
        if temp_arr[i] <= temp_arr[j]:
            arr[k] = temp_arr[i]
            i += 1
        else:
            arr[k] = temp_arr[j]
            j += 1
        k += 1
    
    # 复制左子数组剩余元素
    while i <= mid:
        arr[k] = temp_arr[i]
        i += 1
        k += 1
    
    # 复制右子数组剩余元素（实际上不需要，因为已经在正确位置）
    while j <= right:
        arr[k] = temp_arr[j]
        j += 1
        k += 1

def merge_sort_optimized(arr):
    """
    优化的归并排序包装函数
    输入: arr - 待排序数组
    输出: 排序后的数组
    """
    if len(arr) <= 1:
        return arr
    
    # 创建临时数组以减少内存分配
    temp_arr = [0] * len(arr)
    arr_copy = arr.copy()
    merge_sort_inplace(arr_copy, temp_arr, 0, len(arr_copy) - 1)
    return arr_copy

# 测试代码
if __name__ == "__main__":
    try:
        # 测试基本归并排序
        test_arr = [64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42]
        print("原始数组:", test_arr)
        
        sorted_arr = merge_sort(test_arr)
        print("归并排序结果:", sorted_arr)
        
        # 测试稳定性：包含重复元素
        stable_test = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd')]
        # 自定义比较：只比较第一个元素
        def merge_sort_tuples(arr):
            if len(arr) <= 1:
                return arr
            mid = len(arr) // 2
            left = merge_sort_tuples(arr[:mid])
            right = merge_sort_tuples(arr[mid:])
            return merge_tuples(left, right)
        
        def merge_tuples(left, right):
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                # 只比较元组的第一个元素
                if left[i][0] <= right[j][0]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result.extend(left[i:])
            result.extend(right[j:])
            return result
        
        stable_result = merge_sort_tuples(stable_test)
        print("稳定性测试结果:", stable_result)
        print("注意：(3,'a')在(3,'c')前面，保持了原有顺序")
        
    except Exception as e:
        print(f"归并排序过程中发生错误: {e}")

注意事项：

• 归并排序是稳定的排序算法，相等元素的相对位置不会改变
• 时间复杂度始终为 O(n log n)，不受输入数据的影响
• 空间复杂度为 O(n)，需要额外的存储空间来存放临时数组
• 归并排序适合处理链表排序，因为链表的合并操作不需要额外空间
• 对于小规模数组，可以结合插入排序来提高性能（混合排序）

这节详细介绍了归并排序的分治思想和实现方式，强调了其稳定性和一致的时间复杂度特性，是理解稳定排序算法的重要基础。

10.4 堆排序：建堆 + 重复取顶

堆排序是一种基于二叉堆数据结构的比较排序算法。它利用堆的性质（最大堆或最小堆）来实现排序，时间复杂度为 O(n log n)，空间复杂度为 O(1)，是一种原地排序算法。堆排序的核心思想是先将数组构建成一个最大堆，然后重复地将堆顶元素（最大值）与堆的最后一个元素交换，并调整堆以维持堆的性质。

堆排序的关键操作包括建堆（heapify）和堆的维护，其中 heapify 操作负责将一个节点及其子树调整为堆结构。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
堆排序	heap_sort(arr)	基于堆数据结构的原地排序算法，时间复杂度O(n log n)，空间复杂度O(1)，不稳定
堆化操作	heapify(arr, n, i)	将以i为根的子树调整为最大堆，n为堆的大小

def heapify(arr, n, i):
    """
    堆化操作：将以i为根的子树调整为最大堆
    输入: arr - 数组, n - 堆的大小, i - 根节点索引
    输出: 无（原地修改arr）
    """
    # 初始化最大值为根节点
    largest = i
    
    # 计算左子节点和右子节点的索引
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 如果左子节点存在且大于根节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 如果右子节点存在且大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 如果最大值不是根节点，则交换并继续堆化
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归堆化受影响的子树
        heapify(arr, n, largest)

def build_max_heap(arr):
    """
    构建最大堆
    输入: arr - 待构建堆的数组
    输出: 无（原地修改arr）
    """
    n = len(arr)
    
    # 从最后一个非叶子节点开始向上堆化
    # 最后一个非叶子节点的索引为 (n//2 - 1)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def heap_sort(arr):
    """
    堆排序主函数
    输入: arr - 待排序的数组
    输出: 排序后的数组（原地修改）
    """
    n = len(arr)
    
    # 第一步：构建最大堆
    build_max_heap(arr)
    
    # 第二步：逐个提取堆顶元素
    for i in range(n - 1, 0, -1):
        # 将堆顶（最大值）与末尾元素交换
        arr[0], arr[i] = arr[i], arr[0]
        
        # 重新调整堆（堆大小减1）
        heapify(arr, i, 0)
    
    return arr

# 辅助函数：打印堆的结构（用于调试）
def print_heap(arr, n):
    """
    打印堆的层次结构（用于调试）
    输入: arr - 堆数组, n - 堆大小
    输出: 无
    """
    if n == 0:
        print("空堆")
        return
    
    level = 0
    i = 0
    while i < n:
        # 计算当前层的元素数量
        elements_in_level = min(2 ** level, n - i)
        print(f"Level {level}: ", end="")
        
        # 打印当前层的元素
        for j in range(elements_in_level):
            print(arr[i + j], end=" ")
        print()
        
        i += elements_in_level
        level += 1

# 测试代码
if __name__ == "__main__":
    try:
        # 测试堆排序
        test_arr = [64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42]
        print("原始数组:", test_arr)
        
        # 创建副本进行排序
        heap_sorted = heap_sort(test_arr.copy())
        print("堆排序结果:", heap_sorted)
        
        # 演示建堆过程
        demo_arr = [4, 10, 3, 5, 1]
        print("\n建堆演示:")
        print("原始数组:", demo_arr)
        build_max_heap(demo_arr)
        print("构建最大堆后:", demo_arr)
        print("堆的层次结构:")
        print_heap(demo_arr, len(demo_arr))
        
        # 测试边界情况
        edge_cases = [
            [],
            [42],
            [5, 5, 5, 5],
            [1, 2, 3, 4, 5],  # 已排序
            [5, 4, 3, 2, 1]   # 逆序
        ]
        
        print("\n边界情况测试:")
        for i, case in enumerate(edge_cases):
            original = case.copy()
            result = heap_sort(case)
            print(f"测试{i+1}: {original} -> {result}")
            
    except Exception as e:
        print(f"堆排序过程中发生错误: {e}")

注意事项：

• 堆排序是不稳定的排序算法，相等元素的相对位置可能改变
• 时间复杂度始终为 O(n log n)，最坏、平均、最好情况都相同
• 空间复杂度为 O(1)，是真正的原地排序算法
• 建堆的时间复杂度实际上是 O(n)，而不是直观认为的 O(n log n)
• 堆排序在实际应用中不如快速排序和归并排序常用，但在需要保证最坏情况性能时很有价值
• 堆排序的缓存性能较差，因为访问模式不够局部化

这节详细介绍了堆排序的原理和实现，通过建堆和重复提取堆顶元素的方式实现了高效的原地排序，是理解堆数据结构应用的重要实例。