java quickselect

import java.util.Random;

public class QuickSelect {

    // 快速选择算法，用于在无序数组中找到第 k 小的元素
    public static int quickSelect(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        Random random = new Random();
        while (true) {
            if (left == right) return nums[left];
            int pivotIndex = left + random.nextInt(right - left + 1);
            pivotIndex = partition(nums, left, right, pivotIndex);
            if (pivotIndex == k - 1) {
                return nums[pivotIndex];
            } else if (pivotIndex > k - 1) {
                right = pivotIndex - 1;
            } else {
                left = pivotIndex + 1;
            }
        }
    }

    // 分区函数，返回枢轴索引
    private static int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, right);
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex);
        return storeIndex;
    }

    // 交换数组中的两个元素
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 测试代码
    public static void main(String[] args) {
        int[] nums = {9, 3, 2, 7, 6, 4, 8, 5, 1};
        int k = 4;
        System.out.println("The " + k + "-th smallest element is: " + quickSelect(nums, k));
    }
}

解释说明

1. 快速选择算法：quickSelect 函数用于在无序数组中找到第 k 小的元素。它使用了类似快速排序的分区思想，但只递归处理包含目标元素的那一部分。

2. 分区函数：partition 函数将数组分为两部分，一部分小于枢轴元素，另一部分大于或等于枢轴元素，并返回枢轴元素的最终位置。

3. 交换函数：swap 函数用于交换数组中的两个元素。

4. 测试代码：main 函数提供了一个示例数组和一个 k 值，展示了如何使用 quickSelect 函数来找到第 k 小的元素。