《高中-Scratch-ppt课件：10_排序》由会员分享，可在线阅读，更多相关《高中-Scratch-ppt课件：10_排序（17页珍藏版）》请在金锄头文库上搜索。
1、1home back first prev next last本节目标本节目标排序排序外排序内排序插入排序冒泡排序快速排序2home back first prev next last排序排序 2-1排序排序(Sorting) 是是计算机程序算机程序设计中的一种中的一种重要操作，它的功能是将一个数据元素（或重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关）的任意序列，重新排列成一个关键字字有序的序列。有序的序列。例如， 8 3 2 1 7 4 6 5 1 2 3 4 5 6 7 8 3home back first prev next last排序排序 2-2内排序，指
2、的是待排序内排序，指的是待排序记录存放在存放在计算机内算机内存中存中进行的排序行的排序过程，内排序有多种算法，程，内排序有多种算法，不同的算法，所用的不同的算法，所用的时间和内存空和内存空间也不同也不同外排序，指的是待排序外排序，指的是待排序记录的数量很大，以的数量很大，以致内存一次不能容致内存一次不能容纳全部全部记录，在排序，在排序过程程中尚需中尚需对外存如硬外存如硬盘进行行访问的排序的排序过程程4home back first prev next last插入排序插入排序 2-1插入排序是插入排序是这样实现的：的： 1、新建一个空列表，用于保存已排序的有序数列（我们称之为“有序列表”）。2
3、、从原数列中取出一个数，将其插入“有序列表”中，使其仍旧保持有序状态3、重复2号步骤，直至原数列为空。插入排序的，效率不高，但是容易实现。它借助了逐步扩大成果的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。5home back first prev next last插入排序插入排序 2-2编程，通程，通过插入排序，完成插入排序，完成 49 38 65 97 76 13 27 的升序排列的升序排列6home back first prev next last冒泡排序冒泡排序 2-1冒泡排序属于交冒泡排序属于交换排序排序1、将所有待排序的数字放入工作列表中。2、从列表的第一个数字到
4、倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。3、重复2号步骤，直至再也不能交换。冒泡排序的平均时间复杂度与插入排序相同，也是非常容易实现的算法7home back first prev next last冒泡排序冒泡排序 2-28home back first prev next last快速排序快速排序 8-1快速排序（快速排序（Quick sort）是）是对冒泡排序的一冒泡排序的一种改种改进。它的基本思想是：。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分
5、别进行快速排序，以此达到整个数据变成有序序列9home back first prev next last快速排序快速排序 8-2设要排序的数要排序的数组是是A1AN，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动10home back first prev next last快速排序快速排序 8-3一趟快速排序的算法是：一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=1，J
6、=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=J11home back first prev next last快速排序快速排序 8-4-1例如：待排序的数例如：待排序的数组A的的值分分别是：是： 49 38 65 97 76 13 27 初始关键数据：X=49 注意X在一趟排序中不变，每次都是和X进行比较，无论在什么位置，一趟排序的目的就是
7、把X放在中间，小的放前面，大的放后面。按照第三步从后面开始找，第一次交换后：27 38 65 97 76 13 49第二次交换后：27 38 49 97 76 13 65 ( 按照第四步从前面开始找X的值，6549,两者交换) 12home back first prev next last快速排序快速排序 8-4-2第三次交换后：27 38 13 97 76 49 65 ( 按照第五步将又一次执行算法的第三步从后开始找) 第四次交换后：27 38 13 49 76 97 65 ( 按照第四步从前面开始找大于X的值，9749,两者交换) 此时再执行第三步的时候就发现I=J，从而结束一趟快速排序
8、经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于49的数全部在49的后面，所有小于49的数全部在49的前面13home back first prev next last快速排序快速排序 8-5快速排序就是快速排序就是递归调用此用此过程程在以在以49为中点中点分割分割这个数据序列，分个数据序列，分别对前面一部分和后面一前面一部分和后面一部分部分进行行类似的快速排序，从而完成全部数据序似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列列的快速排序，最后把此数据序列变成一个有序成一个有序的序列的序列根据根据这种思想种思想对于上述数于上述数组A的快速排序
9、的全的快速排序的全过程程: 初始状态49 38 65 97 76 13 27 进行一次快速排序之后划分为27 38 13 49 76 97 65 分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序 76 97 65 经第三步和第四步交换后变成 65 76 97 完成排序 14home back first prev next last快速排序快速排序 8-6实践践证明，快速排序是所有排序算法中最高效的明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保一种。它采用了分治的思想：先保证列表的前半列表的前半部分都小于后半部分，然后分
10、部分都小于后半部分，然后分别对前半部分和后前半部分和后半部分排序，半部分排序，这样整个列表就有序了。整个列表就有序了。这是一种是一种先先进的思想，也是它高效的原因。因的思想，也是它高效的原因。因为在排序算在排序算法中，算法的高效与否与列表中数字法中，算法的高效与否与列表中数字间的比的比较次次数有直接的关系，而数有直接的关系，而保保证列表的前半部分都小于列表的前半部分都小于后半部分后半部分就使得前半部分的任何一个数从此以后就使得前半部分的任何一个数从此以后都不再跟后半部分的数都不再跟后半部分的数进行比行比较了，大大减少了了，大大减少了数字数字间不必要的比不必要的比较。15home back fi
11、rst prev next last快速排序快速排序 8-7链表表 list 用于存用于存储待排序的数据待排序的数据因因为 Scratch 不支持不支持递归，因此建立一个，因此建立一个辅助的助的链表表 sub_seq 用来用来记录生成的子序生成的子序列的起始和列的起始和终止元素的位置止元素的位置变量量 i, j 代表一趟排序的起始和代表一趟排序的起始和终止元素止元素的位置的位置变量量 key 表示一趟排序的关表示一趟排序的关键数据数据变量量 temp 是是临时变量，用于量，用于链表表 list 第第i, j 元素的交元素的交换16home back first prev next last快速排序快速排序 8-817home back first prev next last总结总结排序排序外排序内排序插入排序冒泡排序快速排序
