十大经典排序算法之快速排序 快速排序的算法分析
yuyutoo 2024-10-12 01:08 6 浏览 0 评论
快速排序(Quick Sort)采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。
算法特性
- 稳定性
快速排序是一种不稳定的排序算法。
- 时间复杂度
快速排序的时间复杂度在最坏情况下是O(n^2),平均的时间复杂度是O(N*logN)。
- 空间复杂度
快速排序是一种原地排序算法,不需要额外的空间进行排序。因此,快速排序的空间复杂度为O(1)。
算法步骤
快速排序算法通过多次比较和交换来实现排序,其流程如下:
1、首先设定一个基准值,通过该基准值将数组分成左右两部分。
2、将大于或等于基准值的数据集中到数组右边,小于基准值的数据集中到数组的左边。此时,左边部分中各元素都小于基准值,而右边部分中各元素都大于或等于基准值。
3、然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个基准值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
动画演示
代码实现
Java代码:
private static int[] quickSort(int[] array, int left, int right) {
if (left < right) {
int partitionIndex = partition(array, left, right);
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
return array;
}
private static int partition(int[] array, int left, int right) {
// 设定基准值
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (array[i] < array[pivot]) {
swap(array, i, index);
index ++;
}
}
swap(array, pivot, index - 1);
return index - 1;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
相关推荐
- 国产RISC-V终端Sipeed Lichee Console4A上架,1699元起
-
IT之家12月11日消息,国内著名开源硬件厂商Sipeed矽速科技推出RISC-V终端LicheeConsole4A,售价1699元(不带LM4A模块)-3299元。Li...
- H3C交换机常用配置命令
-
1、配置主机名...
- ThinkPad老版Bios中英文对应详解
-
ThinkPad老版Bios中文对应详解。解决方案:...
- 澳大利亚Console Connect与非洲数据中心达成战略合作,增强整个非洲的数据连接
-
据techafricanews网11月13日报道,在2024年非洲科技节上,澳大利亚ConsoleConnect与非洲数据中心共同宣布了一项具有里程碑意义的战略合作协议,该协议致力于提升非洲大陆关键...
- 多功能调焦 腾龙TAP-in Console延期发售
-
最新消息传出,腾龙TAP-inConsole(modeltap-01)多功能调焦器由于生产方面原因原本预计3月24日发售延迟至3月30日,腾龙的这款调焦器功能类似于适马的USBDock调焦底座,...
- 关于交换机上存在的不同接口介绍(一)
-
生活中常见的电子设备有很多,其中明交换机主要起到的是连接的作用,上面有非常多的接口,下面就一起来看看这些不同的接口作用是什么。1、RJ-45接口这是我们见的最多、应用最广的一种接口类型,它属于双绞线以...
- 颜值更高?微软新推精英版Xbox One手柄
-
本月,微软的XboxOne升级了更强大的版本——XboxOneEliteconsole(精英版?),升级版的控制手柄功能更强大,可以主导你的客厅;从曝光的图片上看得出,新版XboxOneE...
- “全球首个”:Console Connect为全球物联网项目推出连接解决方案
-
据DevelopingTelecoms2月27日报道,在MWC2023上,全球网络即服务(NaaS)平台ConsoleConnect推出了“全球首个”私有连接解决方案,可帮助企业在全球范围内动态...
- 密码遗忘专题——Console口密码遗忘
-
如果忘记了Console口密码,用户可以通过以下两种方式来设置新的Console口密码:方法一:通过STelnet/Telnet登录设备修改Console口密码。...
- 为锐捷路由器交换机开启web和telnet,实现轻松管理
-
笔者上一篇文章写了关于锐捷二层交换机配置教程,那么接下来讲一下锐捷的路由交换设备配置web、telnet技巧。同样,今天的教程也是基于命令行,比较简单,适合新手小白进行学习。准备工作配置前准备:con...
- C# - 类文件构成,C#基本语法,Console属性与方法 007
-
类文件(.cs)构成类文件主要分为引用命名空间与自己项目的命名空间...
- Console OS系统帮你在PC上自由切换Windows和安卓应用
-
通过ConsoleOS你可以在你的PC上安装自己喜欢的安卓游戏,需要时之间切换回Windows进行其他工作,ConsoleOS能够完全利用你的PC硬件配置,该系统可以安装在PC的内置硬盘里,也可以...
- 交换机通过串口线console口登录设备
-
一、功能简介:PC端通过设备的Console口登录,实现对第一次上电的设备进行基本配置和管理。...
- (每日持续更新)jdk api之Console基础、应用、实战
-
博主18年的互联网软件开发经验,从一名程序员小白逐步成为了一名架构师,我想通过平台将经验分享给大家,因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验,晚上进行用心精简、整...
- KFC推出“真正的次世代主机”KFConsole!真4K/120帧
-
今天KFCGaming官方推特发布了一则“主机”宣传片,正式公布了旗下名为KFConsole的全新主机产品。并宣称:游戏的未来就在这里,介绍真正的次世代主机!根据官方介绍,本款KFC主机功能强大,支...
你 发表评论:
欢迎- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了,如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
推荐7个模板代码和其他游戏源码下载的网址
-
其实模版网站在开发工作中很重要,推荐几个参考站给大家
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)