十大经典排序算法之快速排序 快速排序的算法分析
yuyutoo 2024-10-12 01:08 5 浏览 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;
}
相关推荐
- 国内外注塑机及电脑密码大全(常见注塑机通用密码)
-
一、国外注塑机(日本、德国等)东洋注塑机万能码:9422345日精注塑机密码:222|7777DAMEG注塑机密码:000000000新泻注塑机密码:241650|261450住友注塑机密码:...
- 并发编程实战来咯(并发编程的艺术和并发编程实战)
-
提到并发编程,就不得不提C++ConcurrencyinAction(SecondEdition)(《C++并发编程实战第2版》)啦!《C++并发编程实战第2版》英文原版&中文译版看到这个...
- 无锁队列Disruptor原理解析(无锁队列应用场景)
-
队列比较队列...
- 无锁CAS(附无锁队列的实现)(cas是一种无锁算法)
-
本文所有代码对应的Github链接为:https://github.com/dongyusheng/csdn-code/tree/master/cas_queue...
- Linux高性能服务器设计(linux 服务器性能)
-
C10K和C10M计算机领域的很多技术都是需求推动的,上世纪90年代,由于互联网的飞速发展,网络服务器无法支撑快速增长的用户规模。1999年,DanKegel提出了著名的C10问题:一台服务器上同时...
- 浅谈Go语言的并发控制(go语言 并发)
-
前言本文原创,著作权归...
- Datenlord |Etcd 客户端缓存实践(etcd 数据存储)
-
简介和背景...
- 无锁编程——从CPU缓存一致性讲到内存模型
-
缓存是一个非常常用的工程优化手段,其核心在于提升数据访问的效率。缓存思想基于局部性原理,这个原理包括时间局部性和空间局部性两部分:...
- 如何利用CAS技术实现无锁队列(cas会锁总线吗)
-
linux服务器开发相关视频解析:...
- Kotlin协程之一文看懂Channel管道
-
概述Channel类似于Java的BlockingQueue阻塞队列,不同之处在于Channel提供了挂起的send()和receive()方法。另外,通道Channel可以...
- 详解C++高性能无锁队列的原理与实现
-
1.无锁队列原理1.1.队列操作模型...
你 发表评论:
欢迎- 一周热门
-
-
前端面试: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)