考考大家，华为云公众号里展示的这个快排程序哪里错了

8 1 2 3 8
while 就是死循环了吧，i 和 j 都动不了

While 死循环，而且 while 里面第一个 if 有啥意义么…他在循环内部更改了 arr ，但是没有更新 pivot 数值。

@joh pivot 数值一定要更新吗？

@stevenshuang 是会死循环没错，那这份代码和正确的版本之间差了什么呢？

```
void qsort(vector<int>& arr, int l, int r) {
if (l >= r) return;
int x = arr[l + r >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
if (i < j) swap(ar[i], arr[j]);
}
qsort(arr, l, j), qsort(arr, j + 1, r);
}
```

@hemingqiao 这个版本显然也是有问题的，举个简单的反例：100 1 这种长度为 2 的逆序数组

@hemingqiao Quick sort 里面 pivot 在左边、右边、中间都可以的。

真正的问题是`int i = left`这里，这把 pivot 也放进去了，那 `while(arr[i] < pivot) i++;` 一次也不会进循环体。

说不定在鸿蒙系统上就是正确的呢？手动狗头。

@samhjn 你跑一下试试呢？我在 leetcode 上的 912 提交通过之后才贴上来的

void quickSort(int left, int right, vector<int>& arr) {
if (left >= right) return;

int i = left, j = right;
int pivot = arr[left]; // 选择 left 位置的元素作为枢轴,通常会选择中位数或随机元素作为枢轴以避免最坏情况的性能。
while (i < j) {
while (i < j && arr[j] > pivot) j--; // 从右向左找第一个小于等于 pivot 的数
while (i < j && arr[i] < pivot) i++; // 从左向右找第一个大于等于 pivot 的数
if (i < j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
swap(arr[left], arr[i]); // 将枢轴放到正确的位置

quickSort(left, i - 1, arr); // 对左半部分进行快速排序
quickSort(i + 1, right, arr); // 对右半部分进行快速排序
}

@billccn 是啊，他贴的这个是有问题的

@hemingqiao 看错了抱歉，没注意到左右游标已经预先补偿了

@AntiFraud 看起来算法是 work 的，但是有没有语句或者条件是冗余的？

@samhjn 不需要.他这个算法问题怪怪的.7 楼说的对

@dif 有道理

1. 当数组存在重复元素时，可能会导致死循环。修改：i++和 j--循环条件判断改为<=
2. i 初始从 left 开始，且 pivot=arr[left]，会导致每次循环 i 和 j 总会有一个不动，pivot 值在 i 和 j 间换来换去。修改：i 从 left+1 开始，最后把 pivot 换到中间。
3. pivot 直接取 left 值，对于接近倒序的的数组性能较差。修改：left~right 间的随机位置作为 pivot ，并换到 left

@billccn 交换 arr[i], arr[j]后下一次循环会进入 while(arr[i] < pivot) i++。真正的问题对于含有重复元素的数组排序，当 arr[i]和 arr[j]都等于 pivot 时会死循环。

大佬 强啊

@deagleWSJ 带等号就没问题了吗？