当前位置： 首页 > news >正文

Java手写快速选择算法应用拓展案例

news 2025/7/14 21:51:42

Java手写快速选择算法应用拓展案例

1. 引言

快速选择算法是一种高效的选择算法，可以用于在数组中找到第K小/大的元素。除了基本的应用场景外，快速选择算法还可以应用于其他问题，如查找中位数、查找最大/最小值等。本文将介绍两个拓展应用案例，并提供完整的代码和步骤描述。

2. 拓展应用案例1：查找中位数

中位数是一个有序数组中的中间值。通过快速选择算法，我们可以快速找到一个数组的中位数。

2.1 步骤描述

  1. 定义一个方法 findMedian，接受一个整型数组 arr 作为参数。
  2. 调用 quickSelect 方法，传入数组 arr、左边界 0、右边界 arr.length - 1 和中位数的位置 (arr.length + 1) / 2。
  3. 在 quickSelect 方法中，选择基准元素 pivot，并调用 partition 方法进行分区。
  4. 根据 partition 方法的返回值 index，判断中位数的位置：
    • 如果 index 等于 (arr.length + 1) / 2 - 1，则返回 arr[index]。
    • 如果 index 大于 (arr.length + 1) / 2 - 1，则递归调用 quickSelect 方法，在左半部分数组中查找中位数。
    • 如果 index 小于 (arr.length + 1) / 2 - 1，则递归调用 quickSelect 方法，在右半部分数组中查找中位数。
  5. 在 main 方法中，调用 findMedian 方法，并打印中位数的值。

2.2 完整代码

public class QuickSelectMedian {public static void main(String[] args) {int[] arr = {5, 3, 8, 2, 9, 1};int median = findMedian(arr);System.out.println("中位数是：" + median);}private static int findMedian(int[] arr) {return quickSelect(arr, 0, arr.length - 1, (arr.length + 1) / 2);}private static int quickSelect(int[] arr, int left, int right, int k) {int pivot = selectPivot(arr, left, right);int index = partition(arr, left, right, pivot);if (index == k - 1) {return arr[index];} else if (index > k - 1) {return quickSelect(arr, left, index - 1, k);} else {return quickSelect(arr, index, right, k);}}private static int selectPivot(int[] arr, int left, int right) {return arr[left];}private static int partition(int[] arr, int left, int right, int pivot) {int i = left;int j = right;while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr, i, j);i++;j--;}}return i;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

3. 拓展应用案例2：查找最大/最小值

快速选择算法也可以用于查找一个数组的最大/最小值。

3.1 步骤描述

  1. 定义一个方法 findMax，接受一个整型数组 arr 作为参数。
  2. 调用 quickSelect 方法，传入数组 arr、左边界 0、右边界 arr.length - 1 和最大值的位置 1。
  3. 在 quickSelect 方法中，选择基准元素 pivot，并调用 partition 方法进行分区。
  4. 根据 partition 方法的返回值 index，判断最大值的位置：
    • 如果 index 等于 1 - 1，则返回 arr[index]。
    • 如果 index 大于 1 - 1，则递归调用 quickSelect 方法，在左半部分数组中查找最大值。
    • 如果 index 小于 1 - 1，则递归调用 quickSelect 方法，在右半部分数组中查找最大值。
  5. 在 main 方法中，调用 findMax 方法，并打印最大值的值。

3.2 完整代码

public class QuickSelectMax {public static void main(String[] args) {int[] arr = {5, 3, 8, 2, 9, 1};int max = findMax(arr);System.out.println("最大值是：" + max);}private static int findMax(int[] arr) {return quickSelect(arr, 0, arr.length - 1, 1);}private static int quickSelect(int[] arr, int left, int right, int k) {int pivot = selectPivot(arr, left, right);int index = partition(arr, left, right, pivot);if (index == k - 1) {return arr[index];} else if (index > k - 1) {return quickSelect(arr, left, index - 1, k);} else {return quickSelect(arr, index, right, k);}}private static int selectPivot(int[] arr, int left, int right) {return arr[left];}private static int partition(int[] arr, int left, int right, int pivot) {int i = left;int j = right;while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr, i, j);i++;j--;}}return i;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

