快速排序，思路总结与实现

思路

1. 找基准值(pivot)
   pivot = start or end
2. 比基准值小的放左边，大的放右边

实现

1. 双指针，left从左到右找比基准值大的元素，right从右到左找比基准值小的元素
   找到后交换left和right指针的内容
   直到left = right
   这是递增排序，递减排序情况相反

2. 如果pivot = start，则右指针先动，否则左指针先动
   目的：在双指针相等后，通过交换将基准值放到合适的位置上，达到划分区域的目的。
   如果不是这样，最后需要对交换的index加1或者-1

3. 判断v[left] = v[right] 和 v[pivot] 的大小,是否需要交换
   需要准备基准值的index 进行递归
   当前索引处值比基准值小，交换位置 index = left
   否则说明所有的值都比基准值大，不需要交换位置 index = left - 1
   递归基准值左侧(start, index - 1)和右侧（index + 1， end）

代码

#include <vector>
#include <iostream>
#include <random>
#include <algorithm>

using namespace std;

vector<int> test_array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25};

// 打印vector内容
void printVector(const string prefix, const vector<int> &vi) {
    cout << prefix;
    for (auto i : vi) {
        cout << " " << i;
    }
    cout << endl;
}

void quickSort(vector<int> &vi, int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int pivot = start;
    int left = pivot + 1;
    int right = end;
    while (left < right)
    {
        while (left < right && vi[right] >= vi[pivot])
        {
            right--;
        }
        while (left < right && vi[left] <= vi[pivot])
        {
            left++;
        }
        swap(vi[left], vi[right]);
    }
    if (vi[left] < vi[pivot])
    {
        swap(vi[left], vi[pivot]);
    }
    else{
        left--;
    }
    quickSort(vi, start, left - 1);
    quickSort(vi, left + 1, end);
}


int main() {
    // 乱排有序vector
    auto rng = std::default_random_engine {};
    std::shuffle(std::begin(test_array), std::end(test_array), rng);

    // 排序前
    printVector("before:", test_array);

    // 排序
    quickSort(test_array, 0, test_array.size() - 1);

    // 排序后
    printVector("after:", test_array);

    return 0;
}