C＃while循环不退出（quicksort）

由于某种原因，我的while循环（i < = j）不会在j比i更低时结束。C＃while循环不退出（quicksort）

我观察了调试值，并且已经多次看到（4,3），（6,5）等的i和j（分别）的值。

public static List<Item> QuickSort(List<Item> a, int left, int right) 
{ 
    int i = left; 
    int j = right; 
    double pivotValue = ((left + right)/2); 
    Item x = a[Convert.ToInt32(pivotValue)]; 
    Item w; 
    while (i <= j) 
    { 
     //these while loops continue looping after i<=j is false 
     while (a[i] < x) 
     { 
      i++; 
     } 
     while (x < a[j]) 
     { 
      j--; 
     } 
     if (i <= j) 
     { 
      w = a[i]; 
      a[i++] = a[j]; 
      a[j--] = w; 
     } 
    } 
    if (left < j) 
    { 
     QuickSort(a, left, j); 
    } 
    if (i < right) 
    { 
     QuickSort(a, i, right); 
    } 
    return a; 
}

来源

2014-03-27 user3470510

这是一个遗憾...... – JustAndrei

我不相信'while while'坏了。继续调试。也许这是递归？ – Benesh

它永远不会去递归。这发生在第一遍。 – user3470510

我敢打赌，它要么递归或内部的一个while循环了仍在继续。我没有记忆快速排序算法，但我敢打赌，如果你在调试器中闯入，你会发现自己处于两个内部while循环之一中。

来源

2014-03-27 21:59:49

除了'a [pivotValue]'保证会破坏这些内部循环，因为它不会大于或小于它自己（当'i'或'j'等于'pivotValue'时] – Sam

它确实通过（a [i ] user3470510

x有什么价值？ –

编码quicksort是一个非常好的练习，它不像看起来一切正常一样容易！ ;）

这是您的代码有一个问题。考虑如果j碰撞到关键点会发生什么，而i不会。您将数据透视表（j）与i的数值进行交换，并通过数据透视表增加i。这不能继续正确（如果你理解Quicksort，你应该明白为什么）。

选择支点后，我喜欢与一个约束（无论是left或right）更换它，去交换价值，直到i和j见面，然后把支点回到了这个地方。当然还有其他方法。

来源

2014-03-27 22:22:27 jods

这不是一个无限循环。

while (a[i] < x) 
    { 
     i++; 
    }

如果x在列表中人数最多的，这将提高“我”只要阵列是超出范围，和PROGRAMM将抛出一个OutOfRangeException。

来源

2014-03-27 22:22:38 hash

这并不能解释所有事情......因为'i'开始时等于'left'和'left <= pivot' by construction，'while（a [i] jods

如果i==j和a[i]==x ...会发生什么？没有增量，没有减量，只是交换和继续...

考虑将while(i<=j)更改为while(i<j)。如果i==j ...

来源

2014-04-04 21:36:41 CiaPan

C＃while循环不退出（quicksort）

回答

相关问题