0

JavaでQuickSortアルゴリズムを実装しようとしています。しかし、コードを実行すると、StackOverFlowExceptionの実行時例外が発生します。境界がめちゃくちゃになっている理由がわからないようです。これがコードです。

import java.util.Scanner;

class QuickSortOne
{
public static void main(String args[])
{
    int a[], n;

    Scanner sn = new Scanner(System.in);

    n = sn.nextInt();
    a = new int[n];
    for (int i = 0; i < n; i++)
    {
        a[i] = sn.nextInt();
    }

    QuickSort(a, 0, n-1);


    for (int i = 0; i < n; i++)
        System.out.println(a[i] + " ");

}

public static void QuickSort(int a[], int l, int r)
{
    if (l < r) //Checking for Base Case
    {
        int p = Partition(a, l, r);
        QuickSort(a, l, p);
        QuickSort(a, p+1, r);
    }
}

public static int Partition(int a[], int l, int r)
{
    int p = a[l];
    int i = l+1;
    for (int j = l+1; j <= r; j++)
        if (a[j] < p)
        {
            int temp = a[j];
            a[j] = p;
            p = temp;
            i++;
        }
    int temp = a[i-1];
    a[i-1] = p;
    p = temp;
    return i;
}
}
4

1 に答える 1

0

分割方法は従来の分割方法とほとんど似ていないため、このアルゴリズムのソースを確認する必要があります。

あなたは間違いなくその場で分割しようとしているので、ウィキペディアでこれのインプレースバージョンを見て、そこで説明されていることを試してみてください.

さらに、パーティションが機能するようになると、ピボットが配置され、そのインデックスが再帰呼び出しでスキップされる可能性がありますが、これは再帰では実行されません。

于 2012-07-01T19:59:20.933 に答える