东南大学计算机学院方效林教学课件

《东南大学计算机学院方效林教学课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东南大学计算机学院方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第九章排序本章主要内容排序的概念插入排序顺序插入排序折半插入排序希尔排序快速排序选择排序归并排序分配排序内部排序算法分析2排序的概念定义将一组杂乱无章的数据按一定规律顺次排列数据表(dataList)待排序数据元素的有限集合排序码(key)通常数据元素有多个属性，作为排序依据的属性称为排序码学生成绩表，按学号小到大排序，按成绩高到低排序3排序的概念排序的稳定性两数据元素排序码相同，排序前后两元素先后顺序若相同，则是稳定的若不同，则不稳定内排序和外排序内排序所有元素都在存在内存的排序外排序数据太多，内存

2、放不下，而存放在外部存储器，排序时需要经常在内、外存之间读写数据41(a)2(b)2(c)3(d)1(a)2(c)2(b)3(d)2(c)1(a)3(d)2(b)初始排序1排序2稳定的不稳定排序的概念排序的时间开销内排序一般用数据比较次数和数据移动次数衡量外排序一般用外存的读写次数衡量(外存慢)排序的空间开销执行排序算法需要的存储空间5顺序插入排序顺序插入排序算法将待排序元素，从后向前寻找适当的插入位置，直到所有元素都插入为止621254925*1608初始21254925*1608第1步21254925*1608第2步21254925*1608第3步212525*491608第4步

3、16212525*4908第5步插入25，25≥21，无需移动插入49，49≥25，无需移动插入25*，25*<49，212525*491608插入16，16<49,25*,25,21，16212525*49080816212525*49插入08，08<49,25*,25,21,16，49后移，25*填入49,25*,25,21后移，16填入49,25*,25,21,16后移，08填入顺序插入排序算法分析最好情况(n个元素)原数据是按小到大顺序排好的每步只需与前一个数据比较一次，而不用移动数据总比较次数n-1，总移动次数0最坏情况(n个元素,i=0,1,…,n-1)原数据按大到小顺序

4、排好的元素i需要比较i次，每比较1次移动1次，元素i移动2次总比较次数和总移动次数temp=a[i]a[0]=temp比较和移动最坏最好平均值约为n2/4时间复杂度O(n2)顺序插入排序算法分析是稳定的算法，key相同元素原来的顺序不会打乱需要额外一个存储空间821254925*1608初始0816212525*49排序后temp=a[i]a[0]=temp折半插入排序折半插入排序算法将待排序元素，按折半搜索法寻找适当的插入位置，直到所有元素都插入为止91621232525*49low>high，49,25*,25后移，23填入16212525*4923012345lowmidhig

5、h16212525*4923012345lowmidhigh16212525*4923012345lowmidhighmid>23,high=mid-1,mid=(low+high)/2mid≤23,low=mid+1,mid=(low+high)/216212525*4923012345lowmidhighmid≤23,low=mid+1,mid=(low+high)/2折半插入排序算法分析平均情况下，折半搜索比顺序搜索快搜索元素i需比较log2i+1次总比较次数移动的时间复杂度O(n2)是稳定的排序算法，需额外一个存储空间10比较的时间复杂度O(n*log2n)希尔排序基本思

6、想设定不同gap值，距离gap的元素放一起插入排序1121254925*1608初始21254925*1608第1步21254925*160821254925*1608gap=n/3+1=321160825*2549结果21160825*2549gap=gap/3+1=221160825*254908162125*2549结果08162125*254908162125*2549gap=gap/3+1=1结果第2步第3步最后1步是n个元素进行插入排序是不是很慢？希尔排序算法分析设定不同gap值，距离gap的元素放一起插入排序gap值越来越小，由于前面的排序过程，使得大多数数

7、据已经基本有序，因此希尔排序速度仍然很快gap的取值方法有很多种gap=gap/3+1gap=gap/2……希尔排序复杂度分析很困难，还没有完整的数学分析统计得出，平均比较和移动次数在[n1.25,1.6n1.25]内是不稳定的排序算法12快速排序基本思想Partition：任取一元素x为基准(如选第1个)，小于x的元素放在x左边，大于等于x的元素放在x右边对左、右部分递归执行上一步骤直至只有一个元素1321254925*1608初始第1层第2层第