如何用Java查找数组中的第k小的数？附非pivot-index基础版代码

这是一个不依赖 pivot 索引的基础实现，核心逻辑是通过反复定位并移除当前数组的最小值，直到找到目标的第k小元素：

class Func {
    int kthSmallest(int arr[], int smallestIndex, int size) {
        // 定位当前数组的最小值及其位置
        int smallest = arr[0];
        int removeLocation = 0;
        for(int i = 0; i < size; i++){
            if(arr[i] < smallest){
                smallest = arr[i];
                removeLocation = i;
            }
        }
        
        // 通过元素前移的方式移除找到的最小值（修正了原代码的越界问题）
        for(int i = removeLocation; i < size - 1; i++){
            arr[i] = arr[i+1];
        }
        
        // 递归终止条件：找到第1小元素时直接返回
        if(smallestIndex == 1) {
            return smallest;
        } 
        // 递归查找第k-1小元素，数组有效长度减1
        else {
            return kthSmallest(arr, smallestIndex - 1, size - 1);
        }
    }
}

关键细节说明： #

• 工作流程：每次递归都会找出当前数组的最小值，然后通过覆盖的方式“删除”这个最小值，接着递归查找第smallestIndex-1小的元素，直到目标索引为1时返回结果。
• 代码修正：原代码的第二个循环存在数组越界风险（当i等于size-1时，arr[i+1]会访问数组范围外的位置），这里调整为i < size - 1，避免了越界异常。
• 性能特点：这种实现的时间复杂度为O(nk)，在数组规模较大或者k值接近数组长度时，效率会比较有限，更适合处理小规模数组的场景。

内容的提问来源于stack exchange，提问作者jwkoo