如何分析排序算法
分析方法
执行效率
对于排序算法执行效率的分析,不仅仅只是简简单单的一个时间复杂度。
还需要从以下方面进行分析:
- 最好情况、最坏情况、平均情况时间复杂度。对于排序算法来说,有序度不同的数据,对于排序的执行时间有一定的影响,从多个方面分析时间复杂度会更加准确
- 时间复杂度的系数、常数、低阶。在实际开发中,大多是对一些规模较小的数据进行排序,实际运行速度是非常快的,这时候也可以把系数、常数、低阶考虑进来
- 比较次数或交换(移动)次数。常见的排序算法都是基于比较的,这时候会涉及到元素比较大小和元素交换或移动,这时候比较次数和交换次数也会影响到执行效率
内存消耗
在算法中,内存消耗基本上通过空间复杂度来衡量。
但是,在排序算法中,会有一个新的概念用来衡量内存消耗,即 原地排序。原地排序算法特指不需要另外空间存储的排序算法,空间复杂度能达到 \(O(1)\)。
稳定性
针对排序算法,还有稳定性这样一个重要的度量指标。
这个概念是指,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
常见排序算法
常见的排序算法有很多,这里列出 10 种排序算法作比较。而这 10 种常见的排序算法会根据是否进行比较分为两种:
- 比较类排序:冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序、归并排序
- 非比较排序:计数排序、桶排序、基数排序
排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 稳定 |
选择排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 不稳定 |
插入排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 稳定 |
希尔排序 | \(O(n^{1.3 \sim 2})\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 不稳定 |
堆排序 | \(O(n\log_2n)\) | \(O(n\log_2n)\) | \(O(n\log_2n)\) | \(O(1)\) | 不稳定 |
快速排序 | \(O(n\log_2n)\) | \(O(n^2)\) | \(O(n\log_2n)\) | \(O(n\log_2n)\) | 不稳定 |
归并排序 | \(O(n\log_2n)\) | \(O(n\log_2n)\) | \(O(n\log_2n)\) | \(O(n)\) | 稳定 |
计数排序 | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | 稳定 |
桶排序 | \(O(n+k)\) | \(O(n^2)\) | \(O(n)\) | \(O(n+k)\) | 稳定 |
基数排序 | \(O(n \times k)\) | \(O(n \times k)\) | \(O(n \times k)\) | \(O(n+k)\) | 稳定 |
如何选择合适的排序算法?
选择依据
在实际开发的时候,并不是时间复杂度低的排序算法就能适用于任何场景。
比如说,计数排序算法适用于较集中的小范围整数序列,桶排序算法适用于容易划分为桶的均匀整数序列,计数排序适用于可划分为具有递进关系的“位”的整数序列。
一般来说,对于小规模的数据进行排序时,可以选择时间复杂度是 \(O(n^2)\) 的排序算法;对于大规模的数据进行排序时,需要选择时间复杂度是 \(O(n \log n)\) 的排序算法;对于非比较类排序算法,主要应用于特定的场景。
这样选择的原因是,时间复杂度为 \(O(n^2)\) 的排序算法会比 \(O(n \log n)\) 的排序算法的效率低,一般指的都是时间复杂度在没有系数、常数、低阶介入比较的情况,当真正使用的时候,这些是不可避免的。
因此,在实际使用时,有些时候 \(O(n^2)\) 的排序算法也会比 \(O(n \log n)\) 的排序算法的效率高。
通常,为了兼顾任意规模数据的排序,在一个方法中会使用到多种排序算法。
排序实现 - Glibc
例如 Glibc 的 qsort()
函数,数据量较小时会优先使用归并排序算法来对输入数据排序,当数据量比较大时,qsort()
会改用快速排序算法来排序。
在归并排序中,每个元素小于 32 时,会直接进行归并排序;当有元素大于 32 时,则先将元素的指针拷贝到临时空间,再使用归并排序对指针进行排序。
在快排过程中,元素个数小于等于 4 个时候,会使用插入排序代替快速排序。
排序实现 - Java
例如 JDK 8 中 Arrays.sort()
的底层实现,也根据不同的情况使用到多种排序算法。
对于元素个数小于 47 的序列,使用的是插入排序算法;对于元素个数大于 47 而小于 286 的序列,使用的则是快速排序算法。
而对于超过 286 个元素的序列,还会判断这个序列是否结构化(数据是否时升时降),结构化的序列会使用归并排序算法,而非结构化的序列仍然会使用快速排序算法。
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023