java - Java kthSmallestElement 使用快速排序无限循环错误

Question

所以我使用修改后的快速排序算法实现了“查找数组中第 k 个最小的元素”。但是，现在它是无限循环。我不太确定错误在哪里。更新：调试器说错误在第 14 行：“return kthSmallestError(arr, start, j-1, k); 根据打印语句，(start, j-1, k) 值为 (3, 3, 0 ）”感谢您的帮助！

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;
    }
}

Answer 1

请试试这个。

谢谢，

- 约翰

    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;
}

Answer 2

一个明显的错误：left, right, j绝对索引k是相对的。和 之间的所有比较和算术运算j都应k由 校准start。