分治算法：化繁为简的编程智慧 🌟

前言

👋 作为一个正在啃数据结构与算法的普通大学生，最近学到一个特别有意思的算法 —— 分治！🤓 第一次接触时觉得有点懵，但慢慢发现这玩意儿简直是个宝藏！它告诉我们：解决复杂问题根本不用一口气吃成胖子，分步来就好啦😎

什么是分治？🤔

说实话，第一次听到"分治"这个词我整个人都不好了：这啥高大上的东西啊？！😱 后来才发现，这不就是我们整理寝室的日常操作嘛！

想想看：面对那堆堆积如山的杂物，咱们都会：

先分类：课本📚、衣服👕、零食🍪...（嗯...零食应该早就被吃完了😂）
分开整理：课本按科目摆、衣服按季节叠
最后一起放好，房间立马整整齐齐！✨

这不就是分治思想嘛！原来我们早就在用了，只是不知道它有个这么酷的名字！😮

从选择排序说起 📝

还记得C++课上学的第一个排序算法吗？就是那个选择排序！简单粗暴，就是一个个找最小的数：

void selectionSort(vector<int>& arr) {
    for(int i = 0; i < arr.size(); i++) {
        int minIndex = i;
        for(int j = i + 1; j < arr.size(); j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

用选择排序处理成绩单？emmm...问题太多了！😅

班级才30个人，结果要比较400多次，我的CPU都在跟我求饶了！🥵
每次都要从头找最小值，忙得团团转 🔄
数据一多起来，那叫一个慢...我都能喝完一杯奶茶了都还没排完序！☕

快速排序：分治算法的代表作

后来学了快速排序，才知道原来排序还能这么写：

void quickSort(vector<int>& arr, int left, int right) {
    if(left >= right) return;
  
    // 选一个基准值
    int pivot = arr[(left + right) / 2];
  
    // 分区过程
    int i = left, j = right;
    while(i <= j) {
        while(arr[i] < pivot) i++;
        while(arr[j] > pivot) j--;
        if(i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
  
    // 递归排序子区间
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

快排的思路其实很简单：

随便找个基准值（比如33分）
把比33分低的放左边，高的放右边
对左右两边的数字重复这个过程
最后就自然有序了

实测效果简直惊呆了！🎉

30个人的成绩排序只要100多次比较，效率直接起飞！🚀
比选择排序快得不是一点半点，简直是天壤之别！⚡
代码是长了那么一丢丢，但理解了原理后写起来其实也还好啦～😌

分治算法的基本套路

通过快速排序，我总结出分治算法一般包含这几步：

分解：把大问题拆成小问题
- 像快排就是按基准值分成两部分
解决：递归处理小问题
- 对左右两边分别排序
合并：把小问题的结果合起来
- 快排的巧妙之处是不需要额外合并

再来个例子：二分查找

二分查找也是分治的应用，而且代码更简单：

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
  
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] == target) {
            return mid;
        } else if(arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;  // 没找到
}

用二分查找成绩单：