我的quicksort桌面测试似乎不正确

Question

我目前正在练习quicksort，它现在工作得很好。但我可以找到一个失败的例子（因为它似乎是一个特例，我还没有读过它，这就是为什么我做错了......不能解决它）。问题是，我想是因为我选择最小的元素作为主元：

9 1 4 2 7 *0* (star mark means pivotelement) 

现在我设定i,j哪里i将通过阵列（右移），直到它发现它比主元以上的元素。并且j将通过Array（向左移动）直到找到一个低于枢纽元素的元素。找到了，我们切换i和j显示的元素。我们这样做直到i和j交叉（又名“j在i”之前）。在这种情况下，我们切换元件i节目并索引i与主元......我现在不想描述整个算法也将是长期的问题..

9 1 4 2 7 *0* 
i  j  but now we cannot find a j that is lower than Pivotelement. What we do? 
       I would continue by switching i with pivotelement: 

*0* 1 4 2 7 9 
      j i But now is the Problem that i and j are in other positions 
       (j is before i). I have no idea.. Please clarify and help.. 

Answer 1

你有什么好，你已经成功地转动了。

枢轴处于正确的位置，枢轴的两侧满足条件：左侧的所有元素都较少，右侧的所有元素都较大。 i指数在关键点的最后一步移动时处于不利的位置，但您不会在乎您打破了这一点，因为无论如何您都完成了它。现在你递归并快速排序枢轴的左侧和右侧 - 除了没有左侧，所以在这个角落的情况下，你只是递归到右侧。

Answer 2

快速排序工作在分区的概念。在每次迭代中，它会拾取一个pivot元素，并尝试将其放置在最终放置的位置。

开始时i指针始终保持在索引-1（这显然是不可能的，所以我们只给它赋值-1，并且只在我们增加它之后引用一个数组元素）。

所以在您的情况你得到的第一个循环之后，

0 1 4 2 7 9

这是所选择的转动部件的正确位置。

说明：由于i最初是在-1，你递减j指针，直到你得到小于当前的主元（0）的元素。这将j一直带到索引0（您需要将这些条件添加到代码中以确保没有非法内存空间被访问）。

最后i+1（其中i仍然是-1）被替换为pivot元素，所以有效的9被替换为0和viola！

有关更全面的解释，请参阅this链接。