数据排序课件浙教版高中信息技术选修1

数据排序

选修一：数据结构排序排序排序的含义排序概念：将无序数据按照某种规则（递增或递减），重新排列使其变成有序数据。未排序数据的存储方式：①以数组作为存储结构

通过关键字之间的比较判断，将数据移到合适的位置②以链表作为存储结构

对链表进行排序无须移动数据，只需修改指针即可排序的含义列表的sort方法Python内置sorted函数常见排序算法排序算法冒泡排序选择排序插入排序快速排序堆排序归并排序桶排序冒泡排序冒泡排序冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。冒泡排序232013181411202313181411201323181411201318231411201318142311201318141123d[0]d[1]d[2]d[3]d[4]d[5]②①③④⑤第一遍加工冒泡排序201318141123132018141123131820141123131814201123131814112023d[0]d[1]d[2]d[3]d[4]d[5]②①③④第二遍加工初始值冒泡排序232013181411131411182023131114182023111314182023d[0]d[1]d[2]d[3]d[4]d[5]初始值2013181411231318141120231遍加工2遍加工3遍加工4遍加工5遍加工冒泡排序★升序：小数上冒（大数下沉）；★n个数最多进行

n-1

遍排序★两数比较的次数为:n*(n-1)/2★两数交换次数最多为：

n*(n-1)/2冒泡排序思想冒泡排序第n次加工内循环循环次数1524334251元素个数=加工次数+内循环次数对[23,20,13,18,14,11]冒泡排序加工次数与循环次数的关系该列表第i次加工时内循环会循环多少次？冒泡排序程序实现大数下沉defbubble_sort(d):length=len(d)foriinrange(1,length):forjinrange(0,length-i):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]returnda=[23,20,13,18,14,11]print(bubble_sort(a))加工遍数单次加工冒泡排序程序实现小数上冒defbubble_sort(d):

length=len(d)foriinrange(1,length):forjinrange(length-1,i-1,-1):ifd[j]<d[j-1]:

d[j],d[j-1]=d[j-1],d[j]returnda=[23,20,13,18,14,11]print(bubble_sort(a))加工遍数单次加工冒泡排序算法优化采用右侧冒泡排序算法对A进行排序，循环比较多少次？是否需要比较这么多次？如何修改程序，提高算法效率？defbubble_sort(d):

length=len(d)foriinrange(1,length):forjinrange(length-1,i-1,-1):ifd[j]<d[j-1]:

d[j],d[j-1]=d[j-1],d[j]returnda=[2,1,3,4,5]print(bubble_sort(a))冒泡排序算法优化defbubble_sort(d):

c=0

#用于统计每一次加工交换次数

length=len(d)foriinrange(1,length):forjinrange(length-1,i-1,-1):ifd[j]<d[j-1]:c+=1d[j],d[j-1]=d[j-1],d[j]

ifc==0:breakreturnd如果一次加工过程中没有发生数据交换说明数据已经有序。冒泡排序算法优化defbubble_sort(d):

flag=false

#用于判断一次加工是否有元素交换

length=len(d)foriinrange(1,length):forjinrange(length-1,i-1,-1):ifd[j]<d[j-1]:

flag=ture

d[j],d[j-1]=d[j-1],d[j]

ifflag==false:breakreturnd小试牛刀d=[173,172,169,178,183]s=0foriinrange(1,len(d)):c=0forjinrange(0,len(d)-i):s+=1ifd[j]>d[j+1]:c+=1d[j],d[j+1]=d[j+1],d[j]则程序运行之后，s的值为（）A.10B.8C.6D.5选择排序选择排序选择排序原理：①首先从待排序的数据元素中找到最小（大）的一个元素，存放在序列的起始位置。②再从剩余的未排序元素中寻找最小（大）的元素，然后放到未排序序列的起始位置。③重复②，直到所有元素均排序完毕。选择排序2

3451012002034512选择排序0

34510302113选择排序选择排序程序实现defselect_sort(d):length=len(d)foriinrange(1,length):k=i-1forjinrange(i,length):ifd[j]<d[k]:k=jifk!=i-1:d[i-1],d[k]=d[k],d[i-1]returnda=[52,36,68,79,27]n=len(a)

