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

Java快速排序知识点(含面试大厂题和源码)

快速排序(Quick Sort)是一种高效的排序算法,采用分治法(Divide and Conquer)的策略来对一个数组进行排序。快速排序的平均时间复杂度为 O(n log n),在最坏的情况下为 O(n^2),但这种情况很少发生。快速排序因其高效性而在实际应用中非常受欢迎。

快速排序的工作原理:

  1. 选择基准值:从数组中选择一个元素作为基准值(pivot),选择方法有多种,如第一个元素、最后一个元素、中间元素或随机元素。
  2. 分区操作:重新排列数组,所有比基准值小的元素摆放在基准值的前面,所有比基准值大的元素摆放在基准值的后面(相等的可以到任一边)。在这个分区退出之后,基准值所在的位置就是其最终位置。
  3. 递归排序:递归地对基准值左侧和右侧的子数组进行快速排序。

快速排序的优缺点:

优点

  • 在平均情况下,快速排序具有很好的性能,时间复杂度为 O(n log n)。
  • 快速排序是原地排序,不需要额外的存储空间。

缺点

  • 最坏情况下的时间复杂度为 O(n^2),但可以通过随机化来避免。
  • 快速排序是不稳定的排序方法,相等的元素可能会在排序后相对位置发生变化。

快速排序的Java实现:

public class QuickSort {public void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}private 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++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {QuickSort solution = new QuickSort();int[] arr = {10, 7, 8, 9, 1, 5};solution.quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));}
}

在面试中,快速排序是一个重要的知识点,它考察应聘者对分治法策略和递归思想的理解。通过实现快速排序,可以展示你对基本算法和数据结构的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试!快速排序是一种流行且高效的排序算法,经常被用于面试中考察应聘者的算法实现能力。以下是三道可能出现在大厂面试中的与快速排序相关的编程题目,以及相应的Java源码实现。

题目 1:快速排序实现

描述
实现快速排序算法,对给定数组进行排序。

示例

输入: [3, 6, 8, 10, 1, 2, 1]
输出: 经过排序后的数组

Java 源码

import java.util.Arrays;public class QuickSortImplementation {public void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}private 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++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {QuickSortImplementation solution = new QuickSortImplementation();int[] arr = {3, 6, 8, 10, 1, 2, 1};solution.quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));}
}

题目 2:快速排序的变种 - 三数取中法的基准选择

描述
在快速排序中,基准值的选择对性能有很大影响。使用三数取中法选择基准值,即在数组中随机选择三个元素,然后取它们的中值作为基准值。

示例

输入: [3, 6, 8, 10, 1, 2, 1]
输出: 经过排序后的数组

Java 源码

import java.util.Random;public class QuickSortMedianOfThree {// 其他方法与上题相同,仅 partition 方法改变private int partition(int[] arr, int low, int high) {Random random = new Random();int pivotIndex = medianOfThree(arr, low, high);swap(arr, pivotIndex, high);int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private int medianOfThree(int[] arr, int low, int high) {int mid = low + (high - low) / 2;if (arr[low] > arr[mid]) swap(arr, low, mid);if (arr[low] > arr[high]) swap(arr, low, high);if (arr[mid] > arr[high]) swap(arr, mid, high);swap(arr, mid, high);return high;}// swap 方法与上题相同// main 方法与上题相同
}

题目 3:快速排序优化 - 尾递归优化

描述
在快速排序中,对较小的子数组使用尾递归优化,以减少递归深度。

示例

输入: [3, 6, 8, 10, 1, 2, 1]
输出: 经过排序后的数组

Java 源码

public class QuickSortTailRecursion {// quickSort 方法与上题相同private int partition(int[] arr, int low, int high) {// ... 与上题相同}private void swap(int[] arr, int i, int j) {// ... 与上题相同}public static void main(String[] args) {QuickSortTailRecursion solution = new QuickSortTailRecursion();int[] arr = {3, 6, 8, 10, 1, 2, 1};solution.quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));}// 添加 tailRecursiveQuickSort 方法进行尾递归优化public void tailRecursiveQuickSort(int[] arr, int low, int high) {while (low < high) {int pivotIndex = partition(arr, low, high);if (pivotIndex - low < high - pivotIndex) {tailRecursiveQuickSort(arr, low, pivotIndex - 1);low = pivotIndex + 1;} else {tailRecursiveQuickSort(arr, pivotIndex + 1, high);high = pivotIndex - 1;}}}
}

