排序算法基础

快速排序（划分+递归）

快速排序通过一个划分函数将数组分成左右两段，后续分别递归排序，最终在原地完成整个序列的整理。下面的实现使用第一个元素作为 pivot，配合双向填充的方式把 pivot 送到最终的位置。

初始划分函数

hua_fen 会交替从左右两端往中间填充，直到左右指针相遇再把 pivot 放回最终位置并返回索引：

#include<iostream>
#include<vector>
using namespace std;

int hua_fen(vector<int>& nums,int left,int right){
    int tmp = nums[left];
    int seq = 0; // 0 向左填，1 向右填

    while(true){
        if(left == right){
            break;
        }
        if(seq == 0){
            while(right > left && nums[right] >= tmp){
                right--;
            }
            nums[left] = nums[right];
            seq = 1;
        }else{
            while(left < right && nums[left] <= tmp){
                left++;
            }
            nums[right] = nums[left];
            seq = 0;
        }
    }
    nums[left] = tmp;
    return left;
}

void quick_sort(vector<int>& nums,int left,int right){
    if(left >= right) return;
    int mid = hua_fen(nums,left,right);
    quick_sort(nums,left,mid-1);
    quick_sort(nums,mid+1,right);
}

int main(){
    vector<int> nums = {8,2,3,4,7,4,5};
    quick_sort(nums,0,nums.size()-1);
    for(auto& val:nums){
        cout<<val<<endl;
    }
}

划分策略优化

双向循环时需要特别处理 l 与 r 的边界：

从左侧找到第一个大于 pivot 的数，从右侧找到第一个小于 pivot 的数后交换。如果只写 l<r，那么当 l 提前移动到 r 的位置并跳出循环时，r 可能永远不会再次检查，随后的交换会把本应在左边的元素丢失（如 [4,3,2,4,4,1,5]）。
当 r<l 时，区间 [0,l-1] 都是小于等于 pivot 的数，[r+1,end] 都是大于等于 pivot 的数，交换一定要和 r 交换，否则左区间可能会出现大于 pivot 的值，破坏左闭右开区间的性质。
当 r==l 时，左右只剩一个位置，既可以用 r 也可以用 l 交换，但统一使用 r 更简单。

基于上述约束，我们可以把交换的判断写得更清晰：

int hua_fen1(vector<int>& nums,int left,int right){
    int pivot = nums[left];
    int l = left + 1, r = right;
    while(true){
        while(l <= r && nums[l] <= pivot) l++;
        while(l <= r && nums[r] >= pivot) r--;
        if(l >= r) break;
        swap(nums[l], nums[r]);
        l++;
        r--;
    }
    swap(nums[left], nums[r]);
    return r;
}