我有这样的东西,我想把第一个元素作为pivot。为什么这个程序仍然不起作用?
void algSzyb1(int tab[],int l,int p)
{
int x,w,i,j;
i=l; //l is left and p is pivot, //i, j = counter
j=p;
x=tab[l];
do
{
while(tab[i]<x) i++;
while(tab[j]>x) j--;
if(i<=j)
{
w=tab[i];
tab[i]=tab[j];
tab[j]=w;
i++;
j--;
}
}
while(!(i<j));
if(l<j) algSzyb1(tab,l,j);
if(i<p) algSzyb1(tab,i,p);
}
查看代码,而不是真正检查它的功能,只查看单个行,这一行很突出:
while(!(i<j));
我看着那条线,心想:这附近有个虫子。我实际上还没有看过代码,所以我不知道错误是什么,但我看了这一行,它看起来是错误的。
我认为在递增I之前需要递减j。
while (tab[j]>x ) j--;
while (tab[i]<x && i < j) i++;
此外,我添加了一个额外的条件,以确保我不会扫过j。(未初始化的内存读取)。
pivot的名称有点错误,因为最终结果是一个排序的元素,但this和wikipedia页面:quicksort都将pivot移动到更高的分区中,并且不能保证项目位于正确的位置。
结束条件是当你扫过列表时
while( i < j ); /* not !(i<j) */
在搜索结束时,您需要测试一个较小的集合。您创建的代码出现堆栈溢出,因为它重复尝试相同的测试。
if (l<j) algSzyb1(tab, l, j);
if (j+1<p) algSzyb1(tab, j+1, p);
全代码
void algSzyb1(int tab[], int l, int p)
{
int x, w, i, j;
i = l;
j = p;
x = tab[l]; //wróć tu później :D
do
{
while (tab[j]>x ) j--;
while (tab[i]<x && i < j) i++;
if (i < j)
{
w = tab[i];
tab[i] = tab[j];
tab[j] = w;
i++;
j--;
}
} while ((i<j));
if (l<j) algSzyb1(tab, l, j);
if (j+1<p) algSzyb1(tab, j+1, p);
}