项目八 模拟实现商品排序-常用排序算法及其比较-高中信息技术同步精品课堂（沪科版2019选择性必修1）

项目八模 拟 实 现 商 品 排 序 — 常用排序算法及其比较 01 02 03 了解排序算法与数据结构之间的关系。 了解商品排序是如何实现的，知道排序的概念，掌握计算机常用的集中排序算法。 学习目标 理解插入排序法、冒泡排序法、选择排序法各自的特点，并会区别使用。 01 情景导入 导入 若某家店铺某一类商品 6 个品种的月销量分别是 21，25，49，25，16，8，要对这些商品按销量进行排序，你知道怎么排序么？ 1. 尝试使用插入排序法实现商品销量排序 先将初始无序序列的 6 件商品销量数据存放在下标0～5 某一数组中，然后将第一个商品销量数据 21 视作初始有序序列。将剩余的 5 件商品销量数据视作无序序列。接下来每次从无序序列中取第一个商品销量数据插入到有序序列的适当位置上。为了操作方便，插入的商品销量数据与有序序列中商品销量数据从后往前依次比较，一边比较一边将大的商品销量数据往后移动，直至找到插入位置。 1.请采用插入排序法对序列（Q,H,C,Y,P,A,M,S,R,D,F,X)中的数据元素按字母序的升序进行排序，编程并上机调试。 练习题 r=['Q','H',C';,'Y ','P",'A','M','S",'R','D' F",X'"]i=1 while i<12: temp=r[i]j=i-1 while temp<r[i] and j>=0: r[j+1]-ri] j=j-1rli+1]=tempi=i+1 for e in r: print(e) 若采用冒泡排序法，则将这些销量数据看成水里的气泡，数字大小表示气泡的轻重，最先冒出最轻的（最小数），第二次冒出第二轻的，以此类推，如图 5-4 所示，图中斜线下是无序的，斜线上是已冒出的有序的。实现冒泡的方法：从序列最后两个元素开始比较，只要后面元素小，则交换；交换上去的再与最后第三个元素比较，以此类推，这样两两相邻元素比较就冒出当前最小元素。 2. 尝试使用冒泡排序法实现商品销量排序 2.请采用冒泡排序法对序列（Q,H,C,Y,P,A,M,S,R,D,F,X)中的数据元素按字母序的升序进行排序，编程并上机调试。 活 动 若采用选择排序，每趟排序将未完成排序序列中的最小数依次和未完成排序序列中第一个数交换，过程如图 5-5 所示。 3. 尝试使用选择排序法实现商品销量排序 4. 比较三种排序方法 上述三种排序算法都能实现商品销量排行榜，但每种排序算法都有各自的特点，如表 5-1 所示。 02 知识链接 将一组次序任意的数据元素转变为按其关键字（可以标识数据元素的某个数据项的值）递增（或递减）次序排列的过程，称为排序。例如，表 5-2 所示商品销售表可以按序（主关键字，可以唯一标识一个数据元素）递增进行排序，也可以按单价或销量（次关键字，可识别若干数据元素）进行排序。排序后，每个数据元素的顺序会按关键字的顺序排列。排序方法有插入排序（直接插入排序、折半插入排序、希尔排序等）、交换排序（冒泡排序、快速排序）、选择排序（直接选择排序、堆排序等）、归并排序等。 排序 常用的插入排序有直接插入排序、折半插入排序和希尔排序。本单元项目采用的是直接插入排序。直接插入排序的思想是将数据元素序列（初始无序序列）分成两部分，一部分为有序序列，另一部分为无序序列，将无序序列中的每一个元素依次插入到有序序列中。即将待排序数据元素按其关键字的大小插入到有序序列的适当位置上。插入排序的比较次数取决于各元素的初始排列情况。 直接插入排序过程示例如下： 5，3，7，2，4，6（原始序列） 3，5，7，2，4，6（将无序序列 3，7，2，4，6 中的 3 插入到有序序列 5 前） 3，5，7，2，4，6（将无序序列 7，2，4，6 中的 7 插入到有序序列 3，5 后） 2，3，5，7，4，6（将无序序列 2，4，6 中的 2 插入到有序序列 3，5，7 最前面） 2，3，4，5，7，6（将无序序列 4，6 中的 4 插入到有序序列 2，3，5，7 的 3 后） 2，3，4，5，6，7（将 6 插入到 5 后，排序完成） 1. 插入排序 交换排序是针对排序数据元素，两两比较关键字，若发现存在逆序（两个关键字按非递增次序排列），则交换这两个数据元素，一直到待排序数据元素序列中没有逆序为止。常用的排序方法有冒泡排序和快速排序。本单元项目采用的是冒泡排序。冒泡排序的思想是：设 n 为序列的元素个数，用相邻的两两比较方法第一次在 n 个数中冒出最小数，第二次在 n-1 个数中冒出最小数（序列的第二小数），第三次在 n-2 个数中冒出最小数（序列的第三小数）……共冒 n-1 次。 冒泡排序过程示例如下： 5，3，7，2，4，6（原始序列） 2