这些题目和源码展示了快速排序的不同应用和优化技巧。在面试中,能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试!

相关文章:

Java快速排序知识点(含面试大厂题和源码)

快速排序&#xff08;Quick Sort&#xff09;是一种高效的排序算法&#xff0c;采用分治法&#xff08;Divide and Conquer&#xff09;的策略来对一个数组进行排序。快速排序的平均时间复杂度为 O(n log n)&#xff0c;在最坏的情况下为 O(n^2)&#xff0c;但这种情况很少发生…...

SpringBoot整合Swagger2

SpringBoot整合Swagger2 1.什么是Swagger2&#xff1f;&#xff08;应用场景&#xff09;2.项目中如何使用2.1 导入依赖2.2 编写配置类2.3 注解使用2.3.1 controller注解&#xff1a;2.3.2 方法注解2.3.3 实体类注解2.3.4 方法返回值注解2.3.5 忽略的方法 3.UI界面 1.什么是Swa…...

C++算法题 - 矩阵

目录 36. 有效的数独54. 螺旋矩阵48. 旋转图像73. 矩阵置零289. 生命游戏 36. 有效的数独 LeetCode_link 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现…...

记录一个没测出来,有点严重的Bug

前提&#xff1a; 人物&#xff1a;若干个 部门&#xff1a;若干个 部门有一个人物选择框&#xff0c;可以选择所有的人物&#xff0c;且为非必填字段 bug现象: 部门中 的人物选择框每次都少一个人物 代码分析&#xff1a; F12接口后端没问题&#xff0c;定位为前端的问题。 前…...

科学突破可能开创6G通信新时代

格拉斯哥大学开发的火柴盒大小的天线可以为全息通话、改进自动驾驶和更好的医疗保健的世界铺平道路。 格拉斯哥大学表示&#xff0c;这种创新的无线通信天线将超材料的独特特性与复杂的信号处理相结合&#xff0c;有助于构建未来的 6G 网络。 数字编码动态超表面天线&#xf…...

游戏、app抓包

文章目录 协议app抓包游戏抓包 协议 在抓包之前&#xff0c;首先我们要对每个程序使用什么协议有个大致的了解&#xff0c;比如网页这种就是走的http协议。 在一些app中我们通过发送一个请求&#xff0c;然后服务器接受&#xff0c;响应&#xff0c;返回一个数据包&#xff0c…...

PACNet CellNet(代码开源)|bulk数据作细胞分类,评估细胞命运性能的一大利器

文章目录 1.前言2.CellNet2.1CellNet简介2.2CellNet结果 3.PACNet3.1安装R包与加载R包3.2加载数据3.3开始训练和分类3.4可视化分类过程3.5可视化分类结果 4.细胞命运分类和免疫浸润比较 1.前言 今天冲浪看到一个细胞分类性能评估的R包——PACNet&#xff0c;它与转录组分析方法…...

(delphi11最新学习资料) Object Pascal 学习笔记---第10章第1节(定义属性)

第10章 属性和事件 ​ 在过去的三章中&#xff0c;我已经介绍了Object Pascal中面向对象编程&#xff08;OOP&#xff09;的基础知识&#xff0c;解释了这些概念并展示了大多数面向对象编程语言中通用特性是如何具体实现的。自Delphi的早期&#xff0c;Object Pascal语言就是一…...

【网络安全 | 密码学】JWT基础知识及攻击方式详析

前言 JWT&#xff08;Json Web Token&#xff09;是一种用于在网络应用之间安全地传输信息的开放标准。它通过将用户信息以JSON格式加密并封装在一个token中&#xff0c;然后将该token发送给服务端进行验证&#xff0c;从而实现身份验证和授权。 流程 JWT的加密和解密过程如…...

Chrome修改主题颜色

注意&#xff1a;自定义Chrome按钮只在搜索引擎为Google的时候出现。...

