高中信息技术沪教版（2019）选修1 数据与数据结构3.尝试使用选择排序法实现商品销量排序精品课件ppt

项目八 模拟实现商品排序

——常用排序算法及其比较

第三课时 尝试使用选择排序法实现商品销量排序

❑教材分析

本节的主要内容是尝试使用选择排序法实现商品销量排序。以生活中经常需要对某些数据进行查找和排序，如销售统计、商品查找等为主线，整个项目分为尝试使用插入排序法实现商品销量排序、尝试使用㴘泡排序法实现商品销量排序、尝试使用选择排序法实现商品销量排序、比较三种排序方法四部分。

本课时的学习中，学生将尝试使用直接选择排序等方法对模拟的网络购物平台中的店铺销售数据进行排序。在使用直接选择排序中的直接选择排序对6件商品销量数据进行排序的过程中，教材先给出了使用顺序存储结构下的排序示意图(部分)，然后在活动中要求学生完成剩下的步骤示意图以及链式存储结构下的排序过程描述，并完成算法流程图设计和程序的编写，最后上机运行得出结果。

本项目强调引导学生在理解、掌握三种排序方法的基础上，对它们的基本特点和稳定性进行分析。通过本项目的学习，学生能够掌握基本的排序方法，理解排序算法与数据结构的关系，从而学会根据实际问题选择恰当的算法完成数据的排序。

本节课时将从身边熟悉的事例出发，带领学生探究各种排序和查找算法，在学习过程中体验迭代和递归的方法，并理解算法与数据结构的关系，进一步发展学生的计算思维和数字化学习与创新的能力。

❑教学目标

1.掌握常用的数据排序方法——直接选择排序；

2.理解三种排序算法的特点。

3.理解排序算法与数据结构的关系。

4.能通过Python编程实现三种排序算法。

5.培养学生的信息意识和计算思维能力。

❑教学重点

1.掌握常用的数据排序方法；

2.理解排序算法与数据结构的关系。

❑教学难点

1.理解插入排序算法的特点；

2.培养学生的信息意识和计算思维能力。

❑教学方法

体验法、讲授法、讨论法、示例法

❑教学准备

　　计算机教室、多媒体设备、多媒体广播软件、Python编程环境、待排序的商品数据、教学课件等。

❑教学过程

一、新课导入

回顾并提出问题：若要销量相同的商品保持原来的先后顺序，该如何实现？引导学生分析采用选择排序能否实现。

二、选择排序法

1.核心概念

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

2.基本思想

排序定义。所谓计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法（Sorting algorithm）则是一种能将一串数据依照特定的方式进行排列的一种算法。

排序方式。利用所需重排记录的排序码（Sort Key）的值的大小，按照升序或降序将原纪录的顺序重新安排。排序类别。内排序可以分为插入排序（insertion sort）、选择排序（selection sort）、交换排序（exchange sort）、归并排序（merge sort）以及分配排序（distribution sort）。

选择排序法是在要排序的一组数中，选出最小（或最大）的一个数与第一个位置的数交换；在剩下的数当中找最小的与第二个位置的数交换，即顺序放在已排好序的数列的最后，如此循环，直到全部数据元素排完为止。

3.算法描述

选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换 。

4.类别

常见的选择排序可以分为直接选择排序（Straight selection sort）、树形选择排序（Tree-type selection sort）以及堆排序（Heap sort）。

（1）直接选择排序。

①基本思想。实现思想是每步从排序记录中选出排序码最小（最大）的记录，放在已排序记录序列的最后（前）；

②算法特点。直接选择排序算法n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

（2）树形选择排序。

①基本思想。其实现思想是保存先前比较的结果以减少比较次数，是一种不稳定的排序方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

（3）堆排序。

①基本思想。堆排序是一种树形选择排序，是对直接选择排序的有效改进；

②算法描述。从算法描述来看，堆排序需要两个过程，即建立堆和堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成，一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数；

③算法特点。堆排序可通过树形结构保存部分比较结果，可减少比较次数。但由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

5.具体实现方法

①初始状态：无序区为R[0..n-1]（共n个元素），有序区为空。 

②第1趟排序

