【数据结构与算法】十大经典排序算法-快速排序

news/2025/2/11 23:53:35/

🌟个人博客：www.hellocode.top
🏰Java知识导航：Java-Navigate
🔥CSDN：HelloCode.
🌞知乎：HelloCode
🌴掘金：HelloCode
⚡如有问题，欢迎指正，一起学习~~

快速排序（Quick Sort）是一种高效的排序算法，是对冒泡排序的优化。它采用分治法（Divide and Conquer）的思想，将待排序序列不断分割成较小的子序列，然后对每个子序列进行排序，最后合并得到有序的序列。快速排序在大多数情况下具有优异的性能，是许多常见排序算法中最快的之一。

基本思想

快速排序动画演示

这里的动画用大佬五分钟学算法的图，很清晰

  1. 选择一个基准元素（pivot）作为参考点。
  2. 将所有比基准元素小的元素移到基准元素的左边，将所有比基准元素大的元素移到基准元素的右边。此过程称为分区（partitioning）。
  3. 对基准元素左右两边的子序列递归地进行相同的快速排序，直到子序列的大小为1或0，表示子序列已经有序。

如上图所示，快速排序的基本思想就是选取一个基准数，将基准数小的都放在左边，大的都放在右边，也就是每次循环都会确定出基准数应该在的正确位置。

代码实现

对应在代码层面，需要使用到递归法来实现，对于快速排序来说，递归相对还是很容易想到的

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月08日 21:14*/
public class QuickSort {public static void quickSort(int[] arr) {// 特殊情况处理if (arr == null || arr.length == 0 || arr.length == 1) {return;}// 递归入口sort(arr, 0, arr.length - 1);}private static void sort(int[] arr, int left, int right) {// 递归出口if (left > right) {return;}// 初始化双指针int i = left, j = right;// 选取基准数int base = arr[left];while (i != j) {// （注意！！！！）从右边开始// 找比基准数小的while (i < j && arr[j] >= base) {j--;}// 从左边找比基准数大的while (i < j && arr[i] <= base) {i++;}// 交换i jif (i < j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 基准数归位(此时i == j)arr[left] = arr[i];arr[i] = base;// 开始左右两边分别快排sort(arr, left, i - 1);sort(arr, i + 1, right);}
}

这里先移动j还是先移动i主要是需要看基准数选取的位置，如果选最左边的数，就需要先移动j（确保i == j 时对应的值是小于基准数的，再把基准数和该数交换，符合排序规则）
如果选取的基准数是最右边，则先移动i指针（确保 i == j 时对应的值是大于基准数的）

测试：

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月08日 21:14*/
public class Test {public static void main(String[] args) {int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12};System.out.println("排序前：" + Arrays.toString(arr));QuickSort.quickSort(arr);System.out.println("排序后：" + Arrays.toString(arr));}
}

image-20230808213942941

优化

快排的优化主要需要关注基准数的选取，如果待排序数组整体偏降序，此时还选最左侧的为基准数的话，效率就相对慢一些，所以选取一个好的基准数可以让快排的效率更加稳定~

主要的方法有以下几种：

  1. 随机选择基准元素：选择随机的基准元素可以降低最坏情况的概率，进而提高算法性能。
  2. 三数取中法：在选取基准元素时，不是简单地选取第一个或最后一个元素，而是选择中间元素、第一个元素和最后一个元素中的中位数作为基准元素，也可以降低最坏情况的概率。

这里基准数的选取可以很巧妙，还有很多种其他方法，都可以降低最坏情况的发生，本文以三数取中法为例：

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月08日 21:14*/
public class QuickSort {public static void quickSort(int[] arr) {// 特殊情况处理if (arr == null || arr.length == 0 || arr.length == 1) {return;}// 递归入口sort(arr, 0, arr.length - 1);}private static void sort(int[] arr, int left, int right) {// 递归出口if (left > right) {return;}// 初始化双指针int i = left, j = right;// 选取基准数getBase(arr, left, right);int base = arr[left];while (i != j) {// （注意！！！！）从右边开始// 找比基准数小的while (i < j && arr[j] >= base) {j--;}// 从左边找比基准数大的while (i < j && arr[i] <= base) {i++;}// 交换i jif (i < j) {swap(arr, i, j);}}// 基准数归位(此时i == j)arr[left] = arr[i];arr[i] = base;// 开始左右两边分别快排sort(arr, left, i - 1);sort(arr, i + 1, right);}// 取三点中间值（最终会移动到left位置，这样可以不改变原有代码）private static void getBase(int[] arr, int left, int right) {// 这里可以防止溢出且使用 >> 效率相对能高一些// 等价于 (left + right) / 2int mid = left + ((right - left) >> 1);// 确保第一个元素最小if (arr[left] > arr[right]) {swap(arr, left, right);}// 确保最后一个元素最大if (arr[mid] > arr[right]) {swap(arr, mid, right);}// 确定mid就是中间值，交换到最左边if (arr[left] < arr[mid]) {swap(arr, left, mid);}System.out.println("基准数为：" + arr[left]);}// 交换数组两下标元素位置private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

测试：

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月07日 21:02*/
public class Test {public static void main(String[] args) {int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19};System.out.println("排序前：" + Arrays.toString(arr));BubbleSort.bubbleSortOptimized1(arr);System.out.println("排序后：" + Arrays.toString(arr));}
}

排序前：[21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12]
基准数为：15
基准数为：7
基准数为：4
基准数为：12
基准数为：10
基准数为：13
基准数为：32
基准数为：21
基准数为：19
基准数为：32
基准数为：65
基准数为：33
基准数为：65
基准数为：72
基准数为：89
排序后：[4, 7, 10, 12, 13, 15, 19, 21, 32, 32, 33, 65, 65, 72, 89]

总结

优点