大数据:【学习笔记系列】Flink基础架构

Apache Flink 是一个开源的流处理框架&#xff0c;用于处理有界和无界的数据流。Flink 设计用于运行在所有常见的集群环境中&#xff0c;并且能够以高性能和可扩展的方式进行实时数据处理和分析。下面将详细介绍 Flink 的基础架构组件和其工作原理。 1. Flink 架构概览 Flink…...

Debezium系列之:部署Debezium采集Oracle数据库的详细步骤

Debezium系列之:部署Debezium采集Oracle数据库的详细步骤 一、部署Debezium Oracle连接器二、Debezium Oracle 连接器配置三、添加连接器配置四、可插拔数据库与不可插拔数据库一、部署Debezium Oracle连接器 部署的详细步骤可以参考博主这篇技术文章: Debezium系列之:安装…...

C语言通过键盘输入给结构体内嵌的结构体赋值——指针法

1 需求 以录入学生信息&#xff08;姓名、学号、性别、出生日期&#xff09;为例&#xff0c;首先通过键盘输入需要录入的学生的数量&#xff0c;再依次输入这些学生的信息&#xff0c;输入完成后输出所有信息。 2 代码 #include<stdio.h> #include<stdlib.h>//…...

AWS Key disabler:AWS IAM用户访问密钥安全保护工具

关于AWS Key disabler AWS Key disabler是一款功能强大的AWS IAM用户访问密钥安全保护工具&#xff0c;该工具可以通过设置一个时间定量来禁用AWS IAM用户访问密钥&#xff0c;以此来降低旧访问密钥所带来的安全风险。 工具运行流程 AWS Key disabler本质上是一个Lambda函数&…...

【第1节】书生·浦语大模型全链路开源开放体系

目录 1 简介2 内容&#xff08;1&#xff09;书生浦语大模型发展历程&#xff08;2&#xff09;体系&#xff08;3&#xff09;亮点&#xff08;4&#xff09;全链路体系构建a.数据b 预训练c 微调d 评测e.模型部署f.agent 智能体 3 相关论文解读4 ref 1 简介 书生浦语 InternLM…...

代码随想录-链表 | 707设计链表

代码随想录-数组 | 707设计链表 LeetCode 707-设计链表解题思路代码复杂度难点总结 LeetCode 707-设计链表 题目链接 题目描述 你可以选择使用单链表或者双链表&#xff0c;设计并实现自己的链表。 单链表中的节点应该具备两个属性&#xff1a;val 和 next 。val 是当前节点…...

AIGC算法1:Layer normalization

1. Layer Normalization μ E ( X ) ← 1 H ∑ i 1 n x i σ ← Var ⁡ ( x ) 1 H ∑ i 1 H ( x i − μ ) 2 ϵ y x − E ( x ) Var ⁡ ( X ) ϵ ⋅ γ β \begin{gathered}\muE(X) \leftarrow \frac{1}{H} \sum_{i1}^n x_i \\ \sigma \leftarrow \operatorname{Var}(…...

【C语言】——字符串函数的使用与模拟实现(下)

【C语言】——字符串函数的使用与模拟实现&#xff08;下&#xff09; 前言五、长度受限类字符串函数5.1、 s t r n c p y strncpy strncpy 函数5.2、 s t r n c a t strncat strncat 函数5.3、 s t r n c m p strncmp strncmp 函数 六、 s t r s t r strstr strstr 函数6.1、函…...

mac安装nvm详细教程

0. 前提 清除电脑上原有的node (没有装过的可以忽略)1、首先查看电脑上是否安装的有node,查看node版本node -v2、如果有node就彻底删除nodesudo rm -rf /usr/local/{bin/{node,npm},lib/node_modules/npm,lib/node,share/man/*/node.*}2、保证自己的电脑上有安装git,不然下载n…...

上线流程及操作

上节回顾 1 搜索功能-前端&#xff1a;搜索框&#xff0c;搜索结果页面-后端&#xff1a;一种类型课程-APIResponse(actual_courseres.data.get(results),free_course[],light_course[])-搜索&#xff0c;如果数据量很大&#xff0c;直接使用mysql&#xff0c;效率非常低--》E…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...