朕培创客-高中-Scratch-课件：10-排序

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