1

クイックソートアルゴリズムを作成しようとしています。次のコードを見てください。

public static void quickSort(int[] tab, int lowIndex, int highIndex) {
    if (tab.length == 0 || tab == null) {
        return;
    }

    int i = lowIndex;
    int j = highIndex;

    int pivot = tab[tab.length / 2];

    while (i <= j) {
        while (tab[i] < pivot) {
            i++;
        }
        while (tab[j] > pivot) {
            j--;
        }

        if (i <= j) {
            int c = tab[i];
            tab[i] = tab[j];
            tab[j] = c;
            i++;
            j--;
        }

        if (lowIndex < j) {
            quickSort(tab, lowIndex, j); // error !!!
        }
        if (i < highIndex) {
            quickSort(tab, i, highIndex);
        }
    }

}

問題は、スレッド「メイン」での例外 java.lang.StackOverflowError です。なにが問題ですか ？

4

1 に答える 1

3

これは間違っています：

int pivot = tab[tab.length / 2];

でグローバルにではなく、提供されたスライスでピボットを見つける必要がありますtab。

int pivot = tab[lowIndex + (highIndex - lowIndex)/ 2];

また、再帰を終了する条件が間違っています。テーブルの長さは変わりません。かどうかを確認する必要がありますlowIndex >= highIndex

于 2013-02-15T21:41:41.973 に答える