分而治之与快速排序

快速排序算法是一种常用的排序算法，比选择算法快得多，快速排序算法使用了分而治之（divide and conquer，D&C）的思想，即一种著名的递归式问题解决方法。

分而治之

分而治之的工作原理：

1. 找出基线条件，这种条件必须尽可能简单。
2. 不断将问题分解（或者说缩小规模），直到符合基线条件。

分而治之并非是直接用于解决问题的算法，而是一种解决问题的思路，也可以说是算法实现的一种思路，我们用一个例子来说明一下其具体的工作原理。

给定一个数组{2, 4, 6}，计算该数组和，使用循环很容易实现，那如果使用递归函数如何实现呢？

基于分而治之的思想，首先找出该问题的基线，首先基线条件必须尽可能的简单，因此当数组的元素个数为0或者1的时候是最简单的情况，结果就是0或者1，因此

基线条件： 
{ }------元素个数为0，sum = 0；
{a}------元素个数为1，sum = a;

找到基线后，需要将问题不断地缩减让其离基线跟进一步，即

sum({2, 4, 6})
        |
     2  +  sum({4, 6}) 
               |
            4  +  sum({6})
                     |
                     6 ---对应的就是基线条件

那对应的递归实现如下所示：

int sum(std::vector<int> arr) {
    if (arr.empty()) return 0;  // 基线条件中元素个数为0的情况

    int last_num = arr.back();  // 保存最后一个元素的值
    arr.pop_back();  // 将该元素从数组中删除以进行下一次递归调用
    return last_num + sum(arr);
}

分而治之就是将问题拆分成两个次复杂的问题，然后对于每个次复杂问题再进一步分解成两个次次复杂的问题，循环往下，直到问题都变成基线问题。

快速排序

在了解了分而治之的思想后，如何将其用到排序问题上呢？对于排序算法来说，最简单的情况是什么呢？那就是不用对其进行排序，其对应的基线应该如下：

快速排序的基线（不需要排序的数组）：
{ }------元素个数为0，空数组排序结果就是它本身；
{a}------元素个数为1，只包含一个元素的数组，组排序结果也是它本身;

接下来关键的问题是如何将数组分解成次复杂的数组，快速排序就是通过基准值 （pivot）将原数组分解成两个次复杂的数组，基准值往往选取数组的中间值。

选取基准值后，如何通过基准值对剩余元素分割呢？分割方法如下：

快速排序将大于等于基准值（这里是2）的元素放在一块组成数组B，小于基准值的放在一块组成数组A，数组A放在基准值2的左边，数组B放在基准值2的右边，到目前为止，基准2已经处于最终排序结果的位置了，那么我们按照同样的方法对A和B进行快速排序，直至其达到基准条件，最终完成排序。

其算法实现如下所示：

#include <iostream>
#include <vector>

template <typename T>
std::vector<T> quickSort(const std::vector<T>& arr) {
    if (arr.size() < 2) return arr;  // 基线条件

    int pivot_index = arr.size() / 2 - 1;  // 基准值的索引
    const T pivot = arr[pivot_index];      // 基准值
    std::vector<T> less,
    greater;  // less用来存放小于基准值的元素，geater用来存放大于等于基准值的元素

    for (int i = 0; i < arr.size(); ++i) {  // 遍历所有元素
        if (i == pivot_index) continue;       // 抛除基准值
        if (arr[i] < pivot)
            less.emplace_back(arr[i]);  // 小于基准值的元素存入less
        else
            greater.emplace_back(arr[i]);  // 大于等于的元素存入greater
    }

    std::vector<T> sort_less = quickSort(less);  // 对less进行快速排序
    std::vector<T> sort_greater = quickSort(greater);  // 对greater进行快速排序

    // 组装排序后结果
    sort_less.emplace_back(pivot);
    sort_less.insert(sort_less.end(), sort_greater.begin(), sort_greater.end());

    return sort_less;
}

int main() {
    std::vector<int> arr = {3, 5, 2, 1, 4};
    std::vector<int> sorted = quickSort(arr);
    for (int num : sorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}