1、选择性必修一数据与数据结构第五章 数据结构与算法5.3.2 排序算法的程序实现知识回顾请写出冒泡排序的第一遍手动过程返回冒泡排序的基本过程与规则1.排序的最少遍数为n-12.每遍进行的基本过程。第一遍，对n个元素冒泡，加工完毕，最大值23“下沉”至数组最后第一个元素的位置；第二遍，对n-1个元素冒泡，加工完毕，最大值20“下沉”至数组最后第二个元素的位置；第n-1遍，对2个元素冒泡，加工完毕，最大值13“下沉”至数组最后第n-1个元素的位置；3.排序完成。深化排序返回排序过程中，按下面的方式使用变量i和j:i：记录正进行的处理遍数，第1遍处理时值为1，第2遍处理时值为2，依次类推。j：记录当前
2、数组元素的下标。每遍处理过程中，j值总是从第一个数组元素的下标值0开始，按每次加1的方式，直至j=n-i-1为止。每当j取定一个值后，当前数组元素dj将与它的后一个元素dj+1进行比较，若dj dj+1，则互换这两个数组元素中的数据。冒泡排序的程序实现第一遍排序的程序实现for j in range(0,length-1):if LjLj+1:temp=Lj Lj=Lj+1 Lj+1=temp找出规律动手编程def bubble_sort(L):length=len(L)#序列长度为length，需要执行length-1遍加工 for i in range(1,length):for j in
3、 range(0,length-i):if LjLj+1:temp=Lj Lj=Lj+1 Lj+1=temp小组讨论：迭代式如何来的？冒泡排序算法的每一遍加工中，最小的元素“上浮”和最大的元素“下沉”这两种方式在程序实现时有何区别？冒泡排序的基本过程冒泡排序的程序实现冒泡排序的程序结构选择排序的程序实现课堂小结5.3.3 数据排序的应用情境导入奥运排行榜部分数据（Excel数据）编号国家/地区人口数量（万）金牌银牌铜牌总数8中国13640751212810020印度130420102353美国3226236383611021印度尼西亚26110113513巴西205293481523尼日利亚1
4、8231013452俄罗斯14253232128726日本12703961025抽象与建模返回问题：从表中的数据可以看出，每个国家的信息是一条记录，包括编号、国家/地区、人口数量、各奖牌数等数据项。根据刚才的实践体验，对记录按关键字排序，交换应当如何进行？设计算法与数据结构返回数据组织形式有两种，哪种更方便？一是采用7个一维数组按列存储，即每个数组分别存储每个国家的编号、国家/地区、人口数量、各奖牌数等，如定义b数组存储表中8个国家的金牌数量，其对应的值为51,1,36,1,3,0,23,9；二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如8,中国,136407,51,
5、21,28,100对应中国的相关信息。程序实现返回import csv#数据读入csvFile=open(jp.csv,r)#打开相应数据文件reader=csv.reader(csvFile)#建立一个读入数据的对象a=for item in reader:a.append(item)csvFile.close()#排序for i in range(1,len(a)-1):#排序不包含第一行数据 for j in range(1,len(a)-i):if int(aj3)int(aj+13):temp=aj aj=aj+1 aj+1=temp#数据写入csvFile2=open(jp2.cs
6、v,w,newline=)writer=csv.writer(csvFile2,dialect=excel)m=len(a)for i in range(m):writer.writerow(ai)csvFile2.close()小组讨论：排序的稳定性一般情况下，数据规模较小，各种排序方法的时间耗费差异较小，选择面较大；当数据规模较大时，冒泡排序、选择排序的时间复杂度为O(n2)，一般不会选用，常用的有快速排序、归并排序、堆排序、希尔排序等，时间复杂度为O(n log2 n)，python中使用的排序方法为TimSort，它实质上是对归并排序的优化，目前认为是最优秀的排序方法。稳定性是指排序前后，相同的数据项前后关系会不会带来变化，冒泡排序是稳定的，快速排序是不稳定的；数据结构也对排序有很大影响，编程的复杂度不同，空间复杂度不同。一般情况下，降低了时间复杂度，就会带来较高的空间复杂度；降低了空间复杂度，会带来较高的时间复杂度。对较特殊的数据比如在一定范围内的整数，使用桶排序，时间复杂度达到O(n),但空间复杂度会提高，需要较多的辅助空间。记录的关键字排序注意事项排序算法的三步骤不同数据组织形式对算法的实现影响排序算法的稳定性课堂小结课堂作业1.完成课后练习
