排序算法
一、排序基本知识
排序算法:
排序算法是用来将一且元素按照某种顺序进行排列的算法。排序算法多种多样,通常,我们可以用稳定性、是否基于比较、时间/空间复杂度、实现起来是否简单等指标评估排序算法是否优秀。排序算:个元素,在排序后是否仍然保持去的稳定性是指关键字相同的两原来的顺序。基于比较是排序过程中是否进行了元素之间的大小比较。
1、选择排序
选择排序的思想非常简单直接: 选择最小的元素放到第一个位置,选择第二小的元素放在第二个位置,以此类推。
2、冒泡排序
冒泡排序的思想是每次检查相邻的元素,如果不符合排序规则,就交换它们的位置如果所有相邻的元素都符合排序规则,则排序完成。在比较的过程中,较大的元素会像气泡一样慢慢冒到数列的末尾,故将这种方法称为冒泡排序。
3、插入排序
插入排序的思想是把数组分为两部分,且前半部分有序而后半部分无序,每次把无序部分的第一个元素插入有序部分合适的位置。
4、计数排序
计数排序的思想是统计1~ m这m 个数的出现次数,并根据出现次数得到有序的数组.如图4.5 所示,数字1出现了0次,数字2出现了1次,数字3出现了2次,数字4出现了2次,所以排序后的数字依旧是 1个2,2个3,2个4,也就是 23 3 4 4。计数排序是种不基于比较的排序算法,有时也会被称为桶排序,实际上这种说法不太严谨,应该说计数排序是一种特殊的桶排序。桶排序的思想是将 1~ m 分成很多个桶,向每个桶里装入一定范围内的数(比如,每个数分为一个桶),并将装有数的桶继续划分成更小的桶。计数排序可以看作一开始就划分成 m 个大小为 1的桶的排序。另外,还有一种排序算法叫作基数排序,虽然与计数排序读音类似,但它们是两种不同的排序算法。
4、快速排序
快速排序采用了分治的思想,排序时首先选择一个元素作为划分依据,把数组划分成两部分,要求左半边的所有元素都小于等于右半边,如图 4.6 所示,紧接着分别对左、右两部分的元素进行快速排序即可。
5、归并排序与快速排序一样用到了分治的思想,不同的是,归并排序每次都直接把序列一分为二,分别对左半边和右半边的序列进行排序。排序完成后,再将有序的两部分合并即可。
经典习题
[2022 年第12题]以下排序算法的常见实现中,哪个选项的说法是错误的?( )
B、简单选择排序是稳定的
A、冒泡排序算法是稳定的
D、归并排序算法是稳定的
C、简单插入排序是稳定
【解析】:选项中提到的4种算法里,简单选择排序是不稳定的
[答案] B
习题
1、有一台计算机使用选择排序对200个数宇排序共用了100ms,如果花费400ms,大概能对多少个数宇进行排序?( )
A、400
B、800
C、1600
D、3200
[解析] 选择排序的时间复杂度为 O(),也就是说,数据量扩大n倍,时间将扩大倍本题中时间扩大了4倍,则对应的数据量扩大了2倍,大对200×2-400个数字进排序。
[答案]A
2、以下哪个要法不是基于比较的排序算法?( )
A、冒泡排序
B、快速排序
C、计数排序
D、归并排序
[解析]计数排序不是基于比较的排序算法
[答案]C文章来源:https://www.toymoban.com/news/detail-823746.html
3、将数组 {4,1,6,8,2,3,7,5}中的元素按从小到大的顺序排素,最少需要交换 ( ) 次。
A.4
B.5
C.6
D.7
[解析]最少次数的交换顺字是:元素4和8交换位置,元素和5交换位置,元素5和2交换位置,元素2和1交换位置,元素3 和6交换位置,共交换了 5 次能实现数组从小到大排序。
[答案]B文章来源地址https://www.toymoban.com/news/detail-823746.html
到了这里,关于J组一等奖冲刺:排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!