更改元素等於在快速排序中的樞軸

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