高中信息技术5.3 数据排序图文ppt课件

这是一份高中信息技术5.3 数据排序图文ppt课件，共17页。PPT课件主要包含了深化排序，抽象与建模，设计算法与数据结构，程序实现等内容，欢迎下载使用。
请写出冒泡排序的第一遍手动过程
冒泡排序的基本过程与规则
1. 排序的最少遍数为n-12. 每遍进行的基本过程。第一遍，对n个元素冒泡，加工完毕，最大值23“下沉”至数组最后第一个元素的位置；第二遍，对n-1个元素冒泡，加工完毕，最大值20“下沉”至数组最后第二个元素的位置；……第n-1遍，对2个元素冒泡，加工完毕，最大值13“下沉”至数组最后第n-1个元素的位置；3. 排序完成。
排序过程中，按下面的方式使用变量i和j:i：记录正进行的处理遍数，第1遍处理时值为1，第2遍处理时值为2，依次类推。j：记录当前数组元素的下标。每遍处理过程中，j值总是从第一个数组元素的下标值0开始，按每次加1的方式，直至j=n-i-1为止。每当j取定一个值后，当前数组元素d[j]将与它的后一个元素d[j+1]进行比较，若d[j] >d[j+1]，则互换这两个数组元素中的数据。
第一遍排序的程序实现fr j in range(0,length-1): if L[j]>L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp
def bubble_srt(L): length=len(L) #序列长度为length，需要执行length-1遍加工 fr i in range(1,length): fr j in range(0,length-i): if L[j]>L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp
小组讨论：迭代式如何来的？
冒泡排序算法的每一遍加工中，最小的元素“上浮”和最大的元素“下沉”这两种方式在程序实现时有何区别？
5.3.3 数据排序的应用
奥运排行榜部分数据（Excel数据）
问题：从表中的数据可以看出，每个国家的信息是一条记录，包括编号、国家/地区、人口数量、各奖牌数等数据项。根据刚才的实践体验，对记录按关键字排序，交换应当如何进行？
数据组织形式有两种，哪种更方便？
一是采用7个一维数组按列存储，即每个数组分别存储每个国家的编号、国家/地区、人口数量、各奖牌数等，如定义b数组存储表中8个国家的金牌数量，其对应的值为[51,1,36,1,3,0,23,9]；二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如[8,中国,136407,51,21,28,100]对应中国的相关信息。
小组讨论：排序的稳定性
一般情况下，数据规模较小，各种排序方法的时间耗费差异较小，选择面较大；当数据规模较大时，冒泡排序、选择排序的时间复杂度为O (n2)，一般不会选用，常用的有快速排序、归并排序、堆排序、希尔排序等，时间复杂度为O (n lg2 n)，pythn中使用的排序方法为TimSrt，它实质上是对归并排序的优化，目前认为是最优秀的排序方法。稳定性是指排序前后，相同的数据项前后关系会不会带来变化，冒泡排序是稳定的，快速排序是不稳定的；数据结构也对排序有很大影响，编程的复杂度不同，空间复杂度不同。一般情况下，降低了时间复杂度，就会带来较高的空间复杂度；降低了空间复杂度，会带来较高的时间复杂度。对较特殊的数据比如在一定范围内的整数，使用桶排序，时间复杂度达到O (n),但空间复杂度会提高，需要较多的辅助空间。