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

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 867 days ago, the information mentioned may be changed or developed.

华为云前几天公测了类 Github Copilot 的 CodeArts Snap 产品，并发了篇公众号文章展示其强大能力。

先略过其中生成的测试用例 assertEqual(bin_to_octact("101",8)) 等等低级槽点以外，考考各位 V 友，CodeArts Snap 生成的这段快排是正确的吗？哪里错了？如何改正？

//快速排序算法代码
void quickSort(int left, int right, vector<int>& arr) {
    int i = left, j = right;
    int pivot = arr[left];
    while(i < j)
    {
        if(i < j)
        while(arr[i] < pivot) i++;
        while(arr[j] > pivot) j--;
        if (i < j)
        {
            swap(arr[i], arr[j]);
        }
    }
    if(left < j)
        quickSort(left, j, arr);
    if(i < right)

公众号原图

Supplement 1 · Jan 5, 2024

发完贴以后华为云公众号终于把错误的快排给撤下来了哈哈，但不知为何依然把满是错误的 bin_to_octave 的测试用例那张图留着，按说 bug 密度显然是那张图更高吧？

Supplement 2 · Jan 5, 2024

bin_to_octal
写了两遍都写错了，我检讨

19 replies • 2024-01-05 18:43:33 +08:00

stevenshuang

Jan 4, 2024 via iPhone

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

joh

Jan 5, 2024 via Android

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

samhjn

Jan 5, 2024 via iPhone

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

samhjn

Jan 5, 2024 via iPhone

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

hemingqiao

Jan 5, 2024

```
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(arr[i], arr[j]);
}
qsort(arr, l, j), qsort(arr, j + 1, r);
}
```

samhjn

Jan 5, 2024 via iPhone

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

billccn

Jan 5, 2024

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

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

dif

Jan 5, 2024

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

hemingqiao

Jan 5, 2024

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

AntiFraud

Jan 5, 2024

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); // 对右半部分进行快速排序
}

hemingqiao

Jan 5, 2024

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

samhjn

Jan 5, 2024 via iPhone

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

samhjn

Jan 5, 2024 via iPhone

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

joh

Jan 5, 2024

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

tramm

Jan 5, 2024

@dif 有道理

deagleWSJ

Jan 5, 2024

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

deagleWSJ

Jan 5, 2024

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

qwertty01

Jan 5, 2024

大佬强啊

samhjn

Jan 5, 2024 via iPhone

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