快速排序C++的第一个元素作为枢纽

我有这样的事情，我想有第一个元素作为枢轴。为什么这个程序仍然不起作用？快速排序C++的第一个元素作为枢纽

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); 
}

来源

2015-12-19 Marek

此代码是让人毛骨悚然。 – Rabbid76

使用**变量的有意义的名称**并在每个复杂表达式之前使用**注释**以阐明其用法。这将使您的代码易于阅读和更正。 – Ziezi

如果你不知道代码在做什么，那么使用有意义的注释。 – gnasher729

看代码，而不是真的检查它做什么，只是看着各行，这一行中脱颖而出：

while(!(i<j));

我看着那行，我想：有是一个地方在这里的错误。我没有看到代码，所以我不知道这个bug是什么，但是我看着这一行，看起来不对。

来源

2015-12-19 12:10:45 gnasher729

你知道这不是一个独立的while语句，而是它控制着它上面的do循环吗？（尽管如此，但也许出于不同的原因。） –

我认为你需要在增加i之前递减j。

while (tab[j]>x) j--; 
    while (tab[i]<x && i < j) i++;

而且我还增加了一个额外条件，以确保我不扫过去学家（未初始化的内存读取）。

由于最终结果是排序的元素，因此数据透视会稍微错误，但是这和wikipedia page : quicksort都将数据透视图移到了较高的分区，并且不保证该项目位于正确的位置。

结束条件是当你已经在列表中

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); 
}

来源

2015-12-19 12:18:56 mksteve

快速排序C++的第一个元素作为枢纽

回答

相关问题