通过随机枢轴法找到第 K 分钟.一些奇怪的错误

Question

我尝试使用"随机枢轴"方法来查找给定数组
中的第 K 分钟。[代码]

public class FindKthMin {
// Find the Kth min elem by randomized pivot.
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int tempElem = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = tempElem;
}
private static int partition (int[] givenArray, int start, int end, int pivotIndex) {
    // Debug:
    //System.out.println("debug: start = " + start);
    //System.out.println(">> end = " + end);
    //System.out.println(">> pivotIndex = " + pivotIndex);

    int pivot = givenArray[pivotIndex];
    int left = start - 1;
    int right = end;
    boolean hasDone = false;
    while (!hasDone) {
        while (!hasDone) {
            left ++;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[left] >= pivot) {
                // Exchange givenArray[left] and the givenArray[right].
                exchange(givenArray, left, right);
                break;
            }
        }
        while (!hasDone) {
            right --;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[right] < pivot) {
                // Exchange the givenArray[right] and the givenArray[left].
                exchange(givenArray, right, left);
                break;
            }
        }
    }
    givenArray[right] = pivot;
    // Debug:
    //System.out.println(">> split = " + right);
    //System.out.println();
    return right;
}
private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = (int)(start +  Math.random() * (end - start + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition(givenArray, start, end, rand);
    if (k == split + 1) return givenArray[split];
    else if (k < split + 1) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split + 1, end, k);
}
public static int findKthMin_RanP (int[] givenArray, int k) {
    int size = givenArray.length;
    if (k < 1 || k > size) return -1;
    return findKthMin_RanP_Helper(givenArray, 0, size - 1, k);
}

// Main method to test.
public static void main (String[] args) {
    // Test data: {8, 9, 5, 2, 8, 4}.
    int[] givenArray = {8, 9, 5, 2, 8, 4};
    // Test finding the Kth min elem by randomized pivot method.
    System.out.println("Test finding the Kth min elem by randomized pivot method, rest = " + findKthMin_RanP(givenArray, 1));
}
}

但结果是不稳定的，有时是对的，有时是错的。
请看第 5 行findKthMin_RanP_Helper方法：
如果我将此int split = partition(givenArray, start, end, rand);更改为 int split = partition(givenArray, start, end, end); ，结果总是正确的。
我真的找不到这有什么问题。

---

编辑：
问题来自"分区"，新分区应该是这样的：

    private static int partition_second_version (int[] givenArray, int start, int end, int pivotIndex) {
    int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left <= right) {
        while (givenArray[left] < pivot) left ++;
        while (givenArray[right] > pivot) right --;
        if (left <= right) {
            // Exchange givenArray[left] and givenArray[right].
            exchange(givenArray, left, right);
            left ++;
            right --;
        }
    }
    return left;
}

findKthMin_RanP_Helper应该像这样更改：

    private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = start +  (int)(Math.random() * ((end - start) + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition_second_version (givenArray, start, end, rand);
    if (k == split) return givenArray[split - 1];
    else if (k < split) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split, end, k);
}

Answer 1

您的分区例程可以简化...

  private static int partition(int[] givenArray, int start, int end, int pivotIndex) {
    final int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left < right) {
        while (left < givenArray.length && givenArray[left] <= pivot) {
            left++;
        }
        while (right > -1 && givenArray[right] > pivot) {
            right--;
        }
        if (left >= right) {
            break;
        }
        exchange(givenArray, right, left);
    }
    return right;
}

我在你的代码中看到的一个错误是你的分区例程。在第一次交换调用中，不能保证正确的索引始终指向<枢轴的值。>