更改元素等于在快速排序中的枢轴

Question

为什么快速排序更改（在分区空白中）具有与枢轴相同的值的元素会有好处？

我被问到，但我不知道为什么......也许因为如果他们不改变，数组可能会保持无序？

1 3 5 [3] 2 6 
    i  j  swap to 

1 3 2 [3] 5 6 

由于某种原因，它会再进行更换？我不知道...

我想知道为什么交换与枢轴相同的值的元素是一件好事。

Answer 1

考虑这个数组：int[] array = {1, 2, 4, 3, 4};

枢轴可能是array[2] = 4，如果我们通过计算(low + high)/2

现在选择它，让我们考虑，我们不换数组元素当元素等于转动的情况。我们将陷入无限循环并得到StackOverflowError。

private int partition(int[] array, int left, int right){ 
    int pivot = array[(left + right)/2]; 
    while(left <= right){ 
     while(array[left] <= pivot) // CAUSES INFINITE LOOP. Should be array[left] < pivot 
      left++; 
     while(array[right] > pivot) 
      right--; 

     if(left <= right){ 
      swap(left, right, array); 
      left++; 
      right--; 
     } 
    } 

    return left; 
}