qsort

#include<bits/stdc++.h>
using namespace std;

void print(vector<int> &arr){
    for(auto &a : arr){
        cout << a << " ";
    }
    cout << endl;
}

void qsort(vector<int> &arr, int start, int end){
    if(end - start <=  1) return ;
    int val = arr[start];
    int i = start, j = end - 1;
    while(i < j){
        // 1.应该让i从start开始 2.应该先缩小j的范围
        while(i < j && arr[j] > val) j--;
        while(i < j && arr[i] <= val) i++;
        swap(arr[i], arr[j]);
    }
    print(arr);
    swap(arr[start], arr[i]);
    qsort(arr, start, i);
    qsort(arr, i + 1, end);
}

int main(){
    vector<int> nums = {4,5,67,8,89,8999,3443};
    qsort(nums, 0, nums.size());
    print(nums);
    return 0;
}