上
次参加了一个公司的笔试,其中有一道题是:写出快速排序的原理,并要求写出代码。而自己当时只写出了原理,但没能写出代码,回来就开始研究各种排序的
Java实现,发现其中有许多的难点,记得当年学习数据结构的时候还自认为自己学得还可以,当我看到快速排序的时候才发现,原来自己真的很菜,连原理都说
错了,于是学习ing。
1
)分类:
1
)插入排序(直接插入排序、希尔排序)
2
)交换排序(冒泡排序、快速排序)
3
)选择排序(直接选择排序、堆排序)
4
)归并排序
5
)分配排序(箱排序、基数排序)
所需辅助空间最多:归并排序
所需辅助空间最少:堆排序
平均速度最快:快速排序
不稳定:快速排序,希尔排序,堆排序。
2)
选择排序算法的时候
1.
数据的规模; 2.数据的类型 ; 3.数据已有的顺序
一般来说,当数据规模较小时,应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。
考虑数据的类型,比如如果全部是正整数,那么考虑使用桶排序为最优。 考虑数据已有顺序,快排是一种不稳定的排序(当然可以改进),对于大部分排好的数
据,快排会浪费大量不必要的步骤。数据量极小,而起已经基本排好序,冒泡是最佳选择。我们说快排好,是指大量随机数据下,快排效果最理想。而不是所有情
况。
3
)总结:
——按平均的时间性能来分
:
1
)时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好;
2
)时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为最好,特
别是对那些对关键字近似有序的记录序列尤为如此;
3
)时间复杂度为O(n)的排序方法只有,基数排序。
当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
——按平均的空间性能来分
(指的是排序过程中所需的辅助空间大小):
1
) 所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1);
2
) 快速排序为O(logn
),为栈所需的辅助空间;
3
) 归并排序所需辅助空间最多,其空间复杂度为O(n
);
4
)链式基数排序需附设队列首尾指针,则空间复杂度为O(rd
)。
——排序方法的稳定性能:
1
) 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和
经过排序之后,没有改变。
2
) 当对多关键字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。
3
) 对于不稳定的排序方法,只要能举出一个实例说明即可。
4
) 快速排序,希尔排序和堆排序是不稳定的排序方法。
分享到:
相关推荐
第三部分“排序”(第6~11章)按章节顺序分别讨论基本排序方法(如选择排序、插入排序、冒泡排序、希尔排序等)、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法,...
例如目前许多国际著名的计算机公司所举办的各种认证考试绝大部分采用这种方式。 三、论题的研究现状及其发展评述 在线考试是现阶段研究开发的一个热点。它是建立在国际互联网上的应用系统,客户端的配置可以极为简单...
大部分章节含有一个“Q & A”部分,来回答该章节相关的一些常见问题。注意,某些问题会由于知识点的关联性重复出现在多个章节。这些问题、答案及其附带的示例代码都包含在本文档的附录部分。 一、...
目前在美团的团购系统中大量地应用到了机器学习和数据挖掘技术,例如个性化推荐、筛选排序、搜索排序、用户建模等等,为公司创造了巨大的价值。本文主要介绍在美团的推荐与个性化团队实践中的数据清洗与特征挖掘方法...
第二部分 排序和顺序统计学 引言 第6章 堆排序 6.1 堆 6.2 保持堆的性质 6.3 建堆 6.4 堆排序算法 6.5 优先级队列 第7章 快速排序 7.1 快速排序的描述 7.2 快速排序的性能 7.3 快速排序的随机化...
第二部分 排序和顺序统计学 引言 第6章 堆排序 6.1 堆 6.2 保持堆的性质 6.3 建堆 6.4 堆排序算法 6.5 优先级队列 第7章 快速排序 7.1 快速排序的描述 7.2 快速排序的性能 7.3 快速排序的随机化...
本书结构合理,可读性强,加之每章精心设计的习题集,更加适合教学。 本书论述清晰,示例生动,并附有大量习题,适合作为高等院校计算机及相关专业本科生和研究生的教材或参考书。原版自1993年出版第1版到2003年...
中国农村统计年鉴《中国农村统计年鉴—2018》由17部分组成:一、发展综述;二、综合与概要;三、农村基本情况与农业生产条件;四、农业生态与环境;五、农村投资;六、农林牧渔业总产值、中间消耗及增加值;七、主要农产品...
.NET关于string转换的一个小Bug Regular Expressions 完整的在.net后台执行javascript脚本集合 ASP.NET 中的正则表达式 常用的匹配正则表达式和实例 经典正则表达式 delegate vs. event 我是谁?[C#] 表达式计算引擎...
从2005年起,我刊的版面费调整为200元/页(6页之内),超出部分400/页。为此,请您严格按照要求尽量压缩。 2. 提供基金类别和项目编号 为了说明论文所研究课题的重要性,若有基金资助,请在文章首页的左下角写明准确...
绝大部分的解都给出了数学证明。这些算法都根据精确定义的复杂度衡量方法进行分析。本书还讲述针对许多典型问题的算法、各类系统模型及其能力。章后提供大量习题并列出了详细的参考文献。 本书可作为高等院校...
第一部分 综述 第1章 BSD系统的历史和目标 1.1 UNIX系统的历史 1.1.1 UNIX系统的起源 1.1.2 Research小组的UNIX系统 1.1.3 AT&T UNIX System III和System V 1.1.4 伯克利软件发布(BSD) 1.1.5 UNIX无处不在 1.2 ...
爬虫技术研究综述 网页搜索策略 网页分析算法 补充 展开 编辑本段概述 引言 随着网络的迅速发展,万维网成为大量信息的载体,如何有效地提取并利用这些信息成为一个巨大的挑战。搜索引擎(Search Engine),...
关于在广告/网络门户中提供的信息在多大程度上有助于明智的决策,尚未进行很多研究。 该研究旨在确定散户投资者的信息需求,以便他们就共同基金产品的投资及其对印度共同基金产品的在线营销的影响做出明智的决定。 ...
把鼠标定位到表/视图/存储过程名称之上,按F4,可以打开对象描述窗口,方便的查看表和视图的定义,存储过程的源代码, 非常容易对SQL语句的分析其执行计划:单击工具栏上的 按钮就可以看到Explain Plan的...
《jQuery权威指南》除了理论知识丰富而全面外,它还有一个最大的特点就是注重实战,每个知识点都有一个完整的案例,包括需求分析、代码实现和结果展示三个部分,而且还包含两个综合性的案例,它的实践性之强是目前...