Java实现快速选择算法

简介

快速选择算法（Quickselect Algorithm）是一种在数组中查找第 k 小元素的高效算法。它基于快速排序（Quick Sort）的分治思想，但只需要处理划分后的一部分子数组，而不是对整个数组进行排序，因此平均情况下时间复杂度为 O(n)，比排序后再找第 k 小元素的方法要快很多。本文将详细介绍如何用 Java 实现快速选择算法，并探讨其使用方法、常见实践以及最佳实践。

目录

基础概念
Java 实现快速选择算法
使用方法
常见实践
最佳实践
小结
参考资料

基础概念

快速选择算法的核心思想与快速排序类似，都是通过选择一个基准元素（pivot），将数组分为两部分：一部分元素小于等于基准元素，另一部分元素大于等于基准元素。不同的是，快速选择算法只需要关注包含第 k 小元素的那一部分子数组，然后继续在该子数组中进行划分，直到找到第 k 小元素。

平均时间复杂度

平均情况下，快速选择算法的时间复杂度为 O(n)，其中 n 是数组的长度。这是因为每次划分都能大致将问题规模减半，因此总的操作次数与数组长度成正比。

最坏时间复杂度

在最坏情况下，快速选择算法的时间复杂度为 O(n^2)。这种情况发生在每次选择的基准元素都是数组中的最大或最小元素时，导致划分后的子数组一个为空，另一个包含所有元素，每次只能减少一个元素，相当于进行了 n 次线性查找。

Java 实现快速选择算法

以下是一个简单的 Java 代码示例，展示了如何实现快速选择算法：

public class Quickselect {

    public static int quickselect(int[] arr, int k) {
        return quickselect(arr, 0, arr.length - 1, k - 1);
    }

    private static int quickselect(int[] arr, int low, int high, int k) {
        if (low == high) {
            return arr[low];
        }

        int pivotIndex = partition(arr, low, high);

        if (k == pivotIndex) {
            return arr[k];
        } else if (k < pivotIndex) {
            return quickselect(arr, low, pivotIndex - 1, k);
        } else {
            return quickselect(arr, pivotIndex + 1, high, k);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;

                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换 arr[i + 1] 和 arr[high]
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        int k = 3;
        System.out.println("第 " + k + " 小的元素是: " + quickselect(arr, k));
    }
}

代码解释

quickselect 方法：这是对外暴露的接口，接受一个整数数组 arr 和一个整数 k，返回数组中第 k 小的元素。它调用了一个私有的重载方法 quickselect，并将 k 减 1，因为数组索引从 0 开始。
私有 quickselect 方法：这个方法接受数组 arr、起始索引 low、结束索引 high 和目标索引 k。它首先检查 low 和 high 是否相等，如果相等，说明数组中只有一个元素，直接返回该元素。然后调用 partition 方法对数组进行划分，并根据 k 和基准元素的索引 pivotIndex 的关系，决定继续在哪个子数组中查找。
partition 方法：该方法选择数组的最后一个元素作为基准元素 pivot，然后遍历数组，将小于等于 pivot 的元素交换到数组的左边，大于 pivot 的元素交换到数组的右边。最后将基准元素与 i + 1 位置的元素交换，返回基准元素的最终位置 i + 1。

使用方法

使用上述实现的快速选择算法非常简单，只需要调用 quickselect 方法，并传入数组和目标 k 值即可。例如：

int[] arr = {3, 2, 1, 5, 6, 4};
int k = 3;
int result = Quickselect.quickselect(arr, k);
System.out.println("第 " + k + " 小的元素是: " + result);

常见实践

寻找中位数

中位数是数组中排序后位于中间位置的元素。如果数组长度为奇数，中位数就是第 (n + 1) / 2 小的元素；如果数组长度为偶数，中位数是第 n / 2 和第 (n / 2) + 1 小的元素的平均值。可以使用快速选择算法快速找到中位数：

public static double findMedian(int[] arr) {
    int n = arr.length;
    if (n % 2 == 1) {
        return Quickselect.quickselect(arr, (n + 1) / 2);
    } else {
        return (Quickselect.quickselect(arr, n / 2) + Quickselect.quickselect(arr, n / 2 + 1)) / 2.0;
    }
}

前 `k` 个最小元素

如果需要找到数组中前 k 个最小的元素，可以多次调用快速选择算法。每次找到第 i 小的元素后，将其从数组中移除，然后继续在剩余数组中查找第 i + 1 小的元素，直到找到前 k 个最小元素。

public static int[] findKSmallest(int[] arr, int k) {
    int[] result = new int[k];
    int[] remaining = arr.clone();

    for (int i = 0; i < k; i++) {
        int smallest = Quickselect.quickselect(remaining, 1);
        result[i] = smallest;

        // 移除已经找到的最小元素
        int[] newRemaining = new int[remaining.length - 1];
        int index = 0;
        for (int num : remaining) {
            if (num!= smallest) {
                newRemaining[index++] = num;
            }
        }
        remaining = newRemaining;
    }

    return result;
}

最佳实践

随机化基准元素

为了避免最坏情况的发生，可以随机选择基准元素。在 partition 方法中，可以在选择基准元素之前，随机交换数组中的一个元素和最后一个元素：

private static int partition(int[] arr, int low, int high) {
    // 随机选择基准元素
    int randomIndex = low + (int) (Math.random() * (high - low + 1));
    int temp = arr[randomIndex];
    arr[randomIndex] = arr[high];
    arr[high] = temp;

    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;

            // 交换 arr[i] 和 arr[j]
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 交换 arr[i + 1] 和 arr[high]
    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

优化小数组情况

对于小数组，可以使用插入排序等简单排序算法代替快速选择算法，因为在小数组上简单排序算法的常数因子较小，可能会更高效。可以在 quickselect 方法中添加一个阈值判断：

private static int quickselect(int[] arr, int low, int high, int k) {
    if (high - low + 1 <= 16) {
        // 使用插入排序
        insertionSort(arr, low, high);
        return arr[k];
    }

    int pivotIndex = partition(arr, low, high);

    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickselect(arr, low, pivotIndex - 1, k);
    } else {
        return quickselect(arr, pivotIndex + 1, high, k);
    }
}

private static void insertionSort(int[] arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

小结

快速选择算法是一种在数组中查找第 k 小元素的高效算法，平均时间复杂度为 O(n)。通过理解其基础概念、掌握 Java 实现方法，并应用常见实践和最佳实践，可以在实际编程中灵活运用该算法解决各种问题，如寻找中位数、前 k 个最小元素等。同时，通过随机化基准元素和优化小数组情况等技巧，可以进一步提高算法的性能和稳定性。

参考资料

《算法导论》（Introduction to Algorithms）
Wikipedia: Quickselect