b,c=0,0foriinrange(n-1):k=iforjinrange(i+1,n):ifa[j]<a[k]:k=jb=b+1ifk!=i:a[i],a[k]=a[k],a[i]c=c+1print(b,c)该程序段执行后，b和c的值分别为（）A.53B.44C.43D.34Ca=[18,12,11,21,13]n=len(a)f=[False]*5#含有5个元素，且初始值为False的列表foriinrange(n):k=iforjinrange(n-1,i,-1):ifa[j]<a[k]:k=jifk!=i:a[k],a[i]=a[i],a[k]f[i]=Trueprint(f)执行该程序段，f中元素值为True的个数是___________。3插入排序插入排序①从第一个元素开始，该元素可以认为已经被排序；②取出下一个元素，在已经排序的元素序列中从后向前扫描；③如果该元素（已排序）大于新元素，将该元素移到下一位置；④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；⑤将新元素插入到该位置后；重复步骤②~⑤。插入排序832547012345ji下标382547012345ji下标382547012345ji下标第一遍加工插入排序832547012345ji下标第二遍加工832547012345ji下标插入排序第三遍加工832547012345ji下标832547012345ji下标853247012345ji下标插入排序插入排序程序实现definsert_sort(d):foriinrange(1,len(d)):k=d[i]forjinrange(i-1,-2,-1):ifd[j]<k:d[j+1]=d[j]else:breakd[j+1]=kreturnda=[2,4,1,3,9]print(insert_sort(a))从后向前比较快速排序快速排序快速排序算法：①确定基准：从数列中挑出一个元素，称为“基准”；②分区操作：比基准值小的数摆放在基准前面，比基准值大数的摆在基准的后面（相同的数可以到任一边）快速排序归并排序归并排序

归并排序算法是采用分治思想的一个典型的应用。

归并排序分两步：先分割，后合并。图解归并排序4038659776132749403865977613274940386597761327494038659776132749分图解归并排序1327384049657697384065971327497638406597137627494038659776132749治归并排序代码实现defmerge(arr,l,m,r):n1=m-l+1n2=r-m#创建临时数组L=[0]*(n1)R=[0]*(n2)#拷贝数据到临时数组L[]和R[]foriinrange(0,n1):L[i]=arr[l+i]forjinrange(0,n2):R[j]=arr[m+1+j]#归并临时数组到arr[l..r]i=0#第一个子数组的索引j=0#第二个子数组的索引k=l#归并子数组的索引whilei<n1andj<n2:ifL[i]<=R[j]:arr[k]=L[i]i+=1else:arr[k]=R[j]j+=1k+=1whilei<n1:arr[k]=L[i]i+=1k+=1whilej<n2:arr[k]=R[j]j+=1k+=1defmergeSort(arr,l,r):ifl<r:m=(l+r)//2mergeSort(arr,l,m)mergeSort(arr,m+1,r)merge(arr,l,m,r)a=[40,38,65,97,76,13,27,49]print("原列表为：")print(a)mergeSort(a,0,len(a)-1)print("归并排序后的列表（升序）为：")print(a)桶排序桶排序

桶排序算法过程：①将数组分到有限数量的桶里②对每个桶内元素进行排序③依次把各个桶中的记录输出桶排序(无限桶)对列表a=[3,8,2,5,4,7]的元素进行排序。①列表a中最大元素的值为8，则我们设置9个桶。桶的编号为别为0~8。

②把列表a中元素放入到对应编号的桶内。

③按桶的编号，依次输出桶内元素。桶排序a=[3,8,2,5,4,7]print("原列表为：")print(a)tong=[0]*9p=[]foriinrange(len(a)):tong[a[i]]+=1foriinrange(len(tong)):iftong[i]>0:p.append(i)print("桶排序后的列表（升序）为：")print(p)输出结果：原列表为：[3,8,2,5,4,7]桶排序后的列表（升序）为：[2,3,4,5,7,8]难点：桶列表的建立桶的索引是对应与列表a内的元素值桶列表存放的元素值是0或