第7章 排序优秀课件.ppt

第7章 排序第1页，本讲稿共115页第七章第七章 排序排序7.4 7.4 7.4 7.4 归并排序归并排序归并排序归并排序 一一.归并排序的概念归并排序的概念 二二.相邻有序子表的归并相邻有序子表的归并 三三.二路归并排序的实现二路归并排序的实现7.5 7.5 7.5 7.5 分配排序分配排序分配排序分配排序 一一.多关键字排序多关键字排序 二二.基数排序基数排序7.6 7.6 7.6 7.6 内排序方法比较内排序方法比较内排序方法比较内排序方法比较 一一.几种内部排序方法的性能几种内部排序方法的性能 二二.比较分析比较分析 三三.方法选择方法选择第2页，本讲稿共115页第七章第七章 排序排序7.7 7.7 7.7 7.7 拓扑分类的实现拓扑分类的实现拓扑分类的实现拓扑分类的实现 一一.基本思路基本思路 二二.实现步骤实现步骤 三三.算法描述算法描述7.8 7.8 外排序简介外排序简介外排序简介外排序简介 一一.外排序的基本步骤外排序的基本步骤 二二.外排序的时间开销外排序的时间开销 三三.败者树与最佳归并树败者树与最佳归并树第3页，本讲稿共115页第七章第七章第七章第七章 排排排排 序序序序 排序排序排序排序(sorting)(sorting)用某种方法，把元素的无序序列调整为按某用某种方法，把元素的无序序列调整为按某 数据项有序排列的过程；数据项有序排列的过程；数据表数据表数据表数据表 待排序的数据元素的有限集；待排序的数据元素的有限集；有序表有序表有序表有序表 排序后的表；排序后的表；无序表无序表无序表无序表 排序前的表；排序前的表；主关键字主关键字主关键字主关键字 可以唯一标识数据表中各元素的数据项；可以唯一标识数据表中各元素的数据项；排序项排序项排序项排序项 用于排序的数据项；用于排序的数据项；排序码排序码排序码排序码 排序项的值；排序项的值；正序正序正序正序 关键字关键字ki、kj在表中的位置关系符合排序要求；在表中的位置关系符合排序要求；逆序逆序逆序逆序 关键字关键字ki、kj在表中的位置关系不符合排序要求；在表中的位置关系不符合排序要求；第4页，本讲稿共115页第七章第七章第七章第七章 排排排排 序序序序 排序结果唯一性：排序结果唯一性：排序结果唯一性：排序结果唯一性：若以主关键字为排序项，排序结果唯一若以主关键字为排序项，排序结果唯一 ；否则排序结果不唯一；否则排序结果不唯一；排序方法的稳定性：排序方法的稳定性：排序方法的稳定性：排序方法的稳定性：如果有排序码如果有排序码Ki=Kj，排序前排序前Ki领先于领先于Kj (ilen-1;/f lag 记录一趟比较中最后一次发生交换的位置记录一趟比较中最后一次发生交换的位置 while(f lag0)j=flag-1;flag=0；/j 记下要比较的最后位置，重置记下要比较的最后位置，重置f lag初值初值 for(i=0;ireci.key L-reci+1.key)temp=L-reci；L-reci=L-reci+1；L-reci+1=temp；flag=i；第10页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 注意：注意：注意：注意：算法中，算法中，f lag 既是一趟扫描有无交换发生的标记，既是一趟扫描有无交换发生的标记，又是最后一次发生交换的位置记录；又是最后一次发生交换的位置记录；3.3.算法分析：算法分析：算法分析：算法分析：时间复杂度：时间复杂度：时间复杂度：时间复杂度：最坏情况，对无序表扫描最坏情况，对无序表扫描 n-1趟，每次下沉一个趟，每次下沉一个 元素；共进行元素；共进行 n(n-1)/2 次比较，复杂度为次比较，复杂度为O(n2)空间复杂度：空间复杂度：空间复杂度：空间复杂度：in place 动态性能：动态性能：动态性能：动态性能：稳定稳定(在消除逆序过程中没有产生新的逆序在消除逆序过程中没有产生新的逆序)；思考：思考：思考：思考：该算法扫描过程中，该算法扫描过程中，该算法扫描过程中，该算法扫描过程中，“大者大者大者大者”下沉速度大于下沉速度大于下沉速度大于下沉速度大于“小者小者小者小者”上浮上浮上浮上浮速度速度速度速度 ；若能加速若能加速若能加速若能加速“上浮上浮上浮上浮”速度，则可提高效率。如何改进？速度，则可提高效率。如何改进？速度，则可提高效率。如何改进？速度，则可提高效率。如何改进？第11页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 二二二二.快速排序快速排序快速排序快速排序 快速排序快速排序(Quick Sort)冒泡排序的改进冒泡排序的改进 基本思想：基本思想：基本思想：基本思想：分治法分治法分治法分治法 大的待排序表大的待排序表大的待排序表大的待排序表 小的待排序表小的待排序表小的待排序表小的待排序表 更小的待排序表更小的待排序表更小的待排序表更小的待排序表 2 2个个个个(或或1 1个个)元素排序。元素排序。元素排序。元素排序。实现方法：实现方法：实现方法：实现方法：通过一趟排序把待排序表分成前后两部分，使通过一趟排序把待排序表分成前后两部分，使 前一部分元素的排序码前一部分元素的排序码 后一部分元素的排序码后一部分元素的排序码 ；再对每部分元素以同样方法进行排序，直到全表元素再对每部分元素以同样方法进行排序，直到全表元素 按排序码有序；按排序码有序；关键：关键：关键：关键：如何把待排序表分为符合上述要求的两部分如何把待排序表分为符合上述要求的两部分 线性表分割；线性表分割；第12页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 1.1.线性表分割线性表分割线性表分割线性表分割 设待排序记录为设待排序记录为R0,Rn-1。一趟一趟(非递减非递减)排序的分割过程为：排序的分割过程为：设置指针设置指针i、j分别指向待排序表的第一个和最后一个元素；分别指向待排序表的第一个和最后一个元素；选取一个元素选取一个元素Rk，做：做：Rk T，Ri Rk；逐渐减小逐渐减小j，同时依次比较同时依次比较 Rj.key与与 T.key，直到直到 Rj.key T.key时，把时，把 Ri移到移到 Rj的位置上，的位置上，即：即：Ri Rj；反复做反复做、，直到直到 i=j为止，此时令为止，此时令 Ri=T。第13页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 T(T=Rk)ij.TiijjR1，R0，Rn-2，Rn-1jiR0，R1，Rn-2，Rn-1jiR0，R1，Rk，Rn-2，Rn-1第14页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 例，分割无序表例，分割无序表(65 38 49 97 76 13 27 44)，取取 Rk=49 T65389776132744386597761327444438659776132744389776132765443827977613654438277613976544382713769765443827134949769765iiiiiiiijjjjjjjj第15页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 线性分割算法线性分割算法线性分割算法线性分割算法:int Partition(RecType R,int low,int high)/对记录子序列对记录子序列 R low,high 进行分割，返回分割点位置进行分割，返回分割点位置 选取表中元素选取表中元素Rk,k low,high int i,j;RecType T;T=Rk；Rk=Rlow；/low 位置空位置空 i=low;j=high；/i、j分别指向待排序表的头、尾元素分别指向待排序表的头、尾元素 while(i!=j)/i、j 相遇时本趟分割完成相遇时本趟分割完成 /j 向前移动，直到向前移动，直到j 所指示的关键字值所指示的关键字值=T.key&i j)j-；第16页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 if(i j)/j 指示的关键字指示的关键字 T的关键字的关键字 while(Ri.key=T.key&i j)i+；if(i T的关键字的关键字 Rj=Ri；j-；/i 指示的元素交换到指示的元素交换到 j 的位置的位置 Ri=T；/T 放入分割点放入分割点 i 的位置的位置 return i ；/返回本趟的分割点返回本趟的分割点 i 第17页，本讲稿共115页m n7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 2.2.快速排序算法快速排序算法快速排序算法快速排序算法 从快速排序的步骤可以看出，快速排序的过程即是从快速排序的步骤可以看出，快速排序的过程即是 对无序表逐层分割的过程，可以递归实现；对无序表逐层分割的过程，可以递归实现；如图：如图：i-1 i i+1m i n递归过程的边界递归过程的边界递归过程的边界递归过程的边界排序的最小子表排序的最小子表表中多于一个元素表中多于一个元素 即：表起始位置即：表起始位置 m)/表长不小于表长不小于 2 i=partition(L-rec,m,n)；/分割表分割表 L中元素中元素 Qksort(L,m,i-1)；/对前半部分做快速排序对前半部分做快速排序 Qksort(L,i+1,n)；/对后半部分做快速排序对后半部分做快速排序 第19页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 3.3.算法分析算法分析算法分析算法分析 关于关于Rk的选取的选取 Rk直接关系到排序的时间效率：直接关系到排序的时间效率：若若Rk.key为表中最小或最大关键字项，效率最低为表中最小或最大关键字项，效率最低 (每一趟排序只确定一个元素的位置每一趟排序只确定一个元素的位置)；复杂度：复杂度：O(n2)若若Rk平分线性表，效率最高；平分线性表，效率最高；复杂度：复杂度：O(n log2n)实用中采取：实用中采取：选取选取Rm、R 、Rn关键字值的中项位置为关键字值的中项位置为 k；在在m、n之间产生随机数之间产生随机数k(每个子表每个子表k不同不同)；空间复杂度：空间复杂度：空间复杂度：空间复杂度：平均平均 O(log2n)，最坏情况最坏情况O(n)：时间复杂度：时间复杂度：时间复杂度：时间复杂度：平均平均 O(n log2n)，最坏情况：最坏情况：O(n2)动态性能：动态性能：不稳定不稳定不稳定不稳定m+n2适用于大表的排序适用于大表的排序适用于大表的排序适用于大表的排序第20页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序4.4.4.4.快速排序的非递归算法快速排序的非递归算法快速排序的非递归算法快速排序的非递归算法思路：思路：思路：思路：设置一个栈设置一个栈S，在逐层分割过程中，总是对前一在逐层分割过程中，总是对前一(或后一个或后一个)子表子表进行再分割，同时把暂不分割的另一子表起始位置和终止位置压进行再分割，同时把暂不分割的另一子表起始位置和终止位置压栈保存；当前一栈保存；当前一(或后一个或后一个)子表分割完成时，从栈顶弹出另一子子表分割完成时，从栈顶弹出另一子表进行同样分割，以此类推，至栈空，排序完成。表进行同样分割，以此类推，至栈空，排序完成。若待排序记录序列为若待排序记录序列为Rk,m；设第一层分割点位置为设第一层分割点位置为i，第二层分割点位置为第二层分割点位置为 i，则栈则栈S中内容为：中内容为：i-1 i+1k i m i+1mi+1mk i m第21页，本讲稿共115页7.1 7.1 7.1 7.1 交换排序交换排序交换排序交换排序 算法描述：算法描述：算法描述：算法描述：QkSort1(SqList*L,int m,int n)int i,j,k;SqStack S；InitStack(S,20)；/栈栈S中整型元素有两个分量中整型元素有两个分量 Push(S,m,n)；/表元素起始位置表元素起始位置 m 和终点位置和终点位置n 压栈压栈 while(!EmptyStack(s)/栈不空重复做分割栈不空重复做分割 Pop(S,k,j)；/弹出待分割子表起始点到弹出待分割子表起始点到 k，终点到终点到 j while(krec,k,j)；/分割子表分割子表L.reckL.recj Push(S,i+1,j)；/被分割子表的后半部分压栈被分割子表的后半部分压栈 j=i-1；/准备对子表前半部继续做分割准备对子表前半部继续做分割 第22页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 一一一一.直接插入排序直接插入排序直接插入排序直接插入排序(straight insertion sort)简单排序方法简单排序方法简单排序方法简单排序方法 基本思想：基本思想：基本思想：基本思想：将无序表中的元素逐个插入到已经有序的表中；将无序表中的元素逐个插入到已经有序的表中；问题：问题：问题：问题：初始的有序表从何而来？初始的有序表从何而来？解决：解决：解决：解决：无序表中的第一个元素，作为初始有序表中的元素；无序表中的第一个元素，作为初始有序表中的元素；1.1.实现过程实现过程实现过程实现过程 把全表看成两部分把全表看成两部分(两个子表两个子表)，前部为有序前部为有序(有序子表有序子表)，后部为无序的待排序子表；后部为无序的待排序子表；从有序子表最后一个元素开始，由后向前，将无序子表第一从有序子表最后一个元素开始，由后向前，将无序子表第一 个元素个元素Rj依次与有序子表的元素依次与有序子表的元素进行比较，若有序子表元素进行比较，若有序子表元素 的关键字的关键字Rj的关键字，将该元素向后移动一个位置；直到的关键字，将该元素向后移动一个位置；直到 找到找到Rj的位置，将的位置，将Rj插入到有序子表；插入到有序子表；全表所有元素插入完，排序完成；全表所有元素插入完，排序完成；第23页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 例：对无序表例：对无序表(49 38 65 97 76 13 27 44)做直接插入排序，过程如下：做直接插入排序，过程如下：(4949)(38659776132744)起始状态起始状态 排序完成排序完成 (13 27(13 27 38 38 44 44 49 65 76 97)49 65 76 97)(13 (13 2727 38 38 49 65 76 49 65 76 97)97)(44)(13 13 38 49 38 49 65 76 97)65 76 97)(27 44)(38 49 65(38 49 65 76 76 97)97)(13 27 44)(38 49(38 49 65 65 9797)(76 13 27 44)(38 49(38 49 6565)(97 76 13 27 44)(38 38 49)49)(65 97 76 13 27 44)第24页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 2.2.算法描述算法描述算法描述算法描述 void InsertSort(SqList*L)int i,j;RecType T;for(j=1;jlen;j+)/需要做需要做 len-1 次插入次插入 T=L-recj；/暂存无序子表的第一个元素暂存无序子表的第一个元素(待插入元素待插入元素)i=j-1；/i 指向有序子表的最后位置指向有序子表的最后位置 while(i=0&L-reci-key T.key)/查找待插入元素位置查找待插入元素位置 L-reci+1=L-reci；i-；L-reci+1=T；/把待插入元素插入到有序表中把待插入元素插入到有序表中 第25页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 3.3.算法分析算法分析算法分析算法分析 算法特点：算法特点：算法特点：算法特点：查找插入位置与有序子表中元素的移动同时做；查找插入位置与有序子表中元素的移动同时做；时间复杂度：时间复杂度：时间复杂度：时间复杂度：最好情况：最好情况：n-1次比较次比较,2(n-1)次移动，次移动，O(n)最坏情况：最坏情况：次比较次比较,次移动次移动 平均情况：平均情况：次比较次比较,次移动次移动 空间复杂度：空间复杂度：空间复杂度：空间复杂度：in place 动态性能：动态性能：动态性能：动态性能：稳定稳定 适合：适合：适合：适合：表不大表不大(n小小)；表基本有序表基本有序(逆序个数少，每个逆序之间距离短逆序个数少，每个逆序之间距离短)；n(n-1)2n2+n-24n2+7n-84n2+3n-42O(n2)思考：思考：思考：思考：链表的线性插入排序算法链表的线性插入排序算法链表的线性插入排序算法链表的线性插入排序算法？第26页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 二二二二.对分插入排序对分插入排序对分插入排序对分插入排序 直接插入排序的基本操作直接插入排序的基本操作 在有序子表中查找待排序元素在有序子表中查找待排序元素 的插入位置并移动元素；的插入位置并移动元素；有序子表中查找位置时采用对分查找方法有序子表中查找位置时采用对分查找方法 对分插入排序；对分插入排序；1.1.对分插入排序思想对分插入排序思想对分插入排序思想对分插入排序思想 采用对分查找方法找出待排序元素在有序子表中的插入位采用对分查找方法找出待排序元素在有序子表中的插入位 置，并将其插入到有序子表中；置，并将其插入到有序子表中；第27页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序2.2.对分插入排序步骤对分插入排序步骤对分插入排序步骤对分插入排序步骤 以待排序记录序列以待排序记录序列 R0,Rn-1 中的中的 R0为初始有序子表；为初始有序子表；把把 R1 Rn-1 逐个插入到有序子表中：逐个插入到有序子表中：设设 Rj 为待插入元素，为待插入元素，R0 Rj-1为有序子表；为有序子表；设指针设指针 low 和和 high 分别指向对分查找子表的起始与分别指向对分查找子表的起始与终止位置；终止位置；做做Rj T；对分查找对分查找 Rj 在有序子表中的位置，在有序子表中的位置，把把 Rj-1 Rhigh+1依次后移一个位置；依次后移一个位置；把把 Rj 插入到插入到 Rhigh+1 的位置；的位置；high+1 j-1 j 无序子表无序子表有序子表有序子表有序子表有序子表第28页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 3.3.对分插入排序算法对分插入排序算法对分插入排序算法对分插入排序算法 void BInSort(SqList*L)int i,j,mid,low,high;RecType T;for(j=1;jlen;j+)/做做 len-1 次插入次插入 T=L-recj；/暂存待插入元素暂存待插入元素 low=0;high=j-1；/设设low、high为有序子表的头、尾指针为有序子表的头、尾指针 while(lowrecmid.keyT.key)high=mid-1；else low=mid+1；for(i=j-1；ireci+1=L.reci；L-rechigh+1=T；/待插入元素进有序子表待插入元素进有序子表 第29页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 4.4.算法分析算法分析算法分析算法分析空间复杂度：空间复杂度：空间复杂度：空间复杂度：in place 时间复杂度：时间复杂度：时间复杂度：时间复杂度：比较次数减少，最坏情况：比较次数减少，最坏情况：O(nlog2n)移动次数未减少，最坏情况：移动次数未减少，最坏情况：O(n2)计为：计为：O(n2)动态性能：动态性能：动态性能：动态性能：稳定稳定 进一步改进的目标：进一步改进的目标：进一步改进的目标：进一步改进的目标：减少排序过程中元素移动的次数减少排序过程中元素移动的次数 措措措措 施：施：施：施：另设辅助空间，分两个方向做插入另设辅助空间，分两个方向做插入 2-路插入排序路插入排序第30页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序三、希尔排序三、希尔排序三、希尔排序三、希尔排序 希尔排序希尔排序希尔排序希尔排序（Shells sort）也称缩小增量排序也称缩小增量排序插入排序类插入排序类 基于对直接插入排序的分析：基于对直接插入排序的分析：n 较小时效率较高；较小时效率较高；待排序表中元素待排序表中元素“基本有序基本有序”时，效率提高很多；时，效率提高很多；希尔排序以此为依据进行插入排序的改进；希尔排序以此为依据进行插入排序的改进；1.1.基本思想基本思想基本思想基本思想 分治法分治法分治法分治法 将待排序表划分为若干个子表，对各个子表做直接插入排序；将待排序表划分为若干个子表，对各个子表做直接插入排序；连续进行这个过程，当全表连续进行这个过程，当全表“基本有序基本有序”时时,对全表做插入排序对全表做插入排序；基本操作：基本操作：基本操作：基本操作：划分子表划分子表 对各子表做直接插入排序对各子表做直接插入排序第31页，本讲稿共115页 例，表元素例，表元素（5 16 23 11 28 7 80 14 39 55 3 26 5 16 23 11 28 7 80 14 39 55 3 26）若用简单的逐段划分，将其划分为四个子表：若用简单的逐段划分，将其划分为四个子表：5 16 23 11 28 7 80 14 39 55 3 265 16 23 11 28 7 80 14 39 55 3 26 7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 2.2.子表的划分子表的划分子表的划分子表的划分 子表划分的方案对希尔排序的效率有着至关重要的影响：子表划分的方案对希尔排序的效率有着至关重要的影响：不同的划分方案直接影响排序过程中全表趋于不同的划分方案直接影响排序过程中全表趋于“基本有序基本有序”的速度和程度；的速度和程度；表的有序程度直接影响插入排序的效率；表的有序程度直接影响插入排序的效率；对各个子表分别做直接插入排序后，表中元素状态：对各个子表分别做直接插入排序后，表中元素状态：5 16 23 7 11 28 14 39 80 3 26 555 16 23 7 11 28 14 39 80 3 26 55问题：问题：问题：问题：不能消除远距离排序码间的逆序，不能使全表不能消除远距离排序码间的逆序，不能使全表“基本有序基本有序基本有序基本有序”；第32页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序子表划分方法：子表划分方法：将相隔增量将相隔增量 h 的元素构成一个子表，对各子表做直接插入排序，的元素构成一个子表，对各子表做直接插入排序，再减小增量再减小增量 h重新划分子表重新划分子表.，子表划分过程直到，子表划分过程直到 h=1为止。为止。例，无序表例，无序表：0 0 1 12 23 34 45 56 67 78 89 91010 1111 (5(516162323111128287 780801414393955553 32626)全表排序后：全表排序后：3 5 7 11 14 16 23 26 28 29 55 80 3 5 7 11 14 16 23 26 28 29 55 80 h=1h=1各子表排序后：各子表排序后：5 3 7 11 14 23 55 16 26 80 28 39h=3h=3 各子表排序后各子表排序后：5 14 23 11 3 7 80 16 39 55 28 26h=6h=6第33页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 3.3.算法描述算法描述算法描述算法描述 void Shellsort(SqList*L,int t,int d)/t 排序趟数排序趟数，d 每趟间隔每趟间隔 RecType T；int i,j,k,h；for(k=t；k=1；k-)/做做 t 趟排序，最后一趟趟排序，最后一趟 h=1 h=dk；/取本趟排序的间隔取本趟排序的间隔 for(j=h；jlen；j+)/对各子表做插入排序对各子表做插入排序 T=L-recj；i=j-h；while(i=0&L-reci.keyT.key)/查找待插入元素的位置查找待插入元素的位置 L-reci+h=L-reci；i=i-h；L-reci+h=T；/待插入元素进入有序子表待插入元素进入有序子表 第34页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 算法中的基本操作：算法中的基本操作：算法中的基本操作：算法中的基本操作：产生划分子表的增量序列：产生划分子表的增量序列：dtdt-1d2d1=1,t 为排序为排序“趟数趟数”；按照本趟排序给定的按照本趟排序给定的 di(i=t,t-1,1)划分子表；划分子表；对各子表做直接插入排序；对各子表做直接插入排序；算法中：算法中：算法中：算法中：外循环控制对全表做外循环控制对全表做 t“趟趟”排序；排序；内循环控制在给定的内循环控制在给定的 di下，对每个子表做插入排序；下，对每个子表做插入排序；注意：注意：注意：注意：算法中对各个子表的直接插入排序不是一次内循环算法中对各个子表的直接插入排序不是一次内循环(for)完成，而是一次内循环中完成各子表的一项的插入完成，而是一次内循环中完成各子表的一项的插入排序；排序；第35页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 0 0 1 12 23 34 45 56 67 78 89 910101111 无序表：无序表：(5(516162323111128287 780801414393955553 32626)h=6 h=6划分子表：划分子表：划分子表：划分子表：516231128780143955326 各子表排序后各子表排序后：514231137801639552826 h=3 h=3划分子表：划分子表：划分子表：划分子表：各子表排序后各子表排序后：537111423551626802839 h=1 h=1划分子表：划分子表：划分子表：划分子表：全表排序后全表排序后：3 35 57 7111114141616232326262828292955558080第36页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 4.4.算法分析算法分析算法分析算法分析 时间复杂度时间复杂度时间复杂度时间复杂度 开始增量开始增量h 较大，子表个数多，每个子表小，元素移动次数少，较大，子表个数多，每个子表小，元素移动次数少，一次移动消除的逆序多；每完成一趟排序，子表数目减少，子表一次移动消除的逆序多；每完成一趟排序，子表数目减少，子表内元素虽增加，但各项之间更趋于有序，元素移动次数也较少；内元素虽增加，但各项之间更趋于有序，元素移动次数也较少；结论：结论：结论：结论：比直接插入排序效率高，且比直接插入排序效率高，且n 越大越明显越大越明显；关于增量序列的取法关于增量序列的取法关于增量序列的取法关于增量序列的取法 排序时间是所取增量序列的函数排序时间是所取增量序列的函数理论上分析存在困难；理论上分析存在困难；增量增量 h变化太快变化太快(排序趟数少排序趟数少)，h=1之前未能使全表之前未能使全表 “基本有序基本有序”，影响影响排序效率；排序效率；增量增量h变化太慢，则会使排序趟数过多，影响排序效率；变化太慢，则会使排序趟数过多，影响排序效率；第37页，本讲稿共115页7.2 7.2 7.2 7.2 插入排序插入排序插入排序插入排序 在工程应用中，采用已有的一些研究结论：在工程应用中，采用已有的一些研究结论：例如：设排序的趟数为例如：设排序的趟数为t，则可取则可取：在此情况下，在此情况下，时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(n1.5)。也可取其他也可取其他 h系列，例如：取系列，例如：取 或取或取 当当n 较大时，其效率远好于直接插入排序较大时，其效率远好于直接插入排序；空间复杂度：空间复杂度：空间复杂度：空间复杂度：in place 动态性能：动态性能：动态性能：动态性能：不稳定不稳定第38页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序基本思想：基本思想：基本思想：基本思想：把待排序表看成有序与无序两部分把待排序表看成有序与无序两部分(子表子表)，初始，初始，全表为无序表；扫描无序表，每一趟扫描选出无序表的最小全表为无序表；扫描无序表，每一趟扫描选出无序表的最小 项并将其交换到有序子表的最后位置上，最后使全表有序。项并将其交换到有序子表的最后位置上，最后使全表有序。蛮力法蛮力法一一一一.简单选择排序简单选择排序简单选择排序简单选择排序 简单选择排序简单选择排序(Simple Selection Sort)简单排序方法简单排序方法简单排序方法简单排序方法1.1.实现步骤：实现步骤：实现步骤：实现步骤：扫描无序子表扫描无序子表(初始为全表初始为全表)找出其中最小项在表中的位置；找出其中最小项在表中的位置；将选出的元素交换到将选出的元素交换到 有序子表的最后位置上；有序子表的最后位置上；对无序子表中的元素逐个做对无序子表中的元素逐个做 、，直到无序子表为空；直到无序子表为空；第39页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序 例，对无序表例，对无序表(49 38 65 97 76 13 27 4449 38 65 97 76 13 27 44)做简单选择排序做简单选择排序 过程如下：过程如下：(49 38 65 97 76 1327 44)(13 27 38 44(13 27 38 44 49 65 76 49 65 76 97)97)(13 27 38 44(13 27 38 44 49 65)49 65)(76 97)(13 27 38 44(13 27 38 44 49)49)(76 65 97)(13 27 38 44)(13 27 38 44)(76 49 65 97)(13 27 38)(13 27 38)(97 76 49 65 44)(13 27)(13 27)(65 97 76 49 38 44)(13)(13)(38 65 97 76 49 27 44)初始：初始：初始：初始：第40页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序2.2.算法描述算法描述算法描述算法描述 void SslectSort(SqList*L)RecType T；int i,j,k;for(i=0；i len-1；i+)/需作需作 n-1 次选次选 k=i；/k 记录本次选择的最小关键字项的位置记录本次选择的最小关键字项的位置 for(j=i+1；jlen；j+)/从无序子表中项选出最小关键字从无序子表中项选出最小关键字 if(L-recj.keyreck.key)k=j；if(k!=i)/最小关键字项不是无序子表的第最小关键字项不是无序子表的第1个元素个元素 T=L-reci；/最小关键字项换到无序子表第最小关键字项换到无序子表第1个元素的位置个元素的位置 L-reci=L-reck；L-reck=T；第41页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序 3.3.算法分析算法分析算法分析算法分析 时间复杂度：时间复杂度：时间复杂度：时间复杂度：选择第选择第 i个元素，需要个元素，需要n-i 次比较；次比较；总比较次数为：总比较次数为：次次 O(n2)；每选择一个元素最多有每选择一个元素最多有3次元素移动；次元素移动；最多总移动次数为最多总移动次数为 3(n-1)O(n)；时间复杂度为：时间复杂度为：时间复杂度为：时间复杂度为：O(n2)空间复杂度：空间复杂度：空间复杂度：空间复杂度：in place 动态性能：动态性能：动态性能：动态性能：不稳定不稳定 简单选择排序的主要操作简单选择排序的主要操作 “比较比较”：改进改进改进改进 减少比较次数减少比较次数n(n-1)2第42页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序二、堆排序二、堆排序二、堆排序二、堆排序 堆排序堆排序堆排序堆排序(Heap SortHeap Sort)利用堆的特性进行排序，属选择类排序；利用堆的特性进行排序，属选择类排序；1.1.树形选择排序思想树形选择排序思想树形选择排序思想树形选择排序思想 树形选择排序树形选择排序树形选择排序树形选择排序按锦标赛思想进行排序；按锦标赛思想进行排序；简单选择排序：简单选择排序：在在 n个关键字中选出最小值，需个关键字中选出最小值，需n-1次比较；次比较；对其余对其余 n-1个关键字选次小值，需个关键字选次小值，需n-2次比较次比较 减少选择次小值的比较次数的思路减少选择次小值的比较次数的思路 利用选择最小值过程中的比较结果；利用选择最小值过程中的比较结果；例，例，有有8个足球队参加足球锦标赛，需要决出前两名；个足球队参加足球锦标赛，需要决出前两名；若用简单选择法：需赛若用简单选择法：需赛7+6=13场场 第43页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序采用锦标赛的传递规则：采用锦标赛的传递规则：(甲胜乙，乙胜丙，则甲必胜丙甲胜乙，乙胜丙，则甲必胜丙)只需赛只需赛7+2=9 场场 减治策略减治策略减治策略减治策略 ADAEGEEABCDEFGH第一名第一名第一名第一名经过经过7 7场比赛选出第一名场比赛选出第一名淘汰赛过程：淘汰赛过程：第44页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序 利用选拔第一名过程中的比较结果利用选拔第一名过程中的比较结果,选出第二名；选出第二名；根据锦标赛的传递关系，第二名只可能在争夺第一名的比赛根据锦标赛的传递关系，第二名只可能在争夺第一名的比赛 过程中，直接输给第一名的球队中产生，过程中，直接输给第一名的球队中产生，即：在产生第一名的基础上再赛两场即可；即：在产生第一名的基础上再赛两场即可；AAGAABCDDFFGHG第二名第二名第二名第二名第45页，本讲稿共115页7.3 7.3 7.3 7.3 选择排序选择排序选择排序选择排序按照锦标赛思想可实现树形选择排序按照锦标赛思想可实现树形选择排序按照锦标赛思想可实现树形选择排序按照锦标赛思想可实现树形选择排序将将n个关键字个关键字(n=2k)作为完全二叉树作为完全二叉树叶子结点。其排序过程为：叶子结点。其排序过程为：两两比较相邻叶子结点值，把两两比较相邻叶子结点值，把 n/2个小者作为二叉树上一层的个小者作为二叉树上一层的 结点值，对上一层结点值两两比较，选出较小者为二叉树再上结点值，对上一层结点值两两比较，选出较小者为二叉树再上 一层的结点；依次类推，经过一层的结点；依次类推，经过 k层比较选出一个根结点值，即层比较选出一个根结点值，即 为为“最小者最小者”ki，输出输出 ki，并保留各层的比较过程；并保留各层的比较过程；修改最小关键字修改最小关键字ki 所在叶子结点的标志，将其兄弟结点值上移所在叶子结点的标志，将其兄弟结点值上移 至父亲结点中，并与该层兄弟结点值至父亲结点中，并与该层兄弟结点值kp比较；选小者上移至父比较；选小者上移至父 亲结点，再与兄弟比较，选小者上移；依此类推，则根结点为亲结点，再与兄弟比较，选小者上移；依此类推，则根结点为 次小关键字；次小关键字；重复做，从小到大逐次选出各关键字，