  1. 高效性：快速排序是一种高效的排序算法，在大多数实际情况下，它的性能通常比其他常见排序算法（如冒泡排序、插入排序）更好。
  2. 原地排序：快速排序是原地排序算法，不需要额外的辅助空间，只需在原始数组上进行交换操作。

缺点

  1. 最坏情况下的性能：当待排序序列已经基本有序或完全逆序时，快速排序的时间复杂度退化为 O(n^2)，导致性能下降。这是因为基准元素的选择可能导致分区不平衡，使得分区操作不再能有效地减少问题规模。
  2. 不稳定性：快速排序是一种不稳定的排序算法，意味着相等元素的相对顺序在排序后可能发生变化。这在某些情况下可能导致问题，特别是对于复杂对象的排序，需要额外的处理来保持稳定性。

复杂度

  • 时间复杂度：快速排序的平均时间复杂度为O(n log n)，最坏情况下为O(n^2)。
  • 空间复杂度：快速排序是原地排序算法，空间复杂度为O(log n)。

适用于处理大规模数据集的排序，尤其在平均情况下，快速排序的性能较优。但在处理已经有序或近乎有序的数据集时，快速排序的性能可能会下降，这时候其他稳定的排序算法可能更合适。


http://www.ppmy.cn/news/1015512.html

相关文章

Maven 打包生成Windows和Liunx启动文件

Maven 打包生成Windows和Liunx启动文件

新建一个springboot项目。 1、项目结构 2、pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocati…
阅读更多...
小程序如何使用防抖和节流？

小程序如何使用防抖和节流？

防抖&#xff08;Debounce&#xff09;和节流&#xff08;Throttle&#xff09;都是用来优化函数执行频率的技术&#xff0c;特别在处理用户输入、滚动等频繁触发的情况下&#xff0c;它们可以有效减少函数的执行次数&#xff0c;从而提升性能和用户体验。但它们的工作方式和应…
阅读更多...
【产品设计】消息通知系统设计

【产品设计】消息通知系统设计

消息通知可以将内容实时送达用户手机页面&#xff0c;但是泛滥的消息通知会引起用户的反感&#xff0c;也违背了这个设计的初衷。 消息通知可以及时地将状态、内容的更新触达到用户&#xff0c;用户则可以根据收到的消息做后续判断。但是如果没有及时将重要消息触达到用户或者滥…
阅读更多...
Unity 中检测射线穿过的所有的物体

Unity 中检测射线穿过的所有的物体

在开发中 有个需求&#xff0c;射线要检测所有穿过的物体。 代码如下&#xff1a; using UnityEngine;public class HitCollider : MonoBehaviour {public float raycastDistance Mathf.Infinity;// Update is called once per framevoid Update(){Ray ray Camera.main.Scre…
阅读更多...
WordPress获取文章所属分类名称或别名方法

WordPress获取文章所属分类名称或别名方法

最近在开发WordPress主题的时候&#xff0c;想要获取到文章所属分类名称或别名&#xff0c;想了半天没想到&#xff0c;于是去百度了下&#xff0c;马上就得到答案了。 非常简单&#xff0c;WordPress本身自带一个函数可以调出分类别名和链接&#xff1a; <?php the_cate…
阅读更多...
C语言--结构体指针

C语言--结构体指针

结构体指针变量 引入&#xff1a; 指针就是地址&#xff0c;指针变量就是存放地址的变量 int a; int *p; p&a; 结构体也是变量 变量访问有两种方式&#xff1a;1.变量名 2.地址 struct Test t; struct Test *P; p&t; 通过结构体指针访问结构体&#xff1a;用’->来访…
阅读更多...
2208. 将数组和减半的最少操作次数

2208. 将数组和减半的最少操作次数

2208. 将数组和减半的最少操作次数 给你一个正整数数组 nums 。每一次操作中&#xff0c;你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。&#xff08;注意&#xff0c;在后续操作中你可以对减半过的数继续执行操作&#xff09; 请你返回将 nums 数组和 至少 减少一…
阅读更多...
第五次作业 运维高级 构建 LVS-DR 集群和配置nginx负载均衡

第五次作业 运维高级 构建 LVS-DR 集群和配置nginx负载均衡

1、基于 CentOS 7 构建 LVS-DR 群集。 LVS-DR模式工作原理 首先&#xff0c;来自客户端计算机CIP的请求被发送到Director的VIP。然后Director使用相同的VIP目的IP地址将请求发送到集群节点或真实服务器。然后&#xff0c;集群某个节点将回复该数据包&#xff0c;并将该数据包…
阅读更多...
最新文章

Copyright @ 2022~2023