快速排序（Quick Sort）

一、教学目标：

1、 理解快速排序（分治 + 基准划分）、归并排序（分治 + 合并有序子数组）的核心原理，明确两者分治思想的异同；

2、 掌握快排的基准选择、区间划分逻辑，归并排序的拆分与合并步骤，能独立编写 C++ 基础实现代码；

3、 能手动模拟简单数组（5-8 个元素）的排序执行流程，分析两者时间复杂度（均为 O (nlogn)）与空间复杂度（快排 O (logn)、归并 O (n)）；

4、 明确两种算法的适用场景（快排适用于普通数组、归并不稳定场景；归并适用于需要稳定排序、大数据量场景），能根据需求选择合适算法，规避边界处理错误。

二、核心知识点

🔑 1. 算法思想

text

快速排序 = 选择基准 + 分区 + 递归排序

1. 选择基准(pivot)
2. 分区：小于基准的放左边，大于的放右边
3. 递归排序左右两部分

🔑 2. 核心实现代码

cpp

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 分区操作，返回基准位置
        int pi = partition(arr, low, high);
        
        // 递归排序基准左右两部分
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Lomuto分区方案（较易理解）
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;        // 小于基准的边界索引
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

🔑 3. 基准选择策略

策略	实现	特点
固定选择	arr[high]	简单，但可能效率低
随机选择	arr[random(low, high)]	避免最坏情况
三数取中	取首、中、尾的中位数	⭐推荐，平衡性好

cpp

// 三数取中法选择基准
int medianOfThree(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    
    // 对三个元素排序，取中间值
    if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
    
    // 将中间值放到high位置，作为基准
    swap(arr[mid], arr[high]);
    return arr[high];
}

🔑 4. 优化技巧

1. 小数组优化：当数组小于阈值时，切换到插入排序
2. 尾递归优化：减少递归调用栈深度
3. 三路快排：处理大量重复元素的情况

cpp

// 三路快速排序
void quickSort3Way(int arr[], int low, int high) {
    if (low >= high) return;
    
    int lt = low;      // arr[low..lt-1] < pivot
    int gt = high;     // arr[gt+1..high] > pivot
    int i = low + 1;   // arr[lt..i-1] == pivot
    int pivot = arr[low];
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt++], arr[i++]);
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt--]);
        } else {
            i++;
        }
    }
    
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

🔑 5. 复杂度分析

情况	时间复杂度	空间复杂度	说明
最佳	O(n log n)	O(log n)	每次分区均衡
平均			一般情况
最坏	O(n²)	O(n)	每次分区极度不平衡

稳定性：不稳定排序

归并排序（Merge Sort）

一、知识目标

✅ 基础理解目标

1. 理解分治策略：掌握"分-治-合"的三步流程
2. 掌握合并过程：理解如何合并两个有序数组
3. 理解递归/迭代：掌握两种实现方式的区别

✅ 实现能力目标

1. 编码实现：能够手写归并排序的完整代码
2. 合并算法：掌握高效的数组合并方法
3. 边界处理：正确处理各种边界情况

✅ 高级应用目标

1. 外部排序：理解在外部存储中的应用
2. 链表排序：掌握链表的归并排序实现
3. 复杂度证明：能够分析算法复杂度

二、核心知识点

1. 算法思想

归并排序 = 分 + 治 + 合

1. 分：将数组不断对半分，直到单个元素
2. 治：递归排序每个子数组
3. 合：合并两个有序数组

2. 核心实现代码

// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    
    // 递归排序左右两半
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    
    // 合并已排序的两半
    merge(arr, left, mid, right);
}

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 复制数据
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    // 合并回原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    
    // 复制剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

3. 复杂度分析

方面	时间复杂度	空间复杂度	说明
最佳	O(n log n)	O(n)	总是需要额外空间
平均			稳定性能
最坏			性能稳定

稳定性：稳定排序（当合并时相等元素保持原序）

---

🔍 两种排序算法对比

特性	快速排序	归并排序
时间复杂度	平均O(n log n)，最坏O(n²)	总是O(n log n)
空间复杂度	平均O(log n)，最坏O(n)	O(n)
稳定性	不稳定	稳定
原地排序	是（通常）	否（需要额外空间）
最佳适用	内部排序，随机数据	外部排序，稳定要求
最坏情况	已排序/逆序数组	无最坏情况
缓存友好	较好	较差