1.选择排序:不稳定,时间复杂度 O(n^2)
<wbr><wbr><wbr><span><span style="font-size:16px"><span style="color:#000000">选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。<span><wbr></wbr></span></span></span></span></wbr></wbr></wbr>
2.插入排序:稳定,时间复杂度 O(n^2)
<wbr><wbr><wbr><span><span style="color:#000000; font-size:16px">插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i] 又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j]
≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。</span></span></wbr></wbr></wbr>
3.冒泡排序:稳定,时间复杂度 O(n^2)
<wbr><wbr><span><span style="color:#000000"><span style="font-size:16px">冒泡排序方法是最简单的排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序</span>。</span><span><span style="font-family:Arial"><wbr></wbr></span></span></span></wbr></wbr>
4.堆排序:不稳定,时间复杂度 O(nlog n)
<wbr><wbr><wbr><span><span style="font-size:16px"><span style="color:#000000">堆排序是一种树形选择排序,在排序过程中,将A[n]看成是完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。<span><wbr></wbr></span></span></span></span></wbr></wbr></wbr>
5.归并排序:稳定,时间复杂度 O(nlog n)
<wbr><wbr><wbr><span><span style="color:#000000; font-size:16px">设有两个有序(升序)序列存储在同一数组中相邻的位置上,不妨设为A[l..m],A[m+1..h],将它们归并为一个有序数列,并存储在A[l..h]。</span><span><span style="font-family:Arial"><wbr></wbr></span></span><br></span></wbr></wbr></wbr>
6.快速排序:不稳定,时间复杂度 最理想 O(nlogn) 最差时间O(n^2)
<wbr><wbr><wbr><span><span style="color:#000000; font-size:16px">快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理它左右两边的数,直到基准点的左右只有一个元素为止。</span></span></wbr></wbr></wbr>
7.希尔排序:不稳定,时间复杂度 平均时间 O(nlogn) 最差时间O(n^s) 1<s<2
<wbr><wbr><wbr><span><span style="color:#000000; font-size:16px">在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。</span></span></wbr></wbr></wbr>
<wbr><wbr><strong> 稳定性<wbr></wbr></strong></wbr></wbr>
排序类别
|
|
时间复杂度
|
空间复杂度
|
1
|
插入排序
|
O(n2)
|
1
|
√
|
2
|
希尔排序
|
O(n2)
|
1
|
×
|
3
|
冒泡排序
|
O(n2)
|
1
|
√
|
4
|
选择排序
|
O(n2)
|
1
|
×
|
5
|
快速排序
|
O(Nlogn)
|
O(logn)
|
×
|
6
|
堆排序
|
O(Nlogn)
|
1
|
×
|
7
|
归并排序
|
O(Nlogn)
|
O(n)
|
√
|
快速排序与希尔排序比较
快速排序的最差复杂度可能会降为n^2,最快则是nlogn,但是,平均情况下是较快的。
而希尔排序的最差情况下,复杂度可能会降为n^s
到n^s之间,(1<=s<=2),平均则是nlog^2n。
理论上来看,希尔排序可能是效率比较高的。但是,实际情况来看,快速排序的实际效果很不错。
原因就是,快速排序在实际情况中,坏的情况是不太容易出现的(取中间值或随机值),坏情况概率低。
而希尔排序在实际情况中,效率就取决于他在求解过程中的增量,合理的增量是不好找的。
因此,经常会出现不爽的情况,坏的情况概率高。
分享到:
相关推荐
本项目主要使用Java实现各种经典常用数据结构及其算法,包括但不仅限于链表、栈,队列,树,图等经典数据结构。 八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序...
排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排 序,外部排序) 数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余...
本书还较为详细地分析了各种算法的时间复杂度和空间复杂度,介绍了分摊复杂度分析技术。作为各种数据结构和算法的应用,本书给出了图的标准界面及其实现。利用这个标准界面, 实现了图论中的一些经典算法。
数据结构算法在此回购中,我将用Swift编程语言... 以下是一些最常用的Big O表示法及其在不同大小的输入数据上的性能比较的列表。数据结构操作复杂度数组排序算法的复杂度作者 Baquer 执照该存储库是根据MIT许可授权的。
2.3.1 时间复杂度的组成 2.3.2 操作计数 2.3.3 最好、最坏和平均操作计数 2.3.4 步数 第3章 渐近记法 3.1 引言 3.2 渐近记法 3.2.1 大Ο记法 3.2.2 渐近记法Ω和Θ 3.3 渐近数学(可选) 3.3.1 大O记法 3.3.2 Ω记法...
简介: C语言是编程语言中的一朵奇葩,虽已垂垂老矣,但却屹立不倒,... 时间复杂度、冒泡排序法、选择排序法、快速排序法、归并排序法、顺序排序法、二分查找等常用算法的详细讲解; 良好的编码习惯和编程风格。
C语言是编程语言中的一朵奇葩,虽已垂垂老矣,但却屹立不倒,诞生了... 时间复杂度、冒泡排序法、选择排序法、快速排序法、归并排序法、顺序排序法、二分查找等常用算法的详细讲解; 良好的编码习惯和编程风格。
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B.(1),(2) C.(1),(4) D.(3) 7.从逻辑上可以把数据结构分为(C )两大类。【武汉...
龙 翀 -《解决空间规模问题的几种常用的存储结构》 骆 骥 -《数学模型的建立和选择》 施 遥 -《人工智能在围棋程序中的应用》 肖 洲 -《数据结构的在程序设计中的应用》 谢 婧 -《规模化问题的解题策略》 徐 串...
一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接等存储结构。 顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,结点之间的关系由存储...
重表的方式加以优化,以降低其时间和空间复杂度。 2. 总体架构 本项目总体架构如下图所示: 配置器 Configurator 超文本传输协议响应 HttpResponse 日志 Log 主线程 main 多路输入输出 MultiIo 插件管理器 ...
第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的算法。 第1章绪论.................................................................................................................
第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的算法。 第1章绪论................................................................................................................
第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的算法。 第1章绪论................................................................................................................
第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的算法。 第1章绪论.................................................................................................................