數(shù)據(jù)結(jié)構(gòu)專題排序和查找第一頁(yè)，共三十七頁(yè)，2022年，8月28日已經(jīng)學(xué)過(guò)的排序算法（7種）第2章計(jì)數(shù)排序選擇排序冒泡排序插入排序（折半插入排序）第3章箱子排序基數(shù)排序第9章堆排序2第二頁(yè)，共三十七頁(yè)，2022年，8月28日已經(jīng)學(xué)過(guò)的查找方法（5種）第7章哈希查找第11章BST查找AVL查找紅黑樹(shù)查找B樹(shù)查找3第三頁(yè)，共三十七頁(yè)，2022年，8月28日主要內(nèi)容歸并排序快速排序希爾排序排序算法的分析與比較關(guān)于查找的討論4第四頁(yè)，共三十七頁(yè)，2022年，8月28日歸并排序考慮用分治方法解決排序問(wèn)題原子問(wèn)題——n=1分解方法一前n-1個(gè)元素為集合A，最后一個(gè)為集合B對(duì)A遞歸地使用分治方法進(jìn)行排序，B自然有序A、B合并——插入排序!第五頁(yè)，共三十七頁(yè)，2022年，8月28日簡(jiǎn)單分治排序分解方法二選出最大的元素作為B，剩余的作為A對(duì)A遞歸地進(jìn)行排序無(wú)需合并——性能差——?jiǎng)澐植黄胶膺x擇排序！第六頁(yè)，共三十七頁(yè)，2022年，8月28日平衡劃分——?dú)w并排序A——n/k個(gè)元素，B——n-n/k個(gè)元素k=2時(shí)，均勻劃分A、B排序完成后，合并（merge）它們第七頁(yè)，共三十七頁(yè)，2022年，8月28日思想對(duì)于一個(gè)需要排序的數(shù)組A[0…n-1]，把它一分為二：A[0…n/2-1]和A[n/2…n-1]，并對(duì)每個(gè)子數(shù)組遞歸排序然后把這兩個(gè)排好序的子數(shù)組合并為一個(gè)有序數(shù)組歸并排序第八頁(yè)，共三十七頁(yè)，2022年，8月28日//Mergesortifn>1 copyA[0…n/2-1]toB[0…n/2-1] copyA[n/2…n-1]toC[0…n/2-1] Mergesort(B[0…n/2-1]) Mergesort(C[0…n/2-1]) Merge(B,C,A)算法描述時(shí)間代價(jià)較小，空間消耗較多第九頁(yè)，共三十七頁(yè)，2022年，8月28日思想對(duì)兩個(gè)有序數(shù)組的合并初始狀態(tài)下，關(guān)注兩個(gè)待合并數(shù)組的第一個(gè)元素然后比較這兩個(gè)元素的大小，將較小的元素添加到一個(gè)新創(chuàng)建的數(shù)組中接著被復(fù)制數(shù)組中的下標(biāo)后移，指向該較小元素的后繼元素上述操作一直持續(xù)到兩個(gè)數(shù)組中的一個(gè)被處理完為止然后在未處理完的數(shù)組中，剩下的元素被復(fù)制到新數(shù)組的尾部Merge算法10第十頁(yè)，共三十七頁(yè)，2022年，8月28日//Merge(B[0…p-1],C[0…q-1],A[0…p+q-1])i0,j0,k0whilei<pandj<qdo ifB[i]<=C[j] A[k]B[i] ii+1 else A[k]C[j] jj+1 kk+1ifi=p copyC[j…q-1]toA[k…p+q-1]else copyB[i…p-1]toA[k…p+q-1]Merge算法描述第十一頁(yè)，共三十七頁(yè)，2022年，8月28日算法演示第十二頁(yè)，共三十七頁(yè)，2022年，8月28日例題有8個(gè)關(guān)鍵字8,3,2,9,7,1,5,4，使用歸并排序方法將其排列為升序序列，給出排序過(guò)程解：初始：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排序結(jié)束。13第十三頁(yè)，共三十七頁(yè)，2022年，8月28日自然歸并排序naturalmergesort進(jìn)一步改進(jìn)：若原始序列中存在有序子序列，則不進(jìn)行分解[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]第十四頁(yè)，共三十七頁(yè)，2022年，8月28日主要內(nèi)容歸并排序快速排序希爾排序排序算法的分析與比較關(guān)于查找的討論15第十五頁(yè)，共三十七頁(yè)，2022年，8月28日思想按照元素的值進(jìn)行劃分對(duì)給定數(shù)組中的元素進(jìn)行重新排列，以得到一個(gè)快速排序的分區(qū)在一個(gè)分區(qū)中，所有在s下標(biāo)之前的元素都小于等于A[s]，所有在s下標(biāo)之后的元素都大于等于A[s]建立了一個(gè)分區(qū)以后，A[s]已經(jīng)位于它在有序數(shù)組中的最終位置。接下來(lái)使用同樣的方法繼續(xù)對(duì)A[s]前和A[s]后的子數(shù)組分別進(jìn)行排序快速排序第十六頁(yè)，共三十七頁(yè)，2022年，8月28日//Quicksort[A[l…r]]//input:數(shù)組A[0…n-1]中的子數(shù)組A[l…r]//output:排序后的數(shù)組ifl<r sPartition(A[l…r]) Quicksort(A[l…s-1]) Quicksort(A[s+1…r])算法描述算法的前提是選擇一個(gè)元素，根據(jù)該元素的值來(lái)劃分子數(shù)組，這個(gè)元素就是中軸，我們暫時(shí)選擇數(shù)組的第一個(gè)元素作為中軸，即p=A[l]第十七頁(yè)，共三十七頁(yè)，2022年，8月28日思想為了建立一個(gè)分區(qū)，有許多不同的方法對(duì)元素重新排列，其中一種是基于兩次掃描子數(shù)組的高效算法一次是從左到右，另一次是從右到左，每次都把子數(shù)組的元素和中軸進(jìn)行比較從左到右的掃描（i）從第二個(gè)元素開(kāi)始，因?yàn)槲覀兿Ｍ∮谥休S的元素位于子數(shù)組的第一部分，掃描會(huì)忽略小于中軸的元素，直到遇到第一個(gè)大于等于中軸的元素才會(huì)停止從右到左的掃描（j）從最后一個(gè)元素開(kāi)始，掃描忽略大于中軸的元素，直到遇到第一個(gè)小于等于中軸的元素才會(huì)停止兩次掃描停止后，取決于掃描的指針是否相交，會(huì)發(fā)生3種不同的情況Partition算法第十八頁(yè)，共三十七頁(yè)，2022年，8月28日描述如果掃描指針i和j不相交，也就是說(shuō)i<j，簡(jiǎn)單的交換A[i]和A[j]分別對(duì)i加一、j減一，然后繼續(xù)開(kāi)始掃描示意情況一第十九頁(yè)，共三十七頁(yè)，2022年，8月28日描述如果掃描指針相交，也就是說(shuō)i>j，把中軸和A[j]交換示意情況二第二十頁(yè)，共三十七頁(yè)，2022年，8月28日描述如果指針停下來(lái)時(shí)指向的是同一個(gè)元素，也就是說(shuō)i=j，被指向元素的值一定等于p，此時(shí)建立的分區(qū)中分裂點(diǎn)的位置S=i=j示意情況三第二十一頁(yè)，共三十七頁(yè)，2022年，8月28日pA[l]il,jr+1repeat repeatii+1untilA[i]>=p repeatjj-1untilA[j]<=p swap(A[i],A[j])untili>=jswap(A[i],A[j])swap(A[l],A[j])returnjPartition算法描述算法合并了情況二和情況三，即當(dāng)i=j時(shí)也做了一次無(wú)謂的交換i可能越界而j不可能越界，因此實(shí)現(xiàn)時(shí)需要對(duì)i進(jìn)行特殊處理第二十二頁(yè)，共三十七頁(yè)，2022年，8月28日第二十三頁(yè)，共三十七頁(yè)，2022年，8月28日改進(jìn)隨機(jī)數(shù)、兩平均、三平均中軸選擇算法當(dāng)子數(shù)組足夠小時(shí)改用最簡(jiǎn)單的排序算法綜合運(yùn)用這些措施，可縮減20%時(shí)間快速排序的改進(jìn)第二十四頁(yè)，共三十七頁(yè)，2022年，8月28日提示快速排序算法要求熟練掌握源代碼25第二十五頁(yè)，共三十七頁(yè)，2022年，8月28日主要內(nèi)容歸并排序快速排序希爾排序排序算法的分析與比較關(guān)于查找的討論26第二十六頁(yè)，共三十七頁(yè)，2022年，8月28日希爾排序又叫縮小增量排序算法思想：設(shè)待排序列含n個(gè)元素取整數(shù)gap=floor(n/3)+1，將每隔gap的元素放在一個(gè)子序列中，對(duì)子序列插入排序然后縮小間隔，令gap=floor(gap/3)+1，對(duì)新的子序列插入排序重復(fù)上述過(guò)程，直至gap=1時(shí)最后執(zhí)行一次27第二十七頁(yè)，共三十七頁(yè)，2022年，8月28日Shell排序例第二十八頁(yè)，共三十七頁(yè)，2022年，8月28日Shell排序例（續(xù)）第二十九頁(yè)，共三十七頁(yè)，2022年，8月28日算法分析開(kāi)始時(shí)序列數(shù)較多，每個(gè)序列元素?cái)?shù)較少，排序快排序后期子序列元素?cái)?shù)增多，但大多有序，再執(zhí)行插入排序效率較高希爾排序性能與gap選取有關(guān)，一般認(rèn)為其優(yōu)于O(n2)，但很難達(dá)到O(nlogn)30第三十頁(yè)，共三十七頁(yè)，2022年，8月28日實(shí)現(xiàn)template<classT>voidShellSort(Ta[],intn){ intincrement,start; for(increment=n/3+1;increment>=1; increment=increment/3+1) for(start=0;start<increment;start++) insertsort_interval(a,n,start,increment);}第三十一頁(yè)，共三十七頁(yè)，2022年，8月28日實(shí)現(xiàn)（續(xù)）template<classT>voidinsertsort_interval(Ta[],intn,intstart, intincrement){ for(inti=start+increment;i<n;i+=increment) { Tt=a[i]; for(intj=i–increment;j>=start&&t<a[j]; j-=increment) a[j+increment]=a[j]; a[j+increment]=t; }}第三十二頁(yè)，共三十七頁(yè)，2022年，8月28日主要內(nèi)容歸并排序快速排序希爾排序排序算法的分析與比較關(guān)于查找的討論33第三十三頁(yè)，共三十七頁(yè)，2022年，8月28日時(shí)間復(fù)雜度比較初始序列有序時(shí)34第三十四頁(yè)，共三十七頁(yè)，2022年，8月28日部分結(jié)論（1）平均來(lái)看，快排最優(yōu)，但若初始序列有序，則快排性能降至n2級(jí)。使用三平均選中軸法可避免最差情況，結(jié)合插入排序效果更好。（2）插