快速排序算法是一种常用的排序算法，比选择算法快得多，快速排序算法使用了分而治之（divide and conquer，D&C）的思想，即一种著名的递归式问题解决方法。
分而治之
分而治之的工作原理：
- 找出基线条件，这种条件必须尽可能简单。
- 不断将问题分解（或者说缩小规模），直到符合基线条件。
分而治之并非是直接用于解决问题的算法，而是一种解决问题的思路，也可以说是算法实现的一种思路，我们用一个例子来说明一下其具体的工作原理。
给定一个数组{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;
}
