这是一个创建于 322 天前的主题，其中的信息可能已经有所发展或是发生改变。
华为云前几天公测了类 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)
第 1 条附言 · 321 天前
发完贴以后华为云公众号终于把错误的快排给撤下来了哈哈，但不知为何依然把满是错误的 bin_to_octave 的测试用例那张图留着，按说 bug 密度显然是那张图更高吧？
第 2 条附言 · 321 天前
bin_to_octal
写了两遍都写错了，我检讨
写了两遍都写错了，我检讨
 |
1
stevenshuang 322 天前 via iPhone
8 1 2 3 8
while 就是死循环了吧，i 和 j 都动不了 |
 |
2
joh 321 天前 via Android
While 死循环，而且 while 里面第一个 if 有啥意义么…他在循环内部更改了 arr ，但是没有更新 pivot 数值。
|
 |
4
samhjn OP @stevenshuang 是会死循环没错，那这份代码和正确的版本之间差了什么呢？
|
 |
5
hemingqiao 321 天前
```
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); } ``` |
|
6
samhjn OP @hemingqiao 这个版本显然也是有问题的，举个简单的反例：100 1 这种长度为 2 的逆序数组
|
 |
7
billccn 321 天前
@hemingqiao Quick sort 里面 pivot 在左边、右边、中间都可以的。
真正的问题是`int i = left`这里，这把 pivot 也放进去了，那 `while(arr[i] < pivot) i++;` 一次也不会进循环体。 |
 |
8
dif 321 天前
说不定在鸿蒙系统上就是正确的呢？手动狗头。
|
|
9
hemingqiao 321 天前
@samhjn 你跑一下试试呢？我在 leetcode 上的 912 提交通过之后才贴上来的
|
 |
10
AntiFraud 321 天前
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); // 对右半部分进行快速排序 } |
|
11
hemingqiao 321 天前
@billccn 是啊，他贴的这个是有问题的
|
|
12
samhjn OP @hemingqiao 看错了抱歉，没注意到左右游标已经预先补偿了
|
 |
16
deagleWSJ 321 天前
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 |
|
17
deagleWSJ 321 天前
@billccn 交换 arr[i], arr[j]后下一次循环会进入 while(arr[i] < pivot) i++。真正的问题对于含有重复元素的数组排序，当 arr[i]和 arr[j]都等于 pivot 时会死循环。
|
 |
18
qwertty01 321 天前
大佬 强啊
|
Select Language