数据结构专题排序和查找.ppt

数据结构专题排序和查找数据结构专题排序和查找现在学习的是第1页，共37页已经学过的排序算法（已经学过的排序算法（7 7种）种）第第2 2章章计数排序计数排序选择排序选择排序冒泡排序冒泡排序插入排序（折半插入排序）插入排序（折半插入排序）第第3 3章章箱子排序箱子排序基数排序基数排序第第9 9章章堆排序堆排序2现在学习的是第2页，共37页已经学过的查找方法（已经学过的查找方法（5 5种）种）第第7 7章章哈希查找哈希查找第第1111章章BSTBST查找查找AVLAVL查找查找红黑树查找红黑树查找B B树查找树查找3现在学习的是第3页，共37页主要内容主要内容归并排序归并排序快速排序快速排序希尔排序希尔排序排序算法的分析与比较排序算法的分析与比较关于查找的讨论关于查找的讨论4现在学习的是第4页，共37页归并排序归并排序考虑用分治方法解决排序问题考虑用分治方法解决排序问题原子问题原子问题n=1n=1分解方法一分解方法一前前n-1n-1个元素为集合个元素为集合A A，最后一个为集合，最后一个为集合B B对对A A递归地使用分治方法进行排序，递归地使用分治方法进行排序，B B自然有序自然有序A A、B B合并合并插入排序!现在学习的是第5页，共37页简单分治排序简单分治排序分解方法二分解方法二选出最大的元素作为选出最大的元素作为B B，剩余的作为，剩余的作为A A对对A A递归地进行排序递归地进行排序无需合并无需合并性能差性能差划分不平衡划分不平衡选择排序！现在学习的是第6页，共37页平衡划分平衡划分归并排序归并排序An/kAn/k个元素，个元素，Bn-n/kBn-n/k个元素个元素k=2k=2时，均匀划分时，均匀划分A A、B B排序完成后，合并（排序完成后，合并（mergemerge）它们）它们现在学习的是第7页，共37页思想思想对于一个需要排序的数组对于一个需要排序的数组A0n-1A0n-1，把它一分为二：，把它一分为二：A0n/2-1A0n/2-1和和An/2n-1An/2n-1，并对每个子数组递归排序，并对每个子数组递归排序然后把这两个排好序的子数组合并为一个有序数组然后把这两个排好序的子数组合并为一个有序数组归并排序归并排序现在学习的是第8页，共37页/Mergesort/Mergesortif n1if n1copy A0n/2-1 to B0n/2-1copy A0n/2-1 to B0n/2-1copy An/2n-1 to C0n/2-1copy An/2n-1 to C0n/2-1Mergesort(B0n/2-1)Mergesort(B0n/2-1)Mergesort(C0n/2-1)Mergesort(C0n/2-1)Merge(B,C,A)Merge(B,C,A)算法描述算法描述时间代价较小，空间消耗较多现在学习的是第9页，共37页思想思想对两个有序数组的合并对两个有序数组的合并初始状态下，关注两个待合并数组的第一个元素初始状态下，关注两个待合并数组的第一个元素然后比较这两个元素的大小，将较小的元素添加到然后比较这两个元素的大小，将较小的元素添加到一个新创建的数组中一个新创建的数组中接着被复制数组中的下标后移，指向该较小元素的后继接着被复制数组中的下标后移，指向该较小元素的后继元素元素上述操作一直持续到两个数组中的一个被处理完为止上述操作一直持续到两个数组中的一个被处理完为止然后在未处理完的数组中，剩下的元素被复制到新数然后在未处理完的数组中，剩下的元素被复制到新数组的尾部组的尾部MergeMerge算法算法10现在学习的是第10页，共37页/Merge(B0p-1,C0q-1,A0p+q-1)i0,j0,k0while ip and jq doif Bi=CjAkBiii+1elseAkCjjj+1kk+1if i=pcopy Cjq-1 to Akp+q-1elsecopy Bip-1 to Akp+q-1MergeMerge算法描述算法描述现在学习的是第11页，共37页算法演示算法演示现在学习的是第12页，共37页例题例题有有8 8个关键字个关键字8,3,2,9,7,1,5,48,3,2,9,7,1,5,4，使用归并排序方，使用归并排序方法将其排列为升序序列，给出排序过程法将其排列为升序序列，给出排序过程解：解：初初 始：始：8,3,2,9,7,1,5,4 8,3,2,9,7,1,5,4第一趟：第一趟：3,8,2,9,1,7,4,53,8,2,9,1,7,4,5第二趟：第二趟：2,3,8,9,1,4,5,72,3,8,9,1,4,5,7第三趟：第三趟：1,2,3,4,5,7,8,91,2,3,4,5,7,8,9排序结束。排序结束。13现在学习的是第13页，共37页自然归并排序自然归并排序natural merge sortnatural merge sort进一步改进：若原始序列中存在有序子序列，进一步改进：若原始序列中存在有序子序列，则不进行分解则不进行分解4,8,3,7,1,5,6,24,8,3,7,1,5,6,24,8,3,7,1,5,6,24,8,3,7,1,5,6,23,4,7,8,1,2,5,63,4,7,8,1,2,5,61,2,3,4,5,6,7,81,2,3,4,5,6,7,8现在学习的是第14页，共37页主要内容主要内容归并排序归并排序快速排序快速排序希尔排序希尔排序排序算法的分析与比较排序算法的分析与比较关于查找的讨论关于查找的讨论15现在学习的是第15页，共37页思想思想按照元素的值进行划分按照元素的值进行划分对给定数组中的元素进行重新排列，以得到一个快速排序的分区对给定数组中的元素进行重新排列，以得到一个快速排序的分区在一个分区中，所有在在一个分区中，所有在s s下标之前的元素都小于等于下标之前的元素都小于等于AsAs，所有，所有在在s s下标之后的元素都大于等于下标之后的元素都大于等于AsAs建立了一个分区以后，建立了一个分区以后，AsAs已经位于它在有序数组中的最终位已经位于它在有序数组中的最终位置。接下来使用同样的方法继续对置。接下来使用同样的方法继续对AsAs前和前和AsAs后的子数组分别后的子数组分别进行排序进行排序快速排序快速排序现在学习的是第16页，共37页/QuicksortAlr/QuicksortAlr/input:/input:数组数组A0n-1A0n-1中的子数组中的子数组AlrAlr/output:/output:排序后的数组排序后的数组if lrif lrs sPartition(Alr)Partition(Alr)Quicksort(Als-1)Quicksort(Als-1)Quicksort(As+1r)Quicksort(As+1r)算法描述算法描述算法的前提是选择一个元素，根据该元素的值来划分子数组，这个元素就是中轴，我们暂时选择数组的第一个元素作为中轴，即p=Al现在学习的是第17页，共37页思想思想为了建立一个分区，有许多不同的方法对元素重新排列，其中一种是为了建立一个分区，有许多不同的方法对元素重新排列，其中一种是基于基于两次扫描两次扫描子数组的高效算法子数组的高效算法一次是从左到右，另一次是从右到左，每次都把子数组的元素和一次是从左到右，另一次是从右到左，每次都把子数组的元素和中轴进行比较中轴进行比较从左到右的扫描（从左到右的扫描（i i）从第二个元素开始，因为我们希望小于中轴的）从第二个元素开始，因为我们希望小于中轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到元素位于子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会第一个大于等于中轴的元素才会停止停止从右到左的扫描（从右到左的扫描（j j）从最后一个元素开始，扫描忽略大于中轴的元素，）从最后一个元素开始，扫描忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会直到遇到第一个小于等于中轴的元素才会停止停止两次扫描停止后，取决于扫描的指针是否相交，会发生两次扫描停止后，取决于扫描的指针是否相交，会发生3 3种不同的情况种不同的情况PartitionPartition算法算法现在学习的是第18页，共37页描述描述如果扫描指针如果扫描指针i i和和j j不相交，也就是说不相交，也就是说ijijij，把中轴和，把中轴和AjAj交换交换示意示意情况二情况二现在学习的是第20页，共37页描述描述如果指针停下来时指向的是同一个元素，也就是说如果指针停下来时指向的是同一个元素，也就是说i=ji=j，被指向元素的值一定等于，被指向元素的值一定等于p p，此时建立的分区中，此时建立的分区中分裂点的位置分裂点的位置S=i=jS=i=j示意示意情况三情况三现在学习的是第21页，共37页p pAlAli il,jl,jr+1r+1repeatrepeatrepeat irepeat ii+1 until Ai=pi+1 until Ai=prepeat jrepeat jj-1 until Aj=pj-1 until Aj=juntil i=jswap(Ai,Aj)swap(Ai,Aj)swap(Al,Aj)swap(Al,Aj)return jreturn jPartitionPartition算法描述算法描述算法合并了情况二和情况三，即当i=j时也做了一次无谓的交换i可能越界而j不可能越界，因此实现时需要对i进行特殊处理现在学习的是第22页，共37页现在学习的是第23页，共37页改进改进随机数、两平均、三平均中轴选择算法随机数、两平均、三平均中轴选择算法当子数组足够小时改用最简单的排序算法当子数组足够小时改用最简单的排序算法综合运用这些措施，可缩减综合运用这些措施，可缩减20%20%时间时间快速排序的改进快速排序的改进现在学习的是第24页，共37页提示提示快速排序算法要求熟练掌握源代码快速排序算法要求熟练掌握源代码25现在学习的是第25页，共37页主要内容主要内容归并排序归并排序快速排序快速排序希尔排序希尔排序排序算法的分析与比较排序算法的分析与比较关于查找的讨论关于查找的讨论26现在学习的是第26页，共37页希尔排序希尔排序又叫缩小增量排序又叫缩小增量排序算法思想：设待排序列含算法思想：设待排序列含n n个元素个元素取整数取整数gap=floor(n/3)+1gap=floor(n/3)+1，将每隔，将每隔gapgap的元素放在一个子的元素放在一个子序列中，对子序列插入排序序列中，对子序列插入排序然后缩小间隔，令然后缩小间隔，令gap=floor(gap/3)+1gap=floor(gap/3)+1，对新的子序列，对新的子序列插入排序插入排序重复上述过程，直至重复上述过程，直至gap=1gap=1时最后执行一次时最后执行一次27现在学习的是第27页，共37页ShellShell排序例排序例现在学习的是第28页，共37页ShellShell排序例（续）排序例（续）现在学习的是第29页，共37页算法分析算法分析开始时开始时序列数较多，每个序列元素数较少，排序快序列数较多，每个序列元素数较少，排序快排序后期排序后期子序列元素数增多，但大多有序，再执行插入排序效子序列元素数增多，但大多有序，再执行插入排序效率较高率较高希尔排序性能与希尔排序性能与gapgap选取有关，一般认为其优于选取有关，一般认为其优于O O(n(n2 2)，但很难达到，但很难达到O(nlogn)O(nlogn)30现在学习的是第30页，共37页实现实现templatevoid ShellSort(T a,int n)int increment,start;for(increment=n/3+1;increment=1;increment=increment/3+1)for(start=0;start increment;start+)insertsort_interval(a,n,start,increment);现在学习的是第31页，共37页实现（续）实现（续）templatevoid insertsort_interval(T a,int n,int start,int increment)for(int i=start+increment;i=start&t aj;j-=increment)aj+increment=aj;aj+increment=t;现在学习的是第32页，共37页主要内容主要内容归并排序归并排序快速排序快速排序希尔排序希尔排序排序算法的分析与比较排序算法的分析与比较关于查找的讨论关于查找的讨论33现在学习的是第33页，共37页时间复杂度比较时间复杂度比较初始序列有序时初始序列有序时34现在学习的是第34页，共37页部分结论部分结论（1 1）平均来看，快排最优，但若初始序列有序，则快排）平均来看，快排最优，但若初始序列有序，则快排性能降至性能降至n n2 2级。使用三平均选中轴法可避免最差情级。使用三平均选中轴法可避免最差情况，结合插入排序效果更好。况，结合插入排序效果更好。（2 2）插入、选择、冒泡都属）插入、选择、冒泡都属“简单排序简单排序”，复杂度是，复杂度是n n2 2，它们中间当待排序列基本有序或，它们中间当待排序列基本有序或n n较小时，插入排较小时，插入排序更好。序更好。35现在学习的是第35页，共37页部分结论部分结论（3 3）稳定排序算法有：插入、冒泡、归并、基数）稳定排序算法有：插入、冒泡、归并、基数（4 4）不稳定排序算法有：简单选择、希尔、快速、）不稳定排序算法有：简单选择、希尔、快速、堆排序堆排序36现在学习的是第36页，共37页主要内容主要内容归并排序归并排序快速排序快速排序希尔排序希尔排序排序算法的分析与比较排序算法的分析与比较关于查找的讨论关于查找的讨论37现在学习的是第37页，共37页