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

思想对两个有序数组的合并初始状态下，关注两个待合并数组的第一个元素然后比较这两个元素的大小，将较小的元素添加到一个新创建的数组中接着被复制数组中的下标后移，指向该较小元素的后继元素上述操作一直持续到两个数组中的一个被处理完为止然后在未处理完的数组中，剩下的元素被复制到新数组的尾部Merge算法第10页,共37页，星期六，2024年，5月//Merge(B[0…p-1],C[0…q-1],A[0…p+q-1])i?0,j?0,k?0whileipandjqdo ifB[i]=C[j] A[k]?B[i] i?i+1 else A[k]?C[j] j?j+1 k?k+1ifi=p copyC[j…q-1]toA[k…p+q-1]else copyB[i…p-1]toA[k…p+q-1]Merge算法描述第11页,共37页，星期六，2024年，5月算法演示第12页,共37页，星期六，2024年，5月例题有8个关键字8,3,2,9,7,1,5,4，使用归并排序方法将其排列为升序序列，给出排序过程解：初始：8,3,2,9,7,1,5,4第一趟：3,8,2,9,1,7,4,5第二趟：2,3,8,9,1,4,5,7第三趟：1,2,3,4,5,7,8,9排序结束。第13页,共37页，星期六，2024年，5月自然归并排序naturalmergesort进一步改进：若原始序列中存在有序子序列，则不进行分解[4,8,3,7,1,5,6,2]

?[4,8],[3,7],[1,5,6],[2]

?[3,4,7,8],[1,2,5,6]

?[1,2,3,4,5,6,7,8]第14页,共37页，星期六，2024年，5月主要内容归并排序快速排序希尔排序排序算法的分析与比较关于查找的讨论第15页,共37页，星期六，2024年，5月思想按照元素的值进行划分对给定数组中的元素进行重新排列，以得到一个快速排序的分区在一个分区中，所有在s下标之前的元素都小于等于A[s]，所有在s下标之后的元素都大于等于A[s]建立了一个分区以后，A[s]已经位于它在有序数组中的最终位置。接下来使用同样的方法继续对A[s]前和A[s]后的子数组分别进行排序快速排序第16页,共37页，星期六，2024年，5月//Quicksort[A[l…r]]//input:数组A[0…n-1]中的子数组A[l…r]//output:排序后的数组iflr s?Partition(A[l…r]) Quicksort(A[l…s-1]) Quicksort(A[s+1…r])算法描述算法的前提是选择一个元素，根据该元素的值来划分子数组，这个元素就是中轴，我们暂时选择数组的第一个元素作为中轴，即p=A[l]第17页,共37页，星期六，2024年，5月思想为了建立一个分区，有许多不同的方法对元素重新排列，其中一种是基于两次扫描子数组的高效算法一次是从左到右，另一次是从右到左，每次都把子数组的元素和中轴进行比较从左到右的扫描（i）从第二个元素开始，因为我们希望小于中轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会停止从右到左的扫描（j）从最后一个元素开始，扫描忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止两次扫描停止后，取决于扫描的指针是否相交，会发生3种不同的情况Partition算法第18页,共37页，星期六，2024年，5月描述如果扫描指针i和j不相交，也就是说ij，简单的交换A[i]和A[j]分别对i加一、j减一，然后继续开始扫描示意情况一第19页,共37页，星期六，2024年，5月描述如果扫描指针相交，也就是说ij，把中轴和A[j]交换示意情况二第20页,共37页，星期六，2024年，5月描述如果指针停下来时指向的是同一个元素，也就是说i=j，被指向元素的值一定等于p，此时建立的分区中分裂点的位置S=i=j示意情况三第21页,共37页，星期六，2024年，5月p?A[l]i?l,j?r+1repeat repeati?i+1untilA[i]=p repeatj?j-1untilA[j]=p swap(A[i],A[j])untili=jswap(A[i],A[j])swap(A[l],A[j])returnjPartition算法描述算法合并了情况二和情况三，即当i=