用java实现基于快排思想的选择算法

基于快排思想的选择算法（QuickSelect），可以在未排序的数组中查找第k小的元素或第k大的元素。它的基本思想是利用快排的划分思想，每次选择一个基准元素，将数组划分为两个子数组，并判断目标元素所在的子数组在哪里，然后递归处理该子数组，直到找到目标元素。

下面是Java实现基于快排思想的选择算法的示例代码：

public static int quickSelect(int[] arr, int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }

    int pivotIndex = partition(arr, left, right);
    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    while (true) {
        while (i <= j && arr[i] < pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i >= j) {
            break;
        }
        swap(arr, i, j);
        i++;
        j--;
    }
    swap(arr, left, j);
    return j;
}

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

这段代码中，我们首先在数组arr的[left, right]范围内选择一个基准元素pivot，然后对子数组进行划分，将小于pivot的元素移到pivot左边，大于pivot的元素移到pivot右边，最后返回pivot所在的索引pivotIndex。

然后我们将目标元素的索引与pivotIndex进行比较，如果相等，直接返回目标元素。如果目标元素的索引小于pivotIndex，那么说明目标元素在左半部分，我们就在左半部分递归查找。如果目标元素的索引大于pivotIndex，那么说明目标元素在右半部分，我们就在右半部分递归查找。这样反复递归，直到找到目标元素。

最后，我们可以在主函数中调用quickSelect方法，将数组arr的范围[left, right]和目标元素的索引k传入。例如，我们可以查找数组arr中第k小的元素：

int k = 3; // 要查找第3小的元素
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int n = arr.length;
int result = quickSelect(arr, 0, n - 1, k - 1);
System.out.println(result);

输出结果为2，表示数组中第3小的元素为2。