-5 
/**
     * Sort an array in ascending order
     * @param arr array to sort
     */
    public static void quickSort(int[] arr){
        qs(arr, 0, arr.length);
    }

/**
     * Sort a region of an array in ascending order.
     * Elements outside the given region are unchanged.
     * requires: 0 <= start <= end <= arr.length
     * @param arr   array to sort
     * @param start start of region (inclusive)
     * @param end   end of region (exclusive)
     */
    private static void qs(int[] arr, int start, int end){
        if (end <= start+1){    //region of length 0 or 1
            return;
        }
        int x = arr[start];
        int p = partition(arr, start+1, end, x);
            //now swap arr[start] with arr[p-1]
        arr[start] = arr[p-1];
        arr[p-1] = x;
        qs(arr, start, p-1);
        qs(arr, p, end);



    }

    /**
     * Partition a region of an array.
     * Rearranges elements in region so that small ones
     *   all have smaller indexes than the big ones.
     * Elements outside the region are unchanged.
     * requires: 0 <= start <= end <= arr.length
     * @param arr   array to partition
     * @param start start of region (inclusive)
     * @param end   end of region (exclusive)
     * @param x     pivot - "small" and "big" are <x, >=x.
     * @return      start index (inclusive) of big elements
     *              in region after partition.
     */
    private static int partition(
        int[] arr, int start, int end, int x)
    {

        int l = start -1, r = end+1;
        while (true) {
            while (l < end && arr[++l] < x) ;

            while(r> l && arr[--r] >x);// find smaller item

                if(l >= r) // if pointers cross,
                    break; // partition done
                    else  {
                        int temp;
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        return l;
        }


    public static void main(String[] args) {
        int[] a = {15,8,9,6,2,8,8,5,8,4,2};
        quickSort(a);
        for (int i = 0; i < a.length; i++){
            System.out.print(" "+a[i]);
        }
    }
}

partitionメソッドの間違いは何ですか？

4

1 に答える 1

2

いくつかの重要な事実を強調しましょう。

 * @param end   end of region (exclusive)
                               ^^^^^^^^^

 * @param x     pivot - "small" and "big" are <x, >=x.
 * @return      start index (inclusive) of big elements
 *              in region after partition.
 */
private static int partition(
    int[] arr, int start, int end, int x)
{

    int l = start -1, r = end+1;
                      ^^^^^^^^^^

    while (true) {
        while (l < end && arr[++l] < x) ;
               ^^^^^^^^^^^^^^^^^^^^^^^

        while(r> l && arr[--r] >x);// find smaller item
                      ^^^^^^^^

配列全体が分割されている場合は、endですarr.length。次に、設定し、ループが取る限りend = arr.length + 1低いインデックスをインクリメントした後、それが発生しなかった場合（ピボットが配列内の最大要素である場合にアクセスしようとしている場合）、アクセスしようとする最初の配列要素次のループはです。それは. を発生させます。lArrayIndexOutOfBoundsExceptionarr[end]arr[arr.length]ArrayIndexOutOfBoundsException

したがって、AIOBE を確実に入手できますpartition。

ループコントロールを次のように設定r = endおよび変更できます

while(++l < r && arr[l] < x)

と

while(r-- > l && arr[r] > x)

qs(arr, 0, arr.length -1)または、より高いインデックスも包括的に作成してから呼び出すことができますmain。

于 2012-12-01T01:34:13.973 に答える