芊爸升学圈 职教 3分钟了解信息竞赛必须掌握的10大经典排序算法

3分钟了解信息竞赛必须掌握的10大经典排序算法

目前100000+人已关注加入我们

20220614212030412 20220614212031384 20220614212032454 20220614212033994 20220614212034937 20220614212036975 20220614211707859 20220614212038764

20220614212039499 20220614212040865 20220614212039516 20220614212039716 aHR0cHM6Ly9tbWJpei5xbG9nby5jbi9tbWJpel9naWYvbGRGYUJOU2t2SGh0VkNMcHpvY1RpYzZkNjNJbFNvVlgxYklPWGlhWThheDM1TVluUWN2T1FGM1hVNUVpYXNiaWFjWDFtbkdUa3o4dUZmUGtRVEl3cHVxVjVnLzA 20220614212041750 20220614211709915 aHR0cHM6Ly9tbWJpei5xbG9nby5jbi9tbWJpel9naWYvbGRGYUJOU2t2SGh0VkNMcHpvY1RpYzZkNjNJbFNvVlgxMXhpYkdVV2liY3ZDQjhsVzNIZ2JCdGljaWJaOERDQ3NoVnVMaGI3NmE5V25nR0kyOUlYb0xqdDgyUS8w

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序外部排序

内部排序是数据记录在内存中进行排序。

而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

关于时间复杂度:

  1. 平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

  2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

  3. O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

  4. 线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性:

  1. 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

  2. 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

 

2、算法的分类

3、时间复杂度

算法

1、冒泡排序

它重复地访问要排序的元素列,一次比较两个相邻的元素,如果他们的顺序不符合预期就把他们交换过来。访问元素的工作是重复地进行直到没有相邻元素需要交换时为止。

2、快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

3、直接插入排序

直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。

4、选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

5、归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

6、堆排序

堆排序是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的升序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

7、希尔排序

希尔排序是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法把数组按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个数组恰被分成一组,算法终止。

8、计数排序

计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的时间复杂度为线性的O(n+k)(其中k是整数的范围,即max – min + 1),快于任何比较排序算法,这是一种典型的空间换时间的算法。

9、基数排序

基数排序属于“分配式排序”(Distribution Sort),它是透过键值的部分信息,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O(n*log(r)*m) ,其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

10、桶排序

桶排序的工作原理是将数组根据一定的策略均匀的分到有限数量的桶子里,再对每个桶里的内容进行排序。桶排序是鸽巢排序的一种归纳结果,当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间O(n) 。桶排序并不是比较排序,它不受到O(n*log(n)) 的下限的影响。

AlgorithmMan

AlgorithmMan-堆排序

AlgorithmMan-桶排序

AlgorithmMan-二叉树排序

 

冲击2021年蓝桥杯&CSP/NOIP

20220615174801600

  师资介绍  

宋老师

电子科技大学硕士

竞赛成绩:

荣获ACM-ICPC国际大学生程序设计竞赛亚洲赛区银奖

荣获ACM四川省大学生程序设计竞赛金奖

荣获第十一届蓝桥杯国家二等奖、省一等奖

荣获第十一届蓝桥杯省二等奖

荣获国际大学生程序设计竞赛亚洲邀请赛银奖

荣获四川省邀请赛金奖

教学经验:

长期为学校ACM竞赛队队员进行辅导培训

大学期间,帮助老师教学选修课《程序设计竞赛基础》

曾作为大学承办蓝桥杯的学生负责人

教学风格:

耐心细致,对知识盲区的每个方面力求讲清楚,讲全面

幽默诙谐,注重与同学的互动,提升课堂活跃度

善于用图像具体化抽象的思维,更有利于同学们理解与思维上的提升

▍来源:网络,所有图文仅供学习交流使用,如有侵权烦请告知,我们会立即删除。

本文来自网络,不代表芊爸升学圈立场,转载请注明出处:https://www.wish188.com/2021/02/21/10455.html

作者: 芊爸

芊爸陪你升学。
上一篇
下一篇

发表评论

您的电子邮箱地址不会被公开。

联系我们

联系我们

在线咨询: QQ交谈

邮箱: hhyyy9@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部