设置一个变量i，让i从0至n-2循环的同时，在对比数组中元素i跟元素i+1的大小，如果R[i+1]比R[i]小，则用一个变量k来记住他的位置（即k=i+1）。等到循环结束的时候，我们应该找到了R中最小的那个数的位置了。然后进行判断，如果这个最小元素的不是R的第一个元素，就让第一个元素跟他交换一下值，使R[0..0]和R[1..n-1]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[0..i-1]和R[i..n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[0..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 

图1为一个具体例子：（通过寻找最小值的选择排序）

6.Python实现

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

三、尝试使用选择排序法实现商品销最排序

若采用选择排序，每趟排序将未完成排序序列中的最小数依次和未完成排序序列中第一个数交换，过程如图5-5所示。

图5-5选择排序各趟排序后的结果

思考与讨论？

选择排序结点的移动次数与序列的初始排列状态有关，那结点的比较次数与序列的初始排列状态有关吗？

无关。

四、比较三种排序方法

上述三种排序算法都能实现商品销量排行榜，但每种排序算法都有各自的特点，如表5-1所示。

表5-1 排序方法基本特点比较

小贴士 

稳定性：待排序列中相同关键字(如25、25*)排序后相对位置不发生变化的排序称为稳定的排序。             

五、课堂活动

1.在以下流程框图(局部)中完成选择排序算法(设数据在r数组中，n为元素个数)，编程实现，并运行测试。

参考答案：

程序：

r=[21,25,49,25,16,8]

i=0

while i<5:

min=i

j=i+1

while j<=S:

if r[j]<r[min]:

min=j

j=j+1

if i!=min:

temp=r[i]

r[i]=r[min]

r[min]=temp

i=i+1

for e in r:

print(e)

2.请针对上述表格中的各排序方法特点和稳定性给出具体的理由。

参考答案：

插入排序：

(1)无序序列中待排序数据与有序序列中的数据从后往前依次比较，一边比较一边将大的数据往后移动，直至找到插入位置待排序列基本有序情况下，比较次数和移动次数都较少。排序迷度快。

(2)待排序数据与有序序列中的数据从后往前依次比较，当遇到值相同时，不再继续往前比较，直接插入在值相同的数据的后面。这样值相同的数据保持在原序列中的相对位置不发生变化，所以插入排序是稳定的。

冒泡排序：

(1)冒泡排序第一趟排序冒出最小的数，第二趟排序冒出第二小的数，依次类推执行n-1遍完成全部排序。使用冒泡排序不需要完成所有数据排序就可得排行榜的前几名。

(2)冒泡排序针对排序数据元素，两两比较关键字，若发现存在逆序(两个关键字按非递增次序排列)，则交换这两个数据元素。持排序列基本有序情况下，交换次数较少，排序速度快。

(3)冒泡排序中若两个关键字相等，则不进行交换。这样值相同的数据保持在原序列中的相对位置不发生变化，所以冒泡排序是稳定的。

选择排序：

(1)选择排序在选取最小关键字的数据元素的过程中，只记录下标，不交换数据，只有在选出最小关键字的数据元素后，才进行数据交换，因此排序过程中数据的移动次数少。

(2)选择排序第一遍选出最小的数，第二遍选出第二小的数，依次类推执行n-1遍完成全部排序。使用选择排序不需要完成所有教据排序也可得排行榜的前几名。

(3)选择排序中，相同关键字数据元素中原先位置在前面的元素可能被交换到后面去，所以选择排序是不稳定的。

3.某商品品种繁多，假设有1000种，已知商品是按商品编号排列的，现要求尽快地找出价格最低的前10种商品，若有价格相同就按商品编号顺序排列，那么选用哪种排序方法才能较好地完成此项工作呢？请给出理由，并编程实现。

冒泡排序是稳定的，不需要完成所有数据排序就可得排行榜的前几名，所以选择冒泡排序。

程序：

import random

number=[]  #number列表保存商品编号

price=[] #number列表保存商品价格

i=0

while i<1000:

number.append(i)

price.append(random.randint(1,1000))

i=i+1

i=0

while i<999:

j=999

while j>=1:

if price[j]<price[j-1]：

temp=price[j]

price[j]=price[j-1]

price[j-1]=temp

temp=number[i

number[j]=number[j-1]

number[j-1]=temp

j=j-1

i=i+1

i=0

print('price',’’,'number')

while i<10:

print(price[i],'   ',number[i])

i=i+1