文档介绍：第四讲排序算法Jsoi第一轮函授B班第4讲讲义第一节排序及其基本概念一、。设文件由n个记录{R,R,„„,R}组成,n个记录对应的关键字集合为{K,K,„„,12n12K}。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。,排序结果是惟一的,否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序之后,仍能保持它们在排序之前的相对次序,则称这种排序方法是稳定的;否则,称这种排序方法是。,可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序,称为内部排序;反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。内排序适用于记录个数不是很多的小文件,而外排序则适用于记录个数太多,不能一次性放人内存的大文件。内排序是排序的基础,本讲主要介绍各种内部排序的方法。按策略划分内部排序方法可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。二、:(1)关键字大小的比较。(2)改变记录的位置。具体处理方式依赖于记录的存储形式,对于顺序型记录,一般移动记录本身,而链式存储的记录则通过改变指向记录的指针实现重定位。为了简化描述,在下面的讲解中,我们只考虑记录的关键字,则其存储结构也简化为数组或链表。并约定排序结果为递增。,不同的算法有不同的优缺点,没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条:(1)执行时间和所需的辅助空间,即时间复杂度和空间复杂度;(2)算法本身的复杂程度,比如算法是否易读、是否易于实现。第二节插入排序插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的记录集中,使记录依然有序,直到所有待排序记录全部插入完成。一、[1..n]中,则A[1]可看作是一个有序序列,让i从2开始,依次1Jsoi第一轮函授B班第4讲讲义将A[i]插入到有序序列A[1..i-1]中,A[n]插入完毕则整个过程结束,A[1..n]成为有序序列。(用【】表示有序序列)待排序数据:【25】548542119727315(n=10)i=2:【2554】8542119727315i=3:【82554】542119727315i=4:【8255454】2119727315i=5:【821255454】19727315i=6:【1821255454】9727315i=7:【182125545497】27315i=8:【1282125545497】7315i=9:【1282**********】15i=10:【128152**********】[0]作为关键值存储器和循环控制开关。第i趟排序,即A[i]的插入过程为:?保存A[i]?A[0]?j,i,1?如果A[j]<=A[0](即待排序的A[i]),则A[0]?A[j+1],完成插入;否则,将A[j]后移一个位置:A[j]?A[j+1];j,j,1;继续执行?对于上面的数据实例,i从2依次变化到10的过程中,j值分别为{1,0,3,1,0,6,1,7,3}(n:integer);vari,j:integer;beginfori:=2tondobegina[0]:=a[i];j:=i-1;whilea[j]>a[0]do{决定运算次数和移动次数}begina[j+1]:=a[j];j:=j-1;end;a[j+1]:=a[0];end;end;(1)稳定性:稳定2Jsoi第一轮函授B班第4讲讲义(2)时间复杂度:?原始数据正序,总比较次数:n-1n2n,n,22?原始数据逆序,总比较次数:i,,O(n),i22,i2i,n,3n12?原始数据无序,第i趟平均比较次数=ji,,O(n),总次数为:/,j42,1?可见,原始数据越趋向正序,比较次数和移动次数越少。(3)空间复杂度:仅需一个单元A[O]二、:任取一个小于n的整数S作为增量,把所有元素分成S个组。所有间距为S的元素放在同111一个组中。第一组:{A[1],A[S+1],A[2*S+1],„„}11第二组:{A[2],A[S+2],A[2*S+2],„„}11第三组:{A[3],A[S+3],A[2*S+3],„„}11„„第s组:{A[S],A[2*S],A[3*S],„„}1111先在各组内进行直