10种排序算法基础总结
基于比较的排序:
基础排序:
冒泡排序:谁大谁上,每一轮都把最大的顶到天花板 效率太低——掌握swap。
选择排序:效率较低,但经常用它内部的循环方式来找最大值和最小值。
插入排序:虽然平均效率低,但是在序列基本有序时,它很快,所以也有其适用范围。
希尔排序(缩小增量排序):是插排的改良,对空间思维训练有帮助 时间复杂度O(n1.3),介于O(nlgn)~O(n2)之间
分治法:
快速排序:是软件工业中最常见的常规排序法,其双向指针扫描和分区算法是核心,特别地partition算法用来划分不同性质的元素,如选择第K大元素的问题。快速排序时间复杂度为O(NlgN),但是如果主元不是中位数的话,特别地如果每次主元都在数组区间的一侧,复杂度将退化为N²,工业上的优化方法见快速排序分区以及优化方法。快速排序重视子问题的划分。
归并排序:分治法的完美使用,开辟了辅助空间,常见的题目如逆序对数,归并排序重视子问题的解的合并
堆排序:用到了二叉堆数据结构,是继续掌握树结构的起手式 堆排序 = 插排 + 二分查找
上面三个都是NlgN的复杂度,其中快排表现最好,是原址的不用开辟辅助空间;归并排序需要开辟辅助空间;堆排也是原址的,但是常数因子较大,不具备优势。
基于非比较排序:
计数排序:可以说是最快的,用它来解决问题时必须注意如果序列中的值分布非常广(最大值很大,元素分布很稀疏),那么空间将会浪费很多,所以计数排序的使用范围是:序列的关键字比较集中,已知边界,且边界较小。
桶排序:用它解决问题必须注意序列的值是否均匀地分布在桶中。如果不均匀,那么个别桶中的元素会远多于其他桶,桶内排序用比较排序,极端情况下,全部元素在一个桶内,那么复杂度还是会退化成NlgN。
基数排序:kN级别(k是最大数的位数)是整数数值型排序里面又快又稳的,无论元素分布如何,只开辟固定的辅助空间(10个桶),基数排序几乎不需要任何“比较”操作。因此,在实际应用中,对十进制整数来说,基数排序更好用。
上面三种排序其实都是支持负数的,我们可以找出最小的数来,计算出与0的距离,然后把所有的数同时减去这个距离,这样就全部成为自然数,排好序然后再恢复回去就OK了。
十种排序算法对比:
相关文章
- python TCP套接字服务器v1.1-新增服务端命令功能及修改bug(socket+PyQt5)
- tcp心跳包 - python TCP服务器v1.3 - 服务器抗压测试及关闭套接字处理
- python TCP服务器v1.2 - 服务端新增用户登录注册(json, md5加密)
- PullTube for Mac(在线视频下载工具)
- python TCP服务器v1.4 - 客户端连接服务器异常(异常情况分类)处理
- PyQt5可编辑下拉框(comboBox):editable - python TCP服务器v1.5 - 客户端连接界面增加自定义参数(设置超时, 连接地址可选)
- Python TCP服务器v1.6 - multiprocessing多进程及Ctrl-c(SIGINT)退出
- Python TCP服务器v1.7 - PyQt5 server服务端来临
- PyQt5渐变圆环水波进度条+透明淡入(多线程信号)
- python TCP服务器v1.8 - PyQt5登录界面美化+淡入淡出
- socketTCP协程文件+信息传递 - TCP聊天文件服务器v1.9 - 划时代的版本更新(4.6万字)
- python 70行完成requests抓取csdn阅读量.
- TCP聊天文件服务器v2.0 - 重大bug修复+PyQt5文件传输可视化
- TCP聊天文件服务器v2.1 - 服务端线程管理(threading.enumerate)
- 2023开年行 | 犀牛鸟er开启健康新征程
- TCP聊天文件服务器v2.2 - 服务端客户端套接字解决分包/粘包问题 - SocketQueue继承以及减少冗余
- 虹科分享|您的遗留系统的安全性如何?
- gzip的使用 - TCP聊天文件服务器v2.3 - 文件传输建立缓存制度和.gz的解压缩/压缩解决运行内存过大
- 网络传输测速 - TCP聊天+传输文件服务器服务器套接字v2.4 - socket协程文件传送测速
- TCP聊天+传输文件服务器服务器套接字v2.5 - socket测速规范已经gzip的弃用