比较次数 |
交换次数 |
空间 |
类型 |
稳定性statble |
适用范围 |
|||||
最优 |
平均 |
最坏 |
最优 |
平均 |
最坏 |
|||||
冒泡排序 |
n(n-1)/2 |
n(n-1)/2 |
n(n-1)/2 |
0 |
n(n-1)/4 |
n(n-1)/2 |
O(1) |
基于比较排序交换 |
稳定 |
无任何实际使用范围;仅用于比较其他排序性能 |
插入排序 |
n-1 |
O(n^2) |
O(n^2) |
0 |
O(n^2) |
O(n^2) |
O(1) |
基于比较 |
稳定 |
当数据基本有序或者元素个数较少: |
二叉树排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(n) |
基于比较 |
不稳定 |
二叉树排序过程与快排等价,可分析快排性能 |
|||
选择排序 |
n(n-1)/2 |
n(n-1)/2 |
n(n-1)/2 |
0 |
O(n) |
O(n) |
O(1) |
基于比较 |
稳定 |
当比较的耗时,远小于交换的耗时. |
堆排序 |
O(nlogn |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
基于比较 |
不稳定 |
Top K问题:在一堆数据中选取前K(K>1)个数 |
归并排序Merge Sort |
O(nlogn |
O(nlogn) |
O(nlogn) |
O(1) |
O(nlogn) |
O(nlogn) |
O(N) |
基于比较 |
稳定 |
hadoop的reduce过程是一个归并过程(不是归并排序); |
原地归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
O(nlogn) |
O(nlogn) |
O(1) |
基于比较 |
稳定 |
最常见的是bottom up 归并 |
快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(1) |
O(nlogn) |
O(n^2) |
O(logn) |
基于比较 |
不稳定 |
|
最优 |
平均 |
最坏 |
||||||||
计数排序 |
O(n+2^k) |
O(n+2^k) |
O(n+2^k) |
O(n+2^k) |
非基于比较 |
稳定 |
||||
基数排序Radix Sort |
O(nk/s) |
O(nk/s) |
O(nk/s) |
O(n) |
非基于比较 |
稳定 |
在字符串中常见.基数排序中,需要使用到计数排序 |
|||
桶排序 |
O(n) |
O(nk) |
O(n^2k) |
O(nk) |
非基于比较 |
稳定 |
需要假定原始数据均匀分布于给定范围 |
另外:
-
锦标赛排序
锦标赛排序:是寻找第一和第二元素的最优比较次数的方法。 = N-1+logN,如果是要选择Top K元素,与heapsort基本无异,可以看成是heapsort的特例(较少次数比较的heapsort)
这个排序属于选择排序,因为每次都决定哪个元素需要和哪个比较或者交换,该算法思路可以扩展,如赛马问题:
赛马问题,是Top K问题的一个特例.
25匹赛马,5个跑道,也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的3匹马?
这里面,5个跑道,相当于5叉树,锦标赛排序,一次是比较2个元素,所以是2叉树。所以:基本思路是:5个,5个一组比较。
-
归并排序
归并排序可以用于求序列的”逆“。
交换、插入、选择,是比较排序的基本实现方式。交换:通过交换实现2个元素位置的正确性
插入:通过插入方式实现有序过程,因此数据是逐渐增加的过程。选择:是选择哪个元素进行比较或交者交换,在普通的选择排序中,可以不通过交换实现有序过程,比如构造空间O(n),原始序列不变的方式来实现。所以选择排序的一般实现虽然使用交换,但是并不属于基于交换方式的比较排序过程。
-
稳定与不稳定
稳定:稳定的排序是,总有一种实现方式使得对任意序列排序过程稳定。
不稳定:对于给定的排序算法的实现,总可以找到一个序列特例,其结果不稳定。
因此,快排,对case 1排序结果稳定,但并不说明快排是稳定的。
插入排序,如果实现方式中,每次比较<改成<=,这样,排序的结果是不稳定的,但这不能说,插入排序是不稳定的,是实现方式的问题,即,只要找到一种实现方式(用<号,而不是<=号)就可以实现稳定的排序。
-
原地排序
即使用原始序列进行排序,空间O(1),是衡量空间复杂度的。(注:总体来说,空间复杂度分析,要不时间复杂度分析难很多,而且空间限制通常比时间限制更难解决)。
-
排序的前提
传递性:a<b,b<c那么a<c
反自反性,a<b,那么!(b<a)
任意2个元素可比较
排序:是一个序列的“逆”的个数转换为0的过程。
相关推荐
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
排序算法时间复杂度的研究 期刊网站可是要现金的哦。
改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析
1. 首先产生要进行排序的整形数组(可以保存在文件中以备后用) 2. 调用各种排序方法对数组排序,并...对于更多更高级的排序算法,以后会实现,另外,对于复杂字符串排序,这些简单排序并不适合,请采用更高效的方法
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
各种排序算法的稳定性和时间复杂度总结。希望大家能有所收获。
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
常用排序算法的比较 复杂度 稳定性 shell 归并排序 插入排序 冒泡排序 快速排序 基数排序
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
算法时间复杂度
小排序算法的稳定性和时间复杂度
以堆排序算法为例,改变输入规模n,测试算法时间复杂度
常用排序算法时间复杂度、空间复杂度总结。包括:冒泡排序、快速排序、选择排序、堆排序、插入排序、Shell排序、归并排序、基数排序。
算法设计的好坏直接影响计算机的运行时间,计算机排序方法较多,时间复杂度差别较大. 本文从理论 上研究了线性排序(选择法、冒泡法、计数法) 、比较排序、堆排序和快速排序等几种常用的排序算法的时间复杂度.
C语言四种排序算法时间复杂度比较.doc
算法时间复杂度分析基础算法时间复杂度分析基础算法时间复杂度分析基础