实现了快速排序,但结果很笨拙,可能有很多东西是多余的而不是最优的。所以我在谷歌上搜索并找到了一个简单的实现,好吧,它非常简单!遇到了问题。大家知道,根据算法,你可以找到中间的元素(其中一个选项),然后通过相互交换将较小的元素放在它的左边,将大的元素放在右边,然后递归地重复一切。
实现本身如下(我没有包括 swap 函数,我认为它的实现是显而易见的):
#include <iostream>
int a[] = { 65,892,2,3,78,-5,41 };
const int SIZE = sizeof(a) / sizeof(*a);
void qsort(int* mas, int s, int e) {
if (s > e) return;
int mid = mas[(s+e)/2];
int L = s, R = e;
while (L<=R) {
while (mas[L] < mid) L++;
while (mas[R] > mid) R--;
if (L <= R) {
swap(mas, L, R);
L++;
R--;
}
}
qsort(mas, e, L);
qsort(mas, s, R);
}
int main() {qsort(a, 0, SIZE-1);}
但是从源码来看这个数组序列的有趣之处,我们显然要找到中间的元素(mid = 3),然后将元素分散到较小的左边和较大的右边,然后递归应该为这两半打电话。然而,算法搞砸了:在递归调用之前第一次调用 qsort 时,数组采用以下形式:{-5, 3, 2, 892, 78, 65, 41} 也就是说,在 mid=3 的右边是应该在左边的平分。是的,这可能会在下一次递归调用中解决。但这是否违反了算法?
不,如果 L 之前的元素小于或等于枢轴,则不是违规。
Z.s. 带有无效参数的递归调用