循環不變式快速排序

Question

我如何從不變量中得知l是要返回的正確值以及如何初始化l =低;和h =高;建立不變式？

/* invariant 
     * low <= l <= h <= high 
     * In region for indexes i with low <= i < end: 
     * elements are as originally, but rearranged. 
     * if i < l then arr[i] < x 
     * if i >= h then arr[i] >= x 
     * Elements outside region are unchanged. 
     */ 

private static int partition(int[] arr, int low, int high, int x) 
{ 
     int l = low; 
     int h = high; 
     while (l<h) 
     { 
      if (arr[l] < x)  
       l =l +1; 
      else 
      {       
       int x = arr[l]; 
       arr[l] = arr[h-1]; 
       arr[h-1] = x 
       h = h-1; 
      } 
     } 
     return l; 
     } 

Answer 1

您正在將數組分成兩部分開始。您選擇中間元素x，然後您將左側的所有元素縮小爲x，這樣所有剩餘的正確元素將變得大於x。

一旦完成，x是在其正確的位置。現在您分別爲左側和右側段調用相同的方法。

這種方式的高和低表示段的索引lower和upper。例如如果數組的大小是10和x結束了在位置4（索引= 3）然後第一子列表中，低= 0，高= 2

類似地，對於第二子列表中，低= 4和高= 9。