1

l が返される正しい値であり、 l=lowの初期化がどのように行われるかを不変式からどのように理解できますか。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;
      }
4

1 に答える 1

1

まず、アレイを2つの部分に分割します。中央の要素を選択してから、すべての要素を左側にx小さく移動します。これにより、残りのすべての右側の要素が。より大きくなります。xx

完了xすると、正しい位置になります。ここで、左セグメントと右セグメントに対して別々に同じメソッドを呼び出します。

このように、highとlowは、セグメントのlowerとupperインデックスを表します。たとえば、配列のサイズが（index = 3）の位置10にある場合、最初のサブリストでは、low = 0、high=2になります。x4

同様に、2番目のサブリストの場合、low=4およびhigh=9です。

于 2012-12-02T02:58:22.237 に答える