Scratch

状课网-少儿编程网课专业平台

Scratch 跟我学scratch编程:最基本的三种排序算法(1)

发布时间:2021-11-26 11:44:10 浏览 0

  CC哥每天都在考虑应该跟大家分享些什么,最近在跟一些朋友在探讨学编程的意义的时候,大家还是很多人目的是为了信竞的,那考虑到大家的一致诉求,CC哥也会加入一些算法的课程。当然CC哥尽量不用C++来教这些知识,尽量用理论和例子来跟大家做交流。

  今天主要跟大家聊一些最基本的算法知识,在计算机算法中,排序怕是最重要和最基础的部分了,在大量的数据处理中,一个优秀的算法可以节省大量的时间。排序的算法很多种,各有利弊。有的算法非常简单,但是效率不高。有的算法效率很高,但是比较复杂,占用的存储空间也多。算法还分为稳定和不稳定,稳定的算法在碰到同样的值的时候,并不会改变原始的排序,而不稳定的算法,在排序过程中对于同样的值可能会改变原始的排序。

跟我学scratch编程:最基本的三种排序算法(1)

  稳定排序就是一个考点,大家要了解哪些排序是稳定的,哪些是不稳定的。通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

  今天CC哥跟大家介绍最基本的三种排序算法:

  一:选择排序选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n - 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。

  排序过程

  对以下序列进行排序:(例子摘自网上)

  49 38 65 97 76 13 27 49

  第一趟排序后 13 [38 65 97 76 49 27 49]

  第二趟排序后 13 27 [65 97 76 49 38 49]

  第三趟排序后 13 27 38 [97 76 49 65 49]

  第四趟排序后 13 27 38 49 [76 97 65 49]

  第五趟排序后 13 27 38 49 49 [97 65 76]

  第六趟排序后 13 27 38 49 49 65 [97 76]

  第七趟排序后 13 27 38 49 49 65 76 [97]

  最后排序结果 13 27 38 49 49 65 76 97

  不过要注意:选择排序不是一个稳定排序,它是一个不稳定排序。

  举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

  二:插入排序插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。

  排序过程

  对以下序列进行排序:(例子摘自网上)

  例如:设n=8,数组a中8个元素是: 36,25,48,12,65,43,20,58,执行插入排序程序后,其数据变动情况:

  第0步:[36] 25 48 12 65 43 20 58

  第1步:[25 36] 48 12 65 43 20 58

  第2步:[25 36 48] 12 65 43 20 58

  第3步:[12 25 36 48] 65 43 20 58

  第4步:[12 25 36 48 65] 43 20 58

  第5步:[12 25 36 43 48 65] 20 58

  第6步:[12 20 25 36 43 48 65] 58

  第7步:[12 20 25 36 43 48 58 65]

  大家注意,如果是相等的元素,那么相等的元素是插入在后面,所以不会改变其排序。所以插入排序是一个稳定的排序算法。

  三:冒泡排序

  冒泡排序CC哥有一讲的例子就是讲的冒泡排序,大家可以参考一下,是用scratch做的冒泡排序。

  冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。

  排序过程

  对以下序列进行排序:

  有6个元素需要排序: 8 5 3 1 4 2

  第一趟:

  5 8 3 1 4 2

  5 3 8 1 4 2

  5 3 1 8 4 2

  5 3 1 4 8 2

  5 3 1 4 2 8

  第一趟结束,就把最大的8放到最后了。

  第二趟:

  3 5 1 4 2 8

  3 1 5 4 2 8

  3 1 4 5 2 8

  3 1 4 2 5 8

  第二趟结束,就把倒数第二大的数字放在了倒数第二个。

  后面按照这种方法继续,一共需要n-1次就完成了整个排序。

  所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

跟我学scratch编程:最基本的三种排序算法(1)

  排序算法的评估除了稳定性之外,还有时间复杂度和空间复杂度两个概念,顾名思义,时间复杂度,就是花费的时间了,也就是排序需要执行多少次。这三种排序的方法都是时间复杂度比较高的。平均都是O(N2)。空间复杂度就是顾名思义是排序额外需要占用的空间,今天谈的这三种排序空间复杂度比较低的,只有O(1)。

  下一次CC哥用Scratch把插入排序和选择排序给大家做个例子看一下,冒泡之前做过了,就不再重复了。大家也可以自己试试看。另外以后CC哥会逐渐把其他的排序也都跟大家做个讲解。有些复杂的排序用scratch很难编程,到时候就给大家展示一下C++的编程例子。

  为了丰富今后的教学内容,CC哥在这里做个调查,喜欢的朋友可以给出你的建议哦。

 

  文章来源:跟我学scratch编程

本文链接:https://www.ascratch.com/news/17643.html

上一篇:跟我学scratch编程:俄罗斯方块续 下一篇:返回列表