减治法java求数组中第k小的元素的完整代码

在Java中，我们可以使用一种叫做“快速选择”（QuickSelect）的算法来求解数组中第K小的元素，这是一种基于分治思想的选择排序变种，时间复杂度可以达到平均O(n)。以下是使用减治法的简化版代码：

import java.util.Random;

public class QuickSelect {
    public static int findKthSmallest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 1 || k > nums.length) {
            throw new IllegalArgumentException("Invalid input");
        }
        
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private static int partition(int[] nums, int left, int right) {
        int pivotIndex = left + (right - left) / 2;
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, right); // Move pivot to the end

        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, i, storeIndex);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, right); // Move pivot to its final position
        return storeIndex;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) { // Base case: single element or empty array
            return nums[left];
        }

        int pivotIndex = partition(nums, left, right);

        // If k is at the pivot's place, we found it
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            // Recurse on the left subarray
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            // Recurse on the right subarray
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

    public static void main(String[] args) {
        int[] nums = {7, 10, 4, 3, 20, 15};
        int k = 2;
        System.out.println("The " + k + "th smallest element is: " + findKthSmallest(nums, k));
    }
}

在这个例子中，`findKthSmallest`函数是主入口，它调用了递归的`quickSelect`方法，通过不断地划分数组并缩小搜索范围找到第K小的元素。