0

そこで、修正したクイックソート アルゴリズムを使用して、「配列内で k 番目に小さい要素を見つける」を実装しました。ただし、現在は無限ループです。エラーがどこにあるのかよくわかりません。更新: デバッガーはエラーが 14 行目にあると言います: )"助けてくれてありがとう！

class kthSmallestElement {
    public static void main(String[] args) {
        int[] input = {3, 1, 5, 2, 6, 4, 7};
        int result = kthSmallestElement(input, 0, input.length-1, 3);
        System.out.println(result);
    }
    public static int kthSmallestElement(int[] arr, int start, int end, int k) {
        int j = partition(arr, start, end);
        if (j == k) return arr[j];
        if (j < k) {
            return kthSmallestElement(arr, j+1, end, k-j-1);
        }
        else {
            return kthSmallestElement(arr, start, j-1, k);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left+(right-left)/2];

        while (left <= right) {
            while (arr[left] < pivot) {
                left++;
            }
            while (arr[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        return left;
    }
}
4

2 に答える 2

0

明らかなバグ:left, right, j絶対インデックスkは相対インデックスです。と の間のすべての比較と演算はj、kで調整する必要がありますstart。

于 2013-02-20T07:55:58.357 に答える
0

これを試してください。

ありがとう、

--ジョン

    public static int kthSmallestElement(int[] arr, int start, int end, int k) {
    //int j = partition(arr, start, end);
    int j = partition2(arr, start, end);
    if (j == k)
        return arr[j];
    if (j < k) {
        // without -1 as original code.
        return kthSmallestElement(arr, j + 1, end, k - j );
    } else {
        return kthSmallestElement(arr, start, j - 1, k);
    }
}

public static int partition2(int[] arr, int lo, int hi) {
    int left = lo;
    int right = hi+1;
    int p = arr[lo];

    while (true) {
        while (arr[++left] < p) {
            if (left == hi)
                break;
        }

        while (p < arr[--right]) {
            if (right == lo) {
                break;
            }
        }

        if (left >= right) {
            break;
        }

        exchange(arr, left, right);
    }

    exchange(arr, lo, right);
    return right;
}
于 2014-04-07T21:41:31.457 に答える