手写快排:教你用Java写出高效排序算法!

简介: 快速排序(QuickSort)是经典的排序算法之一,基于分治思想,平均时间复杂度为O(n log n),广泛应用于各种场合。在这篇文章中,我们将手写一个Java版本的快速排序,从基础实现到优化策略,并逐步解析代码背后的逻辑。



大家好!我是小米,一个29岁,积极活泼、喜欢分享技术的程序员。今天我们来聊聊快速排序(QuickSort),一个经典的排序算法,也是许多面试中的常客!

快速排序的基本思想

快速排序(QuickSort)是一种基于分治思想的排序算法。它通过选取一个“基准元素”将待排序数组划分为左右两个部分,分别对左右部分递归地进行快速排序,最终实现数组的有序化。

简单来说:

  1. 选取基准元素;
  2. 将比基准元素小的元素放在它的左边,比它大的放在右边;
  3. 递归地对左右两个子数组进行快排。

这个算法的时间复杂度是O(n log n),在最坏情况下(例如输入数组已经有序的情况下)会退化为O(n^2),但它的平均时间复杂度仍然是O(n log n),因此在实际应用中,快排非常高效。

快速排序的实现

现在,咱们直接上代码!我会逐步讲解如何手写一个快速排序。

代码讲解

这段代码实现了一个简单的手写快速排序。让我们逐步解析一下代码的逻辑:

  • quickSort(): 这是主函数。它接收三个参数:要排序的数组arr,数组的左边界left和右边界right。在这个函数中,通过partition()方法将数组分为两部分,并递归地对这两部分进行快速排序。
  • partition(): 这是快排的核心。它的作用是选择一个基准元素(这里我们选择了最右边的元素),并通过一轮遍历将小于基准的元素放在左边,大于基准的放在右边,最终将基准元素放到正确的位置。返回值是基准元素的索引。
  • swap(): 一个简单的辅助方法,用来交换数组中的两个元素。在partition()过程中,我们需要频繁地交换元素,这个方法让代码更清晰。

为什么选择递归?

递归的核心思想就是“拆分”。我们把问题拆解成更小的子问题,并且这些子问题和原问题结构类似,只是规模小了很多。最终,当子问题变得足够小,我们就可以直接解决它们。

在快排中,每次递归都把数组拆成了两部分,分别递归处理它们。由于每次递归都处理一部分数组,最终我们就能让整个数组有序。

复杂度分析

快速排序的时间复杂度取决于基准元素的选择:

平均情况:每次都能把数组大致分成两个相等的部分。此时,时间复杂度为O(n log n)。

最坏情况:基准元素每次都把数组分成两个极端(一个部分为空,另一个部分包含所有元素),此时时间复杂度为O(n^2)。

为避免最坏情况,我们可以随机选择基准元素,或者使用“三数取中法”(选择左、中、右三个元素的中位数作为基准)。

随机选择基准元素

为了提高快排的效率,我们可以随机选择基准元素,从而减少最坏情况发生的概率。我们可以对partition()进行改进,添加随机选择基准元素的逻辑:

改进后的快速排序

在这个改进版的快排中,我们添加了一个随机选取基准元素的功能。通过随机选取基准元素,避免了在某些特殊情况下(如输入数组已经有序的情况)导致最坏时间复杂度的发生。

这样,即使面对极端的输入数据,我们也能获得平均情况下的时间复杂度O(n log n),提高了快排的稳定性和效率。

END

快速排序是排序算法中的经典之作,其高效的性能使得它在各种场合中都得到了广泛的应用。今天,我们一起手写了快排,并且学习了如何通过随机化基准元素来优化它的性能。

希望这篇文章对你有所帮助!有任何问题或想要深入讨论的内容,欢迎在评论区留言交流!更多实战算法内容,敬请关注小米的后续分享!

小米小贴士:保持好奇心,不断练习,算法其实并没有那么难哦!

我是小米,一个喜欢分享技术的29岁程序员。如果你喜欢我的文章,欢迎关注我的微信公众号软件求生,获取更多技术干货!

相关文章
|
8天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
34 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
10天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
30 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
10天前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
28 0
|
18天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
12 0
|
2月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
56 2
|
2月前
|
安全 算法 Java
java系列之~~网络通信安全 非对称加密算法的介绍说明
这篇文章介绍了非对称加密算法,包括其定义、加密解密过程、数字签名功能,以及与对称加密算法的比较,并解释了非对称加密在网络安全中的应用,特别是在公钥基础设施和信任网络中的重要性。
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
47 6
|
2月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
63 2
|
2月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
46 1