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

基于快排思想的选择算法（QuickSelect）是一种寻找无序数组中第 k 小（或第 k 大）元素的算法。其基本思想是：快速排序每次将数组分为两个部分，左边部分小于等于右边部分，因此我们可以利用这一特性来寻找第 k 小元素。

以下是基于快排思想的选择算法的Java实现：

public static int quickSelect(int[] arr, int k) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int pivotIndex = partition(arr, left, right);
        if (pivotIndex == k - 1) {
            return arr[pivotIndex];
        } else if (pivotIndex < k - 1) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
    return -1; // 表示未找到第 k 小元素
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
        if (arr[i] <= pivot) {
            i++;
        } else if (arr[j] > pivot) {
            j--;
        } else {
            swap(arr, 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;
}

在上述代码中，我们定义了一个 `quickSelect` 方法，该方法接收两个参数，一个是无序数组 `arr`，另一个是第 k 小元素的位置 `k`。首先，我们定义两个指针 `left` 和 `right`，分别指向数组的左端和右端。然后，我们进入循环，每次调用 `partition` 方法将数组分为两个部分，并返回枢轴元素的下标 `pivotIndex`。如果 `pivotIndex` 等于 `k - 1`，则找到了第 k 小元素，返回其值；如果 `pivotIndex` 小于 `k - 1`，则第 k 小元素在枢轴元素的右侧，将 `left` 指针指向 `pivotIndex + 1`；如果 `pivotIndex` 大于 `k - 1`，则第 k 小元素在枢轴元素的左侧，将 `right` 指针指向 `pivotIndex - 1`。最后，如果循环结束仍未找到第 k 小元素，则返回 `-1`。

在 `quickSelect` 方法中，我们调用了 `partition` 方法，将数组分为两个部分。`partition` 方法的实现与快速排序类似，首先选定一个枢轴元素 `pivot`（这里我们选取数组的左端元素），然后定义两个指针 `i` 和 `j`，分别指向数组的左右两端。循环中，我们将 `i` 指针向右移动，直到找到第一个大于枢轴元素的元素；将 `j` 指针向左移动，直到找到第一个小于等于枢轴元素的元素；然后交换 `i` 和 `j` 指向的元素，使得左侧元素小于等于枢轴元素，右侧元素大于枢轴元素。重复以上步骤，直到 `i` 指针超过 `j` 指针，此时将枢轴元素与 `j` 指针指向的元素交换位置，使得枢轴元素左侧元素小于等于它，右侧元素大于它，然后返回 `j` 的值作为枢轴元素的下标。