第7单元排序主讲刘志强

《第7单元排序主讲刘志强》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7单元排序主讲：刘志强西安交通大学计算机教学实验中心计算机软件基础FundamentalsofComputersoftware思考问题“二分查找”很快，但要求数列有序。怎样使数列有序？显示生活中的有序方法有哪些？能否应用到数列的有序化操作中？基本的有序化操作方式有几种？……2教学目标了解有关排序的基本概念排序的典型算法3教学要求通过本单元的学习，了解、掌握有关排序的：基本概念排序、排序分类、算法稳定性典型的排序算法插入排序、选择排序、交换排序快速排序、归并排序4一、基本概念排序排序分类算法稳定性5排序(Sorting)

2、就是将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系:Kp1Kp2...Kpn或Kp1Kp2….Kpn6排序分类根据排序元素所在位置的不同,排序分:内排序和外排序。内排序在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。外排序在数据量大的情况下，只能分块排序，

3、但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。7内排序方法分类内排序方法有许多种：按排序过程中依据的不同原则分类：插入、交换、选择、归并和基数排序等；按排序过程中所需工作量来区分：简单排序（O（n2））快速排序（O（nlogn））基数排序（O（d*n））排序过程中所需进行的操作：比较两个关键字的大小移动记录的位置28若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。排序算法的稳定性9顺序存储

4、结构（C语言描述）：#defineNnstructrecord{intkey；/*关键字项*/intotherterm；/*其它项*/}；typedefstructrecordRECORD；RECORDfile[N+1]；排序算法的数据结构10二、典型排序算法插入排序选择排序交换排序快速排序归并排序11⑴插入排序（算法3-5）基本思想：将n个元素的数列分为已有序和无序两个部分。{{a1}，{a2，a3，a4，…,an}}{{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}}…...{{a1(n-1)，a

5、2(n-1)，…},{an(n-1)}}每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。有序无序12插入排序算法步骤Step1从有序数列{a1}和无序数列{a2,a3,…,an}开始进行排序;Step2处理第i个元素时(i=2,3,…,n),数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1、ai-2,…,a1进行比较,找出合适的位置将ai插入。Step3重复Step2，共进行n-1的插入处理，

6、数列全部有序。13插入排序举例设有数列{18，12，10，12，30，16}初始状态：{18}，{12，10，12，30，16}比较次数i=1{18}，{12，10，12，30，16}1i=2{12，18}，{10，12，30，16}2i=3{10，12，18}，{12，30，16}2i=4{10，12，12，18}，{30，16}1i=5{10，12，12，18，30}，{16}3{10，12，12，16，18，30}总计：9次14插入排序算法insert_sort(item,n)int*item,n;{inti，j，

7、t;for（i=1；i=0&&t

8、rintf(“%3d”,a[i]);printf(“”);insert_sort(a,6);/*调用插入排序函数*/printf(“Aftersorting”);for(i=0;i<6;i++)printf(“%3d”,a[i]);printf(“”);}示例16算法讨论插入算法比较次数和交换次数约为n2