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

排序系列 之 快速排序

  • !!!排序仅针对于数组哦
  • 本次排序是按照升序来的哦
  • 代码后边有图解哦

介绍

  • 快速排序英文名为Quick Sort

基本思路

  • 快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素base,利用base将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列

代码

<!----java----->
import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr = {7,2,3,6,1,5,4};  // 待排序数组sort(arr,0, arr.length-1); // 方法调用,left和right为带排序数组的起始位置和最终位置,所以right=arr.length-1System.out.println(Arrays.toString(arr));}public static void sort(int[] arr,int left,int right){if(left>=right){return;}    // 判断带排序数组的长度,严格的左边游标要不大于右边游标int base = arr[left];    // 定义基准数int i = left;       // 定义左边的游标。这里不用left,是因为left位置为基准数,基准数不能变int j = right;      // 定义右边的游标。这里不用right,是因为后续递归的时候需要一个参数while(i!=j){    // 循环走起,当i和j相遇时,跟基准数交换。不相遇时,i位置大于基准数,j位置小于基准数时,i位置和j位置的数交换/**   思考下,为啥这里先是j在i前边???    */while(arr[j]>=base && i<j){j--;}    // 循环停止,说明j指向的数值要比基准数小。降序为<= while(arr[i]<=base && i<j){i++;}    // 循环停止,说明i指向的数值要比基准数大。降序为>= /** 【公布问题答案啦】* 因为j停下的时候代表当前数比基准数小,i停下是当前数比基准数大。我们此次排序是升序,相遇数要和基准数交换,所以需要保证相遇数一定要小于基准数*/// 本次排序为升序,即需要找到一个位置,这个位置的左边都是比基准数小的,右边都是比基准数大的int temp = arr[i];  // i比基准数大,j比基准数小,交换。交换完成后,i和j不等,两个游标继续前走或后走arr[i] = arr[j];arr[j] = temp;}// i和j相遇,i也行j也行,因为都指向一个嘛,跟基准数交换。然后对基准数左右两遍递归arr[left] = arr[i];arr[i] = base;sort(arr,left,i-1);sort(arr,i+1,right);}
}<!------------------------>
运行结果;
[1, 2, 3, 4, 5, 6, 7]
<!----python----->
def quickSort(arr, left, right):if left >= right:return arr;base = arr[left];i, j = left, right;while i != j:while arr[j] >= base and i < j:j -= 1while arr[i] <= base and i < j:i += 1arr[j], arr[i] = arr[i], arr[j];arr[i], arr[left] = arr[left], arr[i];quickSort(arr,left,i-1);quickSort(arr,i+1,right);return arrarr = [7,2,3,6,1,5,4]
print(quickSort(arr, 0, len(arr) - 1))
<!------------------------>
运行结果;
[1, 2, 3, 4, 5, 6, 7]

代码思路及流程图(直接上图,不清楚可以对照代码看哦)

在这里插入图片描述

复杂度

  • 时间复杂度:最好和平均情况下为O(n log n),最坏情况下为O(n^2)。
  • 空间复杂度:最好情况下为O(log n),最坏情况下为O(n),额外空间为O(1)。
    (复杂度先记住吧,等后续研究彻底了,会再写篇文章的)
  • 它是非稳定排序

扩展一下

Python的一个更简单的方法
# 该方法不适用java哦
def quickSort(arr):if len(arr)<2:return arr;base=arr[0];left = [x for x in arr if x<base];middle = [x for x in arr if x==base];right = [x for x in arr if x>base];return quickSort(left)+middle+quickSort(right);arr=[7,2,3,6,1,5,4];
print(quickSort(arr))  # [1, 2, 3, 4, 5, 6, 7]

巩固一下

给定一个数组,用上述方法进行排序,流程是不是跟下图一样呢?
int[] arr = {3,7,1,6,2,5,4}
在这里插入图片描述

文章推荐

  • 实在是不会做动画,如果还看不懂,可以移步这里:
    十大经典排序算法
    【漫画】不要再问我快速排序了
  • 有错误请指正,谢谢各位~
http://www.lryc.cn/news/403089.html

相关文章:

  • 【银河麒麟服务器操作系统】java进程oom现象分析及处理建议
  • Redis的AOF持久化策略(AOF的工作流程、AOF的重写流程,操作演示、注意事项等)
  • 共享模型之无锁
  • 下载安装VSCode并添加插件作为仓颉编程入门编辑器
  • 解决:Linux上SVN 1.12版本以上无法直接存储明文密码
  • Mongodb多键索引中索引边界的混合
  • 如何利用windows本机调用Linux服务器,以及如何调用jupyter界面远程操控
  • 如何定位Milvus性能瓶颈并优化
  • 阿里云服务器 篇三:提交搜索引擎收录
  • powe bi界面认识及矩阵表基本操作 - 1
  • SpringBoot 项目 pom.xml 中 设置 Docker Maven 插件
  • k8s二次开发-kubebuiler一键式生成deployment,svc,ingress
  • Flutter 状态管理新境界:多Provider并行驱动UI
  • 标识符和关键字的区别是什么,常用的关键字有哪些?自增自减运算符,移位运算符continue、break、return的区别是什么?
  • 在VS Code上搭建Vue项目教程(Vue-cli 脚手架)
  • AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理
  • Docker 和 k8s 之间是什么关系?
  • 敲详细的springframework-amqp-rabbit源码解析
  • Telegram Bot、小程序开发(三)Mini Apps小程序
  • Django F()函数
  • GraphRAG的实践
  • 自动驾驶三维车道线检测系列—LATR: 3D Lane Detection from Monocular Images with Transformer
  • 守护动物乐园:视频AI智能监管方案助力动物园安全与秩序管理
  • FairGuard游戏加固入选《嘶吼2024网络安全产业图谱》
  • 数据仓库事实表
  • LeetCode题练习与总结:两数之和Ⅱ-输入有序数组--167
  • 在 Java 中,怎样设计一个可扩展且易于维护的微服务架构?
  • 零基础入门鸿蒙开发 HarmonyOS NEXT星河版开发学习
  • Chromium CI/CD 之Jenkins实用指南2024-在Windows节点上创建任务(九)
  • ceph进程网卡绑定逻辑