java - 循环不变量快速排序

Question

我如何从不变量中理解 l 是要返回的正确值以及如何初始化l=low ; 和h=high ; 建立不变量？

/* 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就在正确的位置。现在您分别为左右线段调用相同的方法。

这种方式high和low代表了段的lower和upper索引。例如，如果您的数组大小是10并且x最终位于位置4（索引 = 3），那么对于第一个子列表，低 = 0，高 = 2。

同样对于第二个子列表，low=4 和 high=9。