各种排序算法相关性质整理

时间：2024-10-05 20:33:22浏览次数：1

排序算法	稳定性	最优时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度
选择排序	不稳定	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$
冒泡排序	稳定	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$
插入排序	稳定	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$
计数排序	稳定	$O(N+W)$	$O(N+W)$	$O(N+W)$	$O(W)$
基数排序（使用计数排序为内层排序）	稳定（取决于内层排序）	$O(kN+\sum_{i=1}^{k}w_i)$	$O(kN+\sum_{i=1}^{k}w_i)$	$O(kN+\sum_{i=1}^{k}w_i)$	$O(k+N)$
快速排序	不稳定	$O(NlogN)$	$O(NlogN)$	$O(N^2)$	$O(1)$
归并排序	稳定	$\Theta(NlogN)$	$\Theta(NlogN)$	$\Theta(NlogN)$	$O(N) / O(1)$
堆排序	不稳定	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(1)$
桶排序（使用插入排序为内层排序）	稳定（取决于内层排序）	$O(N)$	$O(N+N^2/k+k)$	$O(N^2)$	$O(k)$
希尔排序	不稳定	$O(N)$	$O(NlogN)$	$o(N^2)$	$O(1)$
锦标赛排序	不稳定	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(N)$
tim排序	稳定	$O(N)$	$O(NlogN)$	$O(NlogN)$	$O(N)$

标签：稳定,NlogN,复杂度,内层,算法,整理,排序,sum
From： https://www.cnblogs.com/jerrycyx/p/18448449

算法练习记录(24.10.5)
1.B.BrightnessBegins思路要求最后的灯泡打开的数量，由于一开始灯泡是打开的，如果最后还需要打开，那么操作数量一定是偶数，移目至操作前提，需要灯泡的序号能整除$x$，由于遍历1~x，推出最后灯泡$i$亮的条件是：$1~i$中有偶数个$i$的因数，即$i$有偶数个因数，反之即有奇数个......
Dijkstra算法，动态规划和滑动窗口
一：最小花费题目链接：1928.规定时间内到达终点的最小花费-力扣（LeetCode）（1）Dijkstra算法理解问题：首先，我们需要理解问题的核心是找到一条从城市0到城市n-1的路径，这条路径在不超过给定时间 maxTime 的前提下，通行费之和最小。图的表示：由于城市之间是通过双向道路连接的......
Github项目列表临时存放待整理
中台Admin前后端分离的权限管理系统 AutoUpdater.NET是一个类库，允许.NET开发人员轻松地将自动更新功能添加到其经典桌面应用程序项目中。该库仅适用于WinForms或WPF应用程序项目。 NLocalizer是一个类库，供C#和VB.NET开发人员使用文本文件本地化其经典桌面应用程序......
[算法] 容斥
对于某些毒瘤计数题，经常会出现统计重复或遗漏的问题，这时候就可能需要容斥一下容斥原理先从一个经典的例子入手：有三个学科，设为$S_1,S_2,S_3$，有一堆人选不同的学科，现已知选每门学科各自有多少人选，求一共有多少人选学科；根据题意，我们要求的就是：$\midS_1\bigcupS_2\bigc......
代码随想录算法训练营day3|● 203.移除链表元素 ● 707.设计链表 ● 206.反转链表
学习资料：https://programmercarl.com/链表理论基础.html#链表的类型可设置虚拟头结点dummy_head链表最后指向Null一个节点包含值和索引学习记录：203.移除链表元素（基本ListNode(),cur.next,cur.next.val）点击查看代码#Definitionforsingly-linkedlist.#classListNod......
YOLOv8算法改进【NO.138】基于细节增强卷积改进YOLO算法
前言 YOLO算法改进系列出到这，很多朋友问改进如何选择是最佳的，下面我就根据个人多年的写作发文章以及指导发文章的经验来看，按照优先顺序进行排序讲解YOLO算法改进方法的顺序选择。具体有需求的同学可以私信我沟通：首推，是将两种最新推出算法的模块进行融合形成......
YOLOv10/8算法改进【NO.139】借鉴RCS-YOLO算法改进
前言 YOLO算法改进系列出到这，很多朋友问改进如何选择是最佳的，下面我就根据个人多年的写作发文章以及指导发文章的经验来看，按照优先顺序进行排序讲解YOLO算法改进方法的顺序选择。具体有需求的同学可以私信我沟通：首推，是将两种最新推出算法的模块进行融合形成......
9-贪心算法
参考：代码随想录题目分类大纲如下：贪心算法理论基础什么是贪心？贪心的本质是选择每一阶段的局部最优，从而达到全局最优。贪心的套路（什么时候用贪心）贪心算法并没有固定的套路，说白了就是常识性推导加上举反例。靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要......
算法
常见的算法思想比较笨的穷举算法思想又称为枚举法把所有可能枚举一边，效率低。递推从已知到未知，从小到大典型代表：斐波那契数列，由前两项推后一项递归指一种直接或间接地调用原算法本身的算法在程序中不断反复的调用自身来达到求解问题的方法递归调用实际上是自身调用自身......
归并排序
inttmp[];//temp数组存储数据voidmerge_sort(inta[],intl,intr){if(l>=r)return;//递归到最后只有一个数返回intmid=(l+r)/2;//确定分界点l~midmid+1~r;merge_sort(a,l,mid);merge_sort(a,mid+1,r);//递归左右两边intk=0,i=l,j=mid+1;......

排序算法	稳定性	最优时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度
选择排序	不稳定	\(O(N^2)\)	\(O(N^2)\)	\(O(N^2)\)	\(O(1)\)
冒泡排序	稳定	\(O(N)\)	\(O(N^2)\)	\(O(N^2)\)	\(O(1)\)
插入排序	稳定	\(O(N)\)	\(O(N^2)\)	\(O(N^2)\)	\(O(1)\)
计数排序	稳定	\(O(N+W)\)	\(O(N+W)\)	\(O(N+W)\)	\(O(W)\)
基数排序（使用计数排序为内层排序）	稳定（取决于内层排序）	\(O(kN+\sum_{i=1}^{k}w_i)\)	\(O(kN+\sum_{i=1}^{k}w_i)\)	\(O(kN+\sum_{i=1}^{k}w_i)\)	\(O(k+N)\)
快速排序	不稳定	\(O(NlogN)\)	\(O(NlogN)\)	\(O(N^2)\)	\(O(1)\)
归并排序	稳定	\(\Theta(NlogN)\)	\(\Theta(NlogN)\)	\(\Theta(NlogN)\)	\(O(N) / O(1)\)
堆排序	不稳定	\(O(NlogN)\)	\(O(NlogN)\)	\(O(NlogN)\)	\(O(1)\)
桶排序（使用插入排序为内层排序）	稳定（取决于内层排序）	\(O(N)\)	\(O(N+N^2/k+k)\)	\(O(N^2)\)	\(O(k)\)
希尔排序	不稳定	\(O(N)\)	\(O(NlogN)\)	\(o(N^2)\)	\(O(1)\)
锦标赛排序	不稳定	\(O(NlogN)\)	\(O(NlogN)\)	\(O(NlogN)\)	\(O(N)\)
tim排序	稳定	\(O(N)\)	\(O(NlogN)\)	\(O(NlogN)\)	\(O(N)\)

各种排序算法相关性质整理

相关文章

赞助商

阅读排行