Scratch学习课件-10-排序.ppt

1、10 排序排序 程序设计基础 2 home back first prev next last 本节目标本节目标 排序排序 外排序外排序 内排序内排序 插入排序插入排序 冒泡排序冒泡排序 快速排序快速排序 3 home back first prev next last 排序排序 2-1 排序排序(Sorting) 是计算机程序设计中的一种重是计算机程序设计中的一种重 要操作，它的功能是将一个数据元素（或记要操作，它的功能是将一个数据元素（或记 录）的任意序列，重新排列成一个关键字有录）的任意序列，重新排列成一个关键字有 序的序列。序的序列。 例如，例如， 8 3 2 1 7 4 6 5 1

2、2 3 4 5 6 7 8 4 home back first prev next last 排序排序 2-2 内排序，指的是待排序记录存放在计算机内内排序，指的是待排序记录存放在计算机内 存中进行的排序过程，内排序有多种算法，存中进行的排序过程，内排序有多种算法， 不同的算法，所用的时间和内存空间也不同不同的算法，所用的时间和内存空间也不同 外排序，指的是待排序记录的数量很大，以外排序，指的是待排序记录的数量很大，以 致内存一次不能容纳全部记录，在排序过程致内存一次不能容纳全部记录，在排序过程 中尚需对外存如硬盘进行访问的排序过程中尚需对外存如硬盘进行访问的排序过程 5 home back

3、first prev next last 插入排序插入排序 2-1 插入排序是这样实现的：插入排序是这样实现的： 1、新建一个空列表，用于保存已排序的有序数、新建一个空列表，用于保存已排序的有序数 列（我们称之为“有序列表”）。列（我们称之为“有序列表”）。 2、从原数列中取出一个数，将其插入“有序列、从原数列中取出一个数，将其插入“有序列 表”中，使其仍旧保持有序状态表”中，使其仍旧保持有序状态 3、重复、重复2号步骤，直至原数列为空。号步骤，直至原数列为空。 插入排序的，效率不高，但是容易实现。它借插入排序的，效率不高，但是容易实现。它借 助了助了“逐步扩大成果逐步扩大成果“的思想，使有序

4、列表的长的思想，使有序列表的长 度逐渐增加，直至其长度等于原列表的长度。度逐渐增加，直至其长度等于原列表的长度。 6 home back first prev next last 插入排序插入排序 2-2 编程，通过插入排序，完成编程，通过插入排序，完成 49 38 65 97 76 13 27 的升序排列的升序排列 7 home back first prev next last 冒泡排序冒泡排序 2-1 冒泡排序属于交换排序冒泡排序属于交换排序 1、将所有待排序的数字放入工作列表中。、将所有待排序的数字放入工作列表中。 2、从列表的第一个数字到倒数第二个数字，逐、从列表的第一个数字到倒数第

5、二个数字，逐 个检查：若某一位上的数字大于他的下一位，个检查：若某一位上的数字大于他的下一位， 则将它与它的下一位交换。则将它与它的下一位交换。 3、重复、重复2号步骤，直至再也不能交换。号步骤，直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同，冒泡排序的平均时间复杂度与插入排序相同， 也是非常容易实现的算法也是非常容易实现的算法 8 home back first prev next last 冒泡排序冒泡排序 2-2 9 home back first prev next last 快速排序快速排序 8-1 快速排序（快速排序（Quick sort）是对冒泡排序的一）是对冒泡排序

6、的一 种改进。它的基本思想是：种改进。它的基本思想是： 通过一趟排序将要排序的数据分割成独立的两通过一趟排序将要排序的数据分割成独立的两 部分，其中一部分的所有数据都比另外一部分部分，其中一部分的所有数据都比另外一部分 的所有数据都要小，然后再按此方法对这两部的所有数据都要小，然后再按此方法对这两部 分数据分别进行快速排序，以此达到整个数据分数据分别进行快速排序，以此达到整个数据 变成有序序列变成有序序列 10 home back first prev next last 快速排序快速排序 8-2 设要排序的数组是设要排序的数组是A1AN， 首先任意选取一个数据（通常选用第一个数据）首先任意选

7、取一个数据（通常选用第一个数据） 作为关键数据，作为关键数据， 然后将所有比它小的数都放到它前面，所有比然后将所有比它小的数都放到它前面，所有比 它大的数都放到它后面，它大的数都放到它后面， 这个过程称为一趟快速排序。这个过程称为一趟快速排序。 值得注意的是，快速排序不是一种稳定的排序值得注意的是，快速排序不是一种稳定的排序 算法，也就是说，多个相同的值的相对位置也算法，也就是说，多个相同的值的相对位置也 许会在算法结束时产生变动许会在算法结束时产生变动 11 home back first prev next last 快速排序快速排序 8-3 一趟快速排序的算法是：一趟快速排序的算法是：

