高中信息技术1.尝试使用插入排序法实现商品销量排序获奖课件ppt

这是一份高中信息技术1.尝试使用插入排序法实现商品销量排序获奖课件ppt，文件包含项目八第一课时pptx、项目八第一课时doc等2份课件配套教学资源，其中PPT共38页， 欢迎下载使用。
四、尝试使用插人排序法实现商品销最排序
在日常生活中经常可以看到各种排行榜，如关注度排行榜、流行歌曲排行榜、球队实力排行榜、销量排行榜等。许多网络购物平台提供当月最畅销的商品排行。假如某店铺中某一种类商品只有 6件不同价格的商品，若采用人工排序，由于数据量小，简单目测一下就可以得出排序结果。
但实际上大部分情况下的排序数据可能会是成千上万条，因此，采用人工的方式会耗时多，且容易出错。若采用合理的数据结构和算法，编程实现后，系统便能对大量数据进行自动排序，省时省力，且只要程序正确，基本不会出错。
将一组次序任意的数据元素转变为按其关键字（可以标识数据元素的某个数据项的值）递增（或递减）次序排列的过程，称为排序。
小时候你一定玩过扑克牌，当你在整理那些乱序的牌的时候，你想到的第一种方法一定是将这些新摸到的牌插入到对应的位置，以此来达到手牌有序。
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果符合条件（比前面的大或者小，自定义），则让他们交换位置。 2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前面的数据都是有序的。 3.重复步骤二，一直到数据全都排完。
让我们以数组为例，假设有下面的数组：
我们可以看到，前面3个元素已经有序，后面7个元素还是无序状态，这时候我们需要将第4个元素插入到相应的位置，这样有序序列就从3增加到4，无序序列就从7减小到6。
如果对于一个含有n个元素的完全无序的数组，我们可以把第一个元素视作有序，其余 n-1 个元素视为无序，因为只有一个元素的数组肯定是有序的，所以每次将无序序列的第n-1一个元素插入到相应位置后，问题的规模就减少1。如果我们重复 n-1 次，数组就从无序变为有序了。
最后我们用代码实现一下插入排序。
def insertin_srt(array): fr i in range(1, len(array)): v = array[i] j = i - 1 while j >= 0 and array[j] > v: array[j+1] = array[j] # 用前一个元素覆盖当前元素 j = j - 1 array[j+1] = v # 循环结束后，将 v 插入到相应位置 return array
若某家店铺某一类商品6个品种的月销量分别是21，25，49，25*，16，8，要对这些商品按销量进行排序，可采用顺序存储结构下的插入排序法，部分过程如图所示。
先将初始无序序列的6件商品销量数据存放在下标0~5某一数组中，然后将第一个商品销量数据21视作初始有序序列。将剩余的5件商品销量数据视作无序序列。接下来每次从无序序列中取第一个商品销量数据插入到有序序列的适当位置上。为了操作方便，插入的商品销量数据与有序序列中商品销量数据从后往前依次比较，一边比较一边将大的商晶销量数据往后移动，直至找到插入位置。
1.商品除了可以按销量排序外，还可以按什么排序？
2.生活中还有哪些排序的例子？
身高、年龄、体重等
1.参照上述步骤画出剩下的排序过程图。
2.若采用链式存储结构，请根据图所示，用文字描述排序过程，并画出每个过程图。谈谈使用顺序存储结构和链式存储结构实现插人排序，各有何特点，以及具体的算法是否相同；在数据量小和大的情况下分别用哪一种比较好。
插入排序过程(采用链式存储结构)： (1)将原始链表断成有序链表和无序链表。有序链表包括头结点和第一个数据结点，指针Head指向头结点。无序链表包括第二个数据结点开始的所有结点，指针p指向第二个数据结点。 (2)通过指针P获得下一个需要排序数据25(无序链表的第一个节点)。在有序链表中查找第一个大于25的数据结点9,在结点之前插入结点25。若找不到大于25的数据节点，则将结点25插在有序链表的最后。结点25插入有序链表后，断开与无序链表的连接。指针指向无序链表的下一个结点49。
插入排序过程(采用链式存储结构)： (3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下， 插入25:
插入排序过程(采用链式存储结构)： (3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下， 插入49:
插入排序过程(采用链式存储结构)： (3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下， 插入25*:
插入排序过程(采用链式存储结构)： (3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下， 插入16:
插入排序过程(采用链式存储结构)： (3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下， 插入8:
顺序存储结构与链式存储结构的比較： 对于插入位置，顺序存储结构可以从有序序列的首部开始查找也可以从尾部开始查找。链式存储结构通过指针指向下一个结点，因而单链表只能从有序序列的首部开始查找 顺序存储结构在进行插入、删除元素等操作时，需要移动其他元素时间复杂度高。而链式存储结构在进行插入、删除元素等操作时，只需要修改指针，时间复杂度低。在数据量小的时候，建议使用链式存储结构顺序存储结构使用下标表示元素之间的逻辑关系，不额外增加存储空间。链式存储结构需要额外的存储空间存储指针信息。在数据量大的时候，建议使用顺序存储结构。
3.在以下流程框图（局部）中完成插入排序算法（设数据在r数组中，n为元素个数）；编程序实现对大量商品数据进行排序，并运行测试。
程序：r=[21,25,49,25,16,8]i=1while i