java - 选择排序算法

Question

下面是选择排序算法的一个实现，用于查找数组中第K小元素之前的元素。有时这个程序运行良好，但有时会由于堆栈溢出错误而失败(代码片段下方的错误)

public static int rand(int left, int right){
    return left+(int)(Math.random()*(double)(right-left));
}

public static int rank(int[] array, int left, int right, int rank){
    int pivot = rand(left, right);  
    int leftend = partition(array, left, right, array[pivot]);

    int size = leftend - left +1;
    if(size == rank+1){
        for(int i=0; i<=leftend; i++)
        System.out.print(array[i]+" ,");
        return 0;
    }else if(size > rank)
        return rank(array, left, leftend, rank);
    else return rank(array, leftend+1, right, rank - size);

}   

public static int partition(int[] array, int left, int right, int pivot){
    while(true){
        while(left <= right && array[left] <= pivot)
            left++;

        while(right >= left && array[right] > pivot)
        right--;

        if(left > right)
        return left-1;

        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

 }

错误:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Random.nextDouble(Random.java:409)
    at java.lang.Math.random(Math.java:712)
    at mod.rand(mod.java:12)
    at mod.rank(mod.java:16)
    at mod.rank(mod.java:25)

我认为可能是 rand() 导致了这个问题，但我不确定。我也不知道如何修复它。

Answer 1

我假设您希望您的 rand 方法返回介于左(含)和右(含)之间的数字。但是，Math.random() 方法返回 0.0(含)和 1.0(不含)之间的数字。因此，在被评估的子数组的大小为 2 的情况下(即:left=4 和 right=5)，rand 函数将只能返回 4 作为结果。尝试在 rand 函数中更改这一行以确保它可以包含上限:

return left+(int)(Math.random()*(double)(right-left));

对于

return left+(int)(Math.random()*(double)(right-left + 1));