8、1）设置两个变量）设置两个变量I、J，排序开始的时候：，排序开始的时候：I=1，J=N； 2）以第一个元素作为关键数据，赋值给）以第一个元素作为关键数据，赋值给key，即，即 key=A1； 3）从）从J开始向前搜索，即由后开始向前搜索，即每次开始向前搜索，即由后开始向前搜索，即每次 J=J-1，找到第一个小于，找到第一个小于key的值的值AJ，并与，并与AI交换；交换； 4）从）从I开始向后搜索，即由前开始向后搜索，即每次开始向后搜索，即由前开始向后搜索，即每次 I=I+1，找到第一个大于，找到第一个大于key的的AI，与，与AJ交换；交换； 5）重复第）重复第3、4、5步，直到步，直到 I

9、=J 12 home back first prev next last 快速排序快速排序 8-4-1 例如：待排序的数组例如：待排序的数组A的值分别是：的值分别是： 49 38 65 97 76 13 27 初始关键数据：初始关键数据：X=49 注意注意X在一趟排序中不变，在一趟排序中不变， 每次都是和每次都是和X进行比较，无论在什么位置，一趟进行比较，无论在什么位置，一趟 排序的目的就是把排序的目的就是把X放在中间，小的放前面，大放在中间，小的放前面，大 的放后面。的放后面。 按照第三步从后面开始找，第一次交换后：按照第三步从后面开始找，第一次交换后：27 38 65 97 76 13 4

10、9 第二次交换后：第二次交换后：27 38 49 97 76 13 65 ( 按照第四按照第四 步从前面开始找步从前面开始找X的值，的值，6549,两者交换两者交换) 13 home back first prev next last 快速排序快速排序 8-4-2 第三次交换后：第三次交换后：27 38 13 97 76 49 65 ( 按照第五按照第五 步将又一次执行算法的第三步从后开始找步将又一次执行算法的第三步从后开始找 ) 第四次交换后：第四次交换后：27 38 13 49 76 97 65 ( 按照第四按照第四 步从前面开始找大于步从前面开始找大于X的值，的值，9749,两者交换两者

11、交换) 此时再执行第三步的时候就发现此时再执行第三步的时候就发现 I=J，从而结束，从而结束 一趟快速排序一趟快速排序 经过一趟快速排序之后的结果是：经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于，即所有大于49的数全部在的数全部在49的后面，所的后面，所 有小于有小于49的数全部在的数全部在49的前面的前面 14 home back first prev next last 快速排序快速排序 8-5 快速排序就是递归调用此过程快速排序就是递归调用此过程在以在以49为中点分为中点分 割这个数据序列，分别对前面一部分和后面一部割这个数据序列，分别对前面一部分和

12、后面一部 分进行类似的快速排序，从而完成全部数据序列分进行类似的快速排序，从而完成全部数据序列 的快速排序，最后把此数据序列变成一个有序的的快速排序，最后把此数据序列变成一个有序的 序列序列 根据这种思想对于上述数组根据这种思想对于上述数组A的快速排序的全过程的快速排序的全过程: 初始状态初始状态 49 38 65 97 76 13 27 进行一次快速排序之后划分为进行一次快速排序之后划分为 27 38 13 49 76 97 65 分别对前后两部分进行快速排序分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序 76 97 65 经第三步和第

13、四步交换后变成 65 76 97 完成排序 15 home back first prev next last 快速排序快速排序 8-6 实践证明，快速排序是所有排序算法中最高效的实践证明，快速排序是所有排序算法中最高效的 一种。它采用了分治的思想：先保证列表的前半一种。它采用了分治的思想：先保证列表的前半 部分都小于后半部分，然后分别对前半部分和后部分都小于后半部分，然后分别对前半部分和后 半部分排序，这样整个列表就有序了。这是一种半部分排序，这样整个列表就有序了。这是一种 先进的思想，也是它高效的原因。因为在排序算先进的思想，也是它高效的原因。因为在排序算 法中，算法的高效与否与列表中数字

14、间的比较次法中，算法的高效与否与列表中数字间的比较次 数有直接的关系，而数有直接的关系，而“保证列表的前半部分都小于保证列表的前半部分都小于 后半部分后半部分“就使得前半部分的任何一个数从此以后就使得前半部分的任何一个数从此以后 都不再跟后半部分的数进行比较了，大大减少了都不再跟后半部分的数进行比较了，大大减少了 数字间不必要的比较。数字间不必要的比较。 16 home back first prev next last 快速排序快速排序 8-7 链表链表 list 用于存储待排序的数据用于存储待排序的数据 因为因为 Scratch 不支持递归，因此建立一个辅不支持递归，因此建立一个辅 助的链

15、表助的链表 sub_seq 用来记录生成的子序列的用来记录生成的子序列的 起始和终止元素的位置起始和终止元素的位置 变量变量 i, j 代表一趟排序的起始和终止元素的代表一趟排序的起始和终止元素的 位置位置 变量变量 key 表示一趟排序的关键数据表示一趟排序的关键数据 变量变量 temp 是临时变量，用于链表是临时变量，用于链表 list 第第i, j 元素的交换元素的交换 17 home back first prev next last 快速排序快速排序 8-8 18 home back first prev next last 总结总结 排序排序 外排序外排序 内排序内排序 插入排序插入排序 冒泡排序冒泡排序 快速排序快速排序