找出列表中第n小的数 Java程序

找出列表（数组或ArrayList）中第n小的数，可以使用多种算法实现，如选择排序、快速选择等。这里提供一种基于Java的简单快速选择算法示例：

import java.util.ArrayList;
import java.util.Random;

public class KthSmallestElement {
    public static int findKthSmallest(ArrayList<Integer> nums, int k) {
        if (nums == null || nums.size() < k) {
            throw new IllegalArgumentException("Invalid input");
        }

        return quickSelect(nums, 0, nums.size() - 1, k);
    }

    private static int quickSelect(ArrayList<Integer> nums, int left, int right, int k) {
        if (left == right) {
            return nums.get(left);
        }
        
        // 随机选取pivot的位置
        Random rand = new Random();
        int pivotIndex = rand.nextInt(right - left + 1) + left;

        // 将pivot放到中间位置
        swap(nums, pivotIndex, right);

        int partitionIndex = partition(nums, left, right);
        if (partitionIndex == k - 1) {
            return nums.get(partitionIndex);
        } else if (partitionIndex > k - 1) {
            return quickSelect(nums, left, partitionIndex - 1, k);
        } else {
            return quickSelect(nums, partitionIndex + 1, right, k);
        }
    }

    private static void swap(ArrayList<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    private static int partition(ArrayList<Integer> nums, int left, int right) {
        int pivotValue = nums.get(right);
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (nums.get(j) <= pivotValue) {
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, right);
        return i + 1;
    }

    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>();
        nums.add(5);
        nums.add(3);
        nums.add(9);
        nums.add(1);
        nums.add(7);
        int n = 3;
        System.out.println("The " + n + "th smallest element is: " + findKthSmallest(nums, n));
    }
}

这个例子中，`findKthSmallest`方法接受一个整数列表和一个整数k作为输入，然后通过递归地调用`quickSelect`来找到第k小的元素。