高中信息技术浙教版（2019）选修1 第五章　课时3　数据排序 学案（含答案）.docxVIP

课时3数据排序

课时目标

1.通过具体实例，理解排序的概念和基本方法。2.能根据实际的应用场景，选择合理的数据结构，并使用排序算法来编程解决问题。

1.排序

(1)排序的概念

排序是指将一些________的数据变成________的数据。

(2)排序方式

排序方式主要有：________(从小到大排列)和________(从大到小排列)。

(3)待排数据的存储方式

待排数据通常存储在数组或链表中。

2.常见的排序算法

常见的排序方法有：____________、__________、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。

3.利用Python的sort方法和内建函数sorted排序

(1)sort方法

说明：使用sort方法对列表中的数据进行排序时，将____________对列表进行排序，不会产生________列表。

例：列表lista＝[36，23，12，17，22，19，28]，可用命令lista.sort()将列表lista中的数据进行升序排序，可用命令lista.sort(reverse＝True)将列表lista中的数据进行降序排序。

(2)sorted函数

说明：使用sorted函数进行排序时，将排好序的数据返回一个____________。

例：lista＝[36，23，12，17，22，19，28]，执行语句listb＝sorted(lista)后，列表listb中的元素为[12，17，19，22，23，28，36，]，从而实现升序排序；执行语句listc＝sorted(lista，resverse＝True)后，列表listc中的元素为[36，28，23，22，19，17，12]，从而实现降序排序。

4.冒泡排序

(1)冒泡排序的基本思想

冒泡排序是在数列中对________两个数据依次进行________和位置调整，让较大的数“下沉(或上冒)”，较小的数据“上冒(或下沉)”的一种排序技术。

(2)冒泡排序的特点

①________两个数据进行比较。

②n个数据完成排序，共进行________趟(遍)排序。

③n个数据完成排序，数据的比较次数为eq\f(n（n－1）,2)。

④n个数据完成排序，其时间复杂度为________。

5.冒泡排序算法的程序实现

说明：对列表list1中的数据进行升序排序

defbubble_sort(list1)：

count＝len(list1)

#count个数排序共需进行count－1趟

foriinrange(1，count)：

#每一趟排序从前往后进行，比较相邻两个数

forjinrange(0，count－i)：

iflist1[j]list1[j＋1]：

list1[j]，list1[j＋1]＝list1[j＋1]，list1[j]

returnlist1

(1)冒泡排序进行时，数据的比较可以由前往后进行，即list1[j]与listl[j＋1]比较；也可以由后往前进行，即list1[j]与list1[j－1]比较，此时应将循环条件“forjinrange(0，count－i)：”修改为“forjinrange(count－1，i－1，－1)：”。

(2)若要将数据按降序排列，只需将语句“iflist1[j]list1[j＋1]：”修改为“iflist1[j]list1[j＋1]：”即可。

例1采用冒泡排序算法对数据序列“21，15，23，26，33，18，46，17”完成升序排序，理论上讲共需进行排序的遍数为()

A.3遍 B.4遍 C.7遍 D.8遍

听课笔记：

变式训练采用冒泡排序算法对数据序列“16，11，8，9，21，32，28”完成升序排序，共进行数据交换的次数为()

A.3次 B.4次 C.5次 D.6次

例2采用冒泡排序算法对8个数据“48，65，29，16，22，75，36，41”进行降序排序，则第3遍的排序结果是()

原始数据

48，65，29，16，22，75，36，41

第1遍完成后的数据为

75，48，65，29，16，22，41，36

第2遍完成后的数据为

75，65，48，41，29，16，22，36

第3遍完成后的数据为

A.75，65，48，41，36，29，16，22

B.75，65，48，41，29，16，22，36

C.75，65，48，41，36，29，22，16

D.75，65，48，4