一个个熟悉的排序

简介:
	排序,多么熟悉的词。在没有真正接触到它时,已经听闻了它的强大和重要性。如今,那一个个耳熟能详的排序算法,也渐渐的在自己面前揭开了它们的神秘面纱。
	那么多的排序算法,想一一总结一番。可是,在每个总结之前,有个宏观整体上的认识,感觉效果会更好些。所以,我们先从排序讲起。
	排序(Sorting)是数据处理中一种重要而且常用的运算。它就是将一组对象按照规定的次序重新排列的过程,往往是为检索服务的。
		下面我将从以上四个方面,宏观认识一下排序算法。
	首先,排序可分为两大类:
	(1)内部排序(Internal Sorting):待排序的记录全部存放在计算机内存中进行的排序过程。
	(2)外部排序(External Sorting):待排序的记录数量很大,内存不能存储全部记录,需要对外存进行访问的排序过程。
	后面讨论的算法都是指的内部排序。
	对于内部排序的方法,有很多种,主要总结的为排序、交换排序、选择排序和归并排序四类。
		相同键值的两个记录在排序前后相对位置的变化情况是排序算法研究中经常关注的一个问题,这个问题称为排序算法的稳定性。
	判断一种排序算法是否稳定,只需要看经过排序后,序列内相同键值的位置是否发生变化,如果没有变化,则是稳定的;如果位置发生了变化,则是不稳定的。
	比如,
			值得注意的是,稳定性是排序方法本身的特定,与数据无关,换句话说,一种排序方法如果是稳定的,则对所有的数据序列都是稳定的,反过来,如果一组数据上出现不稳定的现象,则该方法是不稳定的。
	下面是各种排序方法的稳定性比较:
	
	评价一个排序算法的优劣,通常可用时间复杂度和空间复杂度两个指标。我们主要讨论时间复杂度。
	在排序过程中主要有比较两个键值大小和将记录从一个位置移动到另一个位置这两种基本操作。因此,从键值的比较次数和记录的移动次数两个方面来分析时间复杂度。
	下面是各种排序算法的时间复杂度:
		
	到此为止,对排序算法的宏观认识也就结束了。主要是从排序的分类、方法、稳定性和时间复杂度四个方面剖析,并没有涉及到某一种排序方法的具体算法,这将是后面需要一个一个总结的工作。
	不管是软考还是自考,都需要学习和掌握排序算法。而此篇宏观性的博客,也主要是从自考的学习中着手,感觉思路更清楚,理解更容易。
 
 

目录
相关文章
|
存储 Java
【面试题精讲】为什么重写equals时必须重写hashCode方法?
【面试题精讲】为什么重写equals时必须重写hashCode方法?
|
9月前
|
人工智能
官宣!西安市数据局与阿里云达成合作
官宣!西安市数据局与阿里云达成合作
301 8
|
7月前
|
缓存 安全 数据可视化
如何让私有化部署不影响用户体验?产品经理必读指南
本文探讨了在数字化产品竞争中,用户体验(UX)与用户界面(UI)设计对产品成功的重要性。合理的UX设计能降低学习成本、提高效率,出色的UI设计则增强视觉吸引力和易用性。同时,随着数据安全需求提升,私有化部署成为企业重要考量。文章从用户导向设计、简化交互、优化性能等方面阐述如何提升用户体验,并结合私有化部署需求,探讨安全与体验的平衡点,确保产品既安全又易用。
|
7月前
|
安全 网络协议 数据建模
免费SSL证书最新申请全攻略
SSL证书分为三种类型:DV(域名验证型)适用于个人博客等,验证简单;OV(组织验证型)适用于电商、金融网站,需验证企业信息;EV(扩展验证型)提供更高信任级别。申请渠道有JoySSL(免费一年单域名证书)、Let's Encrypt(公共免费项目)和阿里云(免费DV证书,但有限制)。以JoySSL为例,申请流程包括注册账号、选择证书、填写信息、验证域名所有权、下载与安装。注意事项包括留意有效期、确保兼容性和使用最新版本证书,以保障网站安全。
|
9月前
|
前端开发 Java 数据库
玩转springboot之springboot注册servlet
在Spring Boot中注册Servlet非常灵活,可以通过 `@WebServlet`注解快速注册,也可以通过 `ServletRegistrationBean`进行细粒度控制。通过这两种方式,可以满足各种场景下的需求,确保应用能够高效处理HTTP请求。
757 14
java的事件驱动如何实现
java的事件驱动如何实现
|
10月前
|
弹性计算 安全 网络安全
阿里云服务器租用流程,四种阿里云服务器租用方式图文教程参考
阿里云服务器可以通过自定义租用、一键租用、云市场租用和活动租用四种方式去租用,不同的租用方式适合不同的用户群体,例如我们只是想租用一款配置较低且可以快速部署应用的云服务器,通常可以选择一键租用或者云市场租用,本文为大家展示不同租用方式的适合对象以及租用流程,以供初次租用阿里云服务器的用户参考和选择。下面是阿里云服务器租用的图文操作步骤。
10961 2
|
存储 安全 编译器
C/C中sizeof和strlen函数的实现:详细解析sizeof和strlen函数的实现机制、参数说明和使用技巧
C/C中sizeof和strlen函数的实现:详细解析sizeof和strlen函数的实现机制、参数说明和使用技巧
303 1
|
安全 关系型数据库 MySQL
WordPress建站之wp-config-sample.php文件
WordPress建站之wp-config-sample.php文件 WordPress 包含名为wp-config-sample.php的文件,让新用户了解常规 WordPress 配置文件的外观。下面北京六翼信息技术有限公司的开发工程师带我们看一下每个标准 WordPress 安装都包含的 WordPress 配置文件示例,并讨论可能的其他选项。查看文件中的注释,了解有关每一行实际含义的更多信息joowp。com。
WordPress建站之wp-config-sample.php文件
|
数据采集 SQL 数据可视化
Dataphin数据探查助力快速了解数据概貌,更早识别潜在风险
在日常数据加工处理工作中,不同角色(运营、开发、数据分析师、业务人员等)尝尝会面临一个共同问题:数据是否可用?在数据量大、数据可信度不高的情况下,常常需要花费大量时间精力对数据进行校验,了解数据概貌并评估数据是否可用,也就是需要进行所谓的“数据探查”工作。因此,Dataphin 特别推出“数据探查”功能,只需要进行简单的配置,就可以周期性地执行探查任务并产出内容丰富、结果准确的可视化探查报告。此外,也可以保留历史的数据探查结果,便于结合历史数据进行对比分析,不仅降低了操作门槛,也能解放人力,提升工作效率。
811 0