4.1 步骤描述

  1. 定义一个方法 findKthSmallest，接受一个整型数组 arr 和一个整数 k 作为参数。
  2. 调用 quickSelect 方法，传入数组 arr、左边界 0、右边界 arr.length - 1 和 k。
  3. 在 quickSelect 方法中，选择基准元素 pivot，并调用 partition 方法进行分区。
  4. 根据 partition 方法的返回值 index，判断第k小的元素的位置：
    • 如果 index 等于 k - 1，则返回 arr[index]。
    • 如果 index 大于 k - 1，则递归调用 quickSelect 方法，在左半部分数组中查找第k小的元素。
    • 如果 index 小于 k - 1，则递归调用 quickSelect 方法，在右半部分数组中查找第k小的元素。
  5. 在 main 方法中，调用 findKthSmallest 方法，并打印第k小的元素的值。

4.2 完整代码

public class QuickSelectKthSmallest {public static void main(String[] args) {int[] arr = {5, 3, 8, 2, 9, 1};int k = 3;int kthSmallest = findKthSmallest(arr, k);System.out.println("第" + k + "小的元素是：" + kthSmallest);}private static int findKthSmallest(int[] arr, int k) {return quickSelect(arr, 0, arr.length - 1, k);}private static int quickSelect(int[] arr, int left, int right, int k) {int pivot = selectPivot(arr, left, right);int index = partition(arr, left, right, pivot);if (index == k - 1) {return arr[index];} else if (index > k - 1) {return quickSelect(arr, left, index - 1, k);} else {return quickSelect(arr, index + 1, right, k);}}private static int selectPivot(int[] arr, int left, int right) {return arr[left];}private static int partition(int[] arr, int left, int right, int pivot) {int i = left;int j = right;while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr, i, j);i++;j--;}}return i;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

在上面的代码中，我们查找数组 arr 中第3小的元素，即 k = 3。运行结果如下：

第3小的元素是：3

这个例子展示了快速选择算法在查找第k小的元素上的应用。通过快速选择算法，我们可以在平均时间复杂度为O(n)的情况下，快速找到第k小的元素。这对于大数据处理和数据挖掘等领域的应用非常有价值。

4. 结论

通过快速选择算法的拓展应用案例，我们可以看到该算法在查找中位数和查找最大/最小值等问题上的高效性和灵活性。通过手写实现和定制化，我们可以根据实际需求进行优化和改进，提高算法的效率和适用性。快速选择算法在大数据处理、机器学习、数据挖掘等领域有着广泛的应用前景。随着数据规模的不断增大和数据处理需求的不断增加，快速选择算法将发挥更加重要的作用。

http://www.lryc.cn/news/171129.html

相关文章：

  • js制作柱状图的x轴时间, 分别展示 月/周/日 的数据
  • 安防监控/视频汇聚/云存储/AI智能视频分析平台EasyCVR下级海康设备无法级联是什么原因？
  • HttpUtils带连接池
  • 智慧养殖：浅谈视频监控与AI智能识别技术助力奶牛高效、智慧养殖
  • 一文总结提示工程框架，除了CoT还有ToT、GoT、AoT、SoT、PoT
  • Java面试笔试acm版输入
  • 新手怎样快速上手接口测试？掌握这几个知识点直接起飞！
  • IDEA 启动 java web 老项目
  • 软路由和硬路由的区别是什么，性价比与可玩性分析
  • 《TCP/IP网络编程》阅读笔记--多线程服务器端的实现
  • 修改el-card的header的背景颜色
  • ubuntu系统中查看打开的端口
  • Datax从mysql同步数据到HDFS
  • 使用 Selenium 或其他工具模拟浏览器使用及语法代码
  • 华为手机如何开启设置健康使用手机模式限制孩子玩手机时间？
  • 【Linux】线程池 | 自旋锁 | 读写锁
  • [网鼎杯 2020 青龙组]bang 题解
  • 创建环境时提示：ERROR conda.core.link:_execute(502)
  • Python150题day07
  • LeetCode 2596. 检查骑士巡视方案
  • 大数据学习1.0-目录
  • 无涯教程-JavaScript - POWER函数
  • ChatGPT：解释Java中 ‘HttpResponse‘ 使用 ‘try-with-resources‘ 的警告和处理 ‘Throwable‘ 打印警告
  • Linux编辑器-gcc的使用
  • 第16篇ESP32 platformio_arduino框架 wifi联网_连接WiFi热点并连接tcp server收发数据进行通讯
  • day1| 704. 二分查找、27. 移除元素
  • R绘制箱线图
  • 利用Audit审计系统行为
  • uniapp：不同权限设置不同的tabBar
  • 如何将本地的项目上传到Git