图示1

image.png

思路1

  1. 以pivotIndex为界，将数组分成左右两个部分，左边的全部小于pivotIndex，右边的全部大于等于pivotindex。
  2. 具体做法如下，把pivotIndex和right位置的数值交换，确保pivotIndex在数组在最右边。
  3. 利用storeIndex进行交换，确保小于pivotValue的数值统统被放在了左边。
  4. 交换storeIndex位置和right位置，把pivotIndex放回去。

    代码1

    ```c

    include

const int N = 1e5 + 5;

void mySwap(int& a, int& b) { int temp = a; a = b; b = temp; }

int partition(int* a, int left, int right, int pivot_index) { int pivot_value = a[pivot_index]; mySwap(a[right], a[pivot_index]); int store_index = left; for (int i = left; i < right; ++i) { if (a[i] < pivot_value) { mySwap(a[store_index], a[i]); store_index++; } }

  1. mySwap(a[right], a[store_index]);
  2. return store_index;

}

void quickSort(int* a, int left, int right) { if (left >= right) { return; }

int pivot_index = (left + right) / 2;
int new_pivot_index = partition(a, left, right, pivot_index);
quickSort(a, left, new_pivot_index - 1);
quickSort(a, new_pivot_index + 1, right);

}

int main() { int n = 0; scanf(“%d”, &n); int a[N]; for (int i = 0; i < n; ++i) { scanf(“%d”, a + i); } quickSort(a, 0, n - 1);
for (int i = 0; i < n; ++i) { printf(“%d “, *(a + i)); }

return 0;

}

<a name="sBlpO"></a>
# 图示2
![image.png](https://cdn.nlark.com/yuque/0/2022/png/1626815/1649689145903-c163fe8d-23f5-4911-9aa8-d20662ad6ac4.png#clientId=u0de2067a-5e83-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=763&id=u8a8158db&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1679&originWidth=1842&originalType=binary&ratio=1&rotation=0&showTitle=false&size=940736&status=done&style=none&taskId=u16a4737c-fa55-49c4-81dc-e9c5a89fa57&title=&width=837.27270912533)
<a name="pD9KK"></a>
# 思路2

- 整体思想不变，选择一个基准值，确保小于等于基准值的被放在左边，大于等于基准值的被放到右边。
- 做法上把基准值取在中间，然后从两边向中间进行交换，双指针的做法。
- 做法参考了ACwing闫学灿大佬的做法，注意边界问题的处理。
- 利用`do-while`结构去避免重复操作的问题。
- `rp`（也就是右指针）右侧的所有数据大于等于`pivotVal`，`lp`（也就是左指针）左侧所有数据小于等于`pivotVal`，因此，在划分边界的时候，要么是`rp 和 rp + 1`，要么是`lp - 1 和 lp`
- 如果边界选择`rp 和 rp + 1`，那么就要向下取整，`pivotVal = a[(left + right) / 2]`，如果边界选择`lp - 1`和`lp`，那么需要向上取整，`pivotVal = a[(left + right + 1) / 2]`。
- 联想到二分查找里面的做法，一般内部取到`xxx - 1`，那么就说明需要往上取整。如果内部取到`xxx + 1`，那么说明应该往下取整。
<a name="DqOvj"></a>
# 代码2
```c
#include <iostream>
#include <algorithm>

const int N = 1e5 + 5;

using namespace std;

void quickSort(int* a, int left, int right) {
    if (left >= right) {
        return;
    }

    // 遇到 xxx - 1，需要往上取整
    // 遇到 xxx + 1，需要往下取整
    int pivot = a[(left + right + 1) / 2];
    int lp = left - 1;
    int rp = right + 1;

    while (lp < rp) {
        do {
            lp++;
        } while (a[lp] < pivot);

        do {
            rp--;
        } while (a[rp] > pivot);

        if (lp < rp) {
            swap(a[lp], a[rp]);
        }
    }
    quickSort(a, left, lp - 1);
    quickSort(a, lp, right);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int a[N];
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
    }
    quickSort(a, 0, n - 1);   
    for (int i = 0; i < n; ++i) {
        printf("%d ", *(a + i));
    }

    return 0;
}