快速排序 - 理由等于检查

许多例子在网络上约快速排序（在Java中）正在接近这样的：快速排序 - 理由等于检查

private void quicksort(int low, int high) { 
    int i = low, j = high; 
    int pivot = numbers[low + (high-low)/2]; 

    while (i <= j) { 

     while (numbers[i] < pivot) { 
     i++; 
     } 

     while (numbers[j] > pivot) { 
     j--; 
     } 

     if (i <= j) { 
     exchange(i, j); 
     i++; 
     j--; 
     } 
    } 

    if (low < j) 
     quicksort(low, j); 
    if (i < high) 
     quicksort(i, high); 
}

我不解的是事情，为什么还有那些等于检查：

1）while (i <= j)代替while (i < j)

2）if (i <= j)代替if (i < j)

这里有没有任何边界情况等于关键？根据我的理解，如果我们有if(i == j)，那么我们基本上会用相同的值交换相同的值。

任何人都可以为我解决这个难题？

来源

2016-06-22 Lucas

你能发布一个这样的在线代码的链接吗？我认为你是对的，与一个元素本身交换是没有意义的 – shole

上面的代码片段实际上来自于vogella博客。 – Lucas

假设条件被i < j代替。

让我们看看会发生什么样的数组：

5,4,3,2,1

while循环将与i = 2和j = 2，并我们将不得不重复调用函数快速排序终止，这些电话将：

quicksort(0,2) and quicksort(2,4)

而如果我们确实有这个条件i<=j循环将终止于i = 4和j = 1现在我们wou ld的呼叫为：

quicksort(0,1) and quicksort(3,4)

哪些是正确的呼叫。

所以基本上你就在那里被交换相同的元素，但该代码的作者没有点必须省略，以避免添加你不需要的时候我等于Ĵ

换一个额外条件的需要

来源

2016-06-22 08:46:45

我明白了。它确实会重叠“2”索引，但它不会破坏算法到底会不会呢？你会告诉我，你会忽略上述代码中的<=个案吗？ – Lucas

是的，它肯定会破坏算法，如果我们有<而不是<=，因为快速排序分区将数组分成两个不相交的子阵列，而不与子数组重叠。 –

@Lucas我会做的唯一事情就是添加交换条件。这意味着只有当我！= j时我才会交换。 –

快速排序 - 理由等于检查

回答

相关问题