快速排序（双指针+递归）-爱代码爱编程

图解·：测试用例 6 6 3 1 7 2 4

代码如下：

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

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;//递归出口 
    int pivot = arr[left];      //第一个元素为枢轴 
    int i = left, j = right;  //i为左指针，j为右指针 

    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;//从右向左找， arr[j] >= pivot，下标右指针j--
        arr[i] = arr[j];                     // arr[j] < pivot,替换i所在位置的数字

        while (i < j && arr[i] <= pivot) i++;//从左向右找，arr[i] <= pivot，下标左指针i++
        arr[j] = arr[i];                     // arr[i] > pivot,替换j所在位置的数字
    }

    arr[i] = pivot;//i==j时，在arr[i]处插入pivot 
    
    //打印 
    for (int k = 0; k < arr.size(); k++) {
        cout << arr[k] << " ";
    }
    cout << endl;

    //以i==j的位置，将数组分为两半区，再进行递归快速排序 
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    quickSort(arr, 0, n - 1);

    return 0;
}

容易编写错误的代码块

    while(i<j)
    {
        while(i<j&&arr[j]>=pivot) j--;
        arr[i]=arr[j];
        
        while(i<j&&arr[i]<=pivot) i++;
        arr[j]=arr[i];
    }
    arr[i]=pivot;