冒泡排序

最简单直观的排序算法，时间复杂度O(n²)

快速排序

高效的分治排序算法，平均时间复杂度O(n log n)

堆排序

基于二叉堆的排序算法，时间复杂度O(n log n)

算法原理

冒泡排序重复遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换的元素。

算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 重复步骤1~3，直到排序完成

算法分析

• 时间复杂度：O(n²)（最坏和平均情况）
• 空间复杂度：O(1)
• 稳定性：稳定

Python实现

def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # 最后i个元素已经有序
        for j in range(0, n-i-1):
            # 当前元素大于下一个元素则交换
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 测试示例
data = [64, 34, 25, 12, 22, 11, 90]
print("排序前：", data)
print("排序后：", bubble_sort(data.copy()))

def optimized_bubble_sort(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

算法原理

快速排序使用分治法策略来把一个序列分为两个子序列。步骤为：

1. 从数列中挑出一个元素作为基准(pivot)
2. 重新排序数列，所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面（相同的数可以到任一边）
3. 递归地把小于基准的子数列和大于基准的子数列排序

算法特点

• 平均时间复杂度：O(n log n)
• 最坏时间复杂度：O(n²)（当输入已经排序时）
• 空间复杂度：O(log n)（递归调用栈）
• 不稳定排序算法

Python实现

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# 测试示例
data = [10, 7, 8, 9, 1, 5, 3, 6, 2, 4]
print("排序前：", data)
print("排序后：", quick_sort(data.copy()))

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]
    
    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_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
        
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_inplace(arr, low, pi-1)
        quick_sort_inplace(arr, pi+1, high)
    return arr

算法原理

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：子节点的键值总是小于（或大于）其父节点。

算法步骤

1. 将待排序序列构建成一个最大堆（升序排序）
2. 将堆顶元素（最大值）与末尾元素交换
3. 减少堆的有效长度，重新调整结构使其满足堆定义
4. 重复步骤2-3，直到整个序列有序

算法分析

• 时间复杂度：O(n log n)（所有情况）
• 空间复杂度：O(1)
• 不稳定排序算法
• 适合大数据量排序

Python实现

def heapify(arr, n, i):
    largest = i  # 初始化最大值为根节点
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 如果左子节点存在且大于根节点
    if left < n and arr[i] < arr[left]:
        largest = left
    
    # 如果右子节点存在且大于当前最大值
    if right < n and arr[largest] < arr[right]:
        largest = right
    
    # 如果最大值不是根节点，则交换
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)  # 递归调整子树

def heap_sort(arr):
    n = len(arr)
    
    # 构建最大堆
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个提取元素
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)  # 调整剩余元素的堆结构
    
    return arr

# 测试示例
data = [12, 11, 13, 5, 6, 7, 3, 2, 8]
print("排序前：", data)
print("排序后：", heap_sort(data.copy()))