资源描述：
《数据结构课件CD 第10章 内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第10章 内部排序数据结构主讲教师：周时阳《数据结构》是计算机科学与技术类各专业的一门基础课。本章主要介绍数据结构课程研究的问题背景、研究内容和范围。讨论了数据结构和算法的基本概念以及算法的评价。关于线性结构、树型结构和图型结构等3类基本结构，将在后续各章陆续展开讨论它们的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。内容摘要2重点讲解10.1概论10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7内部排序方法的比较小结3目录10.1概论“排序”是基于数据逻辑结构(
2、D,R)定义的一种十分常见的运算。数学上，“排序”是指依据D中的每个数据元素之关键字，按照递增(或递减)顺序将数据元素排列的过程。即：假设D={a1,a2,…,ai,…,an}初始序列为(a1,a2,…,ai,…,an)其对应的关键字序列为(k1,k2,…,ki,…,kn)关键字的递增序列为(kp1,kp2,…,kpi,…,kpn)则(a1,a2,…,ai,…,an)排序结果为(ap1,ap2,…,api,…,apn)排序4如果排序算法，对于次关键字排序后，确保相同的次关键字与排序前的相对前后次序不变，则称该算法是稳定的，否则称该算法是不稳定的。即：
3、假设D的初始序列为(…,ai,…,aj,…)其对应的关键字序列为(…,ki,…,kj,…)且ki=kj，关键字的递增序列为(…,ki,kj,…)则D的排序结果为(…,ai,aj,…)相对次序不变！标识多个(>1)数据元素的分量，称为次关键字。5T=(D,R)ai:keyki……Sort(T)keyptki…“排序”运算的一般描述形式为：sort(T,fkey,up_dn)，即根据给定关键字分量，按照up_dn指定的不减序或不增序，对T进行排序。610.2.1直接插入排序10.2插入排序基本原理：在递增(递减)有序表L上，插入一个元素x，使其仍然保持有
4、序。L:(a1,a2,a3,…,ak,ak+1,…,an)L:(a1,a2,a3,…,ak,x,ak+1,…,an)ak≤x＜ak+1≤x≤≤x≤…≤x≤基本步骤：⑴确定插入位置；⑵移动元素；⑶填入新元素。基本步骤：⑴边确定插入位置，边移动元素；⑵填入新元素。x“哨兵技术”目录7算法思想：从表L=(a1,a2,a3,…,ai,…,an)的第2个元素a2开始，直到最后一个元素an为止，逐个插入本元素之左边的有序子表，使其仍然保持有序。()4938659776132749384938()65977613274965493865()659776132749
5、9749386597()761327499749386576977649()1327494938651397769776653813()274949277665973813977665493827()494997139776654938277665494938659776132749()1327384949657697()算法分析：(问题规模为参加排序的元素个数n)比较次数：Tb(n)=n-1移动次数：Tb()=0Tw(n)=∑iTw()=∑(i+1)Ta(n)=(Tb+Tw)/2≈n2/4i=2ni=2n最好情况：正序最差情况：反序算法时间复杂度T
6、(n)=O(n2)810.2.2其它插入排序⒈折半插入排序算法思想：“定位”除了上述顺序定位法外，还可以利用有序子表特点，采用折半定位法。当定位结束(即L>H)时，aL~ai-1向后移动。L:(a1,a2,a3,…,ak-1,ak,ak+1,…,ai-1)LHai≤＜ak≤xLx＜akH算法分析：比较次数：Tb(n)=n-1移动次数：不变Tw(n)=∑㏒i≈n㏒ni=1n-1算法时间复杂度T(n)=O(n2)9⒉2路插入排序(将关键字排序在辅助空间中)算法思想：⑴取出表L=(a1,a2,a3,…,ai,…,an)的第1个元素a1存入辅助空间D[1]；
7、⑵取出表L的下一个元素ai，如果ai＜D[1]，则插入到D[1]之左边的有序子表，否则插入到D[1]之右边的有序子表；⑶重复⑵，直到表L的最后一个元素an插入后为止。D[1]D[2]D[n]HT………算法分析：比较次数：不变移动次数：Tb(n)=0Tw(n)=不变Ta(n)=n2/8算法时间复杂度T(n)=O(n2)10⒊表插入排序(静态链表，ai内部结构增加一个静态指针)算法思想：从表L=(a1,a2,a3,…,ai,…,an)的第2个元素a2开始，直到最后一个元素an为止，逐个插入本元素之左边的有序子表，使其仍然保持有序。从小到大方向定位(即第一
8、次遇到大于ai的元素之前插入)，插入时仅修改指针。Max4938659776132749keynext012
