【正文】 ?選擇問(wèn)題 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 75 合并排序 ?基本思想： ?劃分： ?將待排序元素分成大小大致相同的 2個(gè)子序列 ?求解子問(wèn)題 ?分別對(duì) 2個(gè)子序列進(jìn)行排序 ?合并 ?將排好序的兩個(gè)子序列合并成為一個(gè)有序序列。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 76 合并排序 ?二路歸并排序的分治策略是： ?劃分 ： ?將待排序序列 r1, r2, …, rn劃分為兩個(gè)長(zhǎng)度相等的子序列 r1, …, rn/2和 rn/2＋ 1, …, rn； ?求解子問(wèn)題 ： ?分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子序列； ?合并 ： ?將這兩個(gè)有序子序列合并成一個(gè)有序序列。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 77 合并排序 ?如圖所示 r1 … … rn/2 rn/2＋ 1 … … rn 劃分 r’1… … r’n/2 r’n/2＋ 1… … r’n 遞歸處理 r39。39。1…… r39。39。n/2r39。39。n/2＋ 1 …… r 39。39。n 合并解 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 78 合并排序 ?算法描述（遞歸）： void MergeSort(Type a[], int left, int right){ if (leftright) { //至少有 2個(gè)元素 int i=(left+right)/2。 //取中點(diǎn) mergeSort(a, left, i)。 mergeSort(a, i+1, right)。 merge(a, b, left, i, right)。 //合并到數(shù)組 b copy(a, b, left, right)。 //復(fù)制回?cái)?shù)組 a } } 復(fù)雜度分析 T(n)=O(nlogn) ???????11)()2/(2)1()(nnnOnTOnT算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 79 合并排序 ?實(shí)驗(yàn)表明 ? 合并排序在 n30后即體現(xiàn)出比（標(biāo)準(zhǔn)）插入排序更加優(yōu)越的性能。 ?需要注意的是： ? 合并排序的時(shí)間復(fù)雜性適合于所有情況：最好、最壞或平均。這是合并排序的最大的特點(diǎn) ——“一視同仁” ? 復(fù)雜性的關(guān)鍵體現(xiàn)在合并過(guò)程， “先享受，然后付出代價(jià)” ? 合并排序的另一個(gè)缺陷： ?“異地排序”（ out of place sort） 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 80 快速排序 ?快速排序的分治策略： ?（ 1）劃分 ?選定一個(gè)記錄作為 軸值 (杠桿點(diǎn) )，以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列 r1 … ri1和 ri+1 … rn，前一個(gè)子序列中記錄的值均小于或等于軸值，后一個(gè)子序列中記錄的值均大于或等于軸值； [ r1 … … ri1 ] ri [ ri+1 … … rn ] ≤ri 軸值 ≥ri 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 81 快速排序 ?（ 2）求解子問(wèn)題 ?分別對(duì)劃分后的每一個(gè)子序列遞歸處理； ?（ 3）合并 ?由于對(duì)子序列 r1 … ri1和 ri+1 … rn的排序是 就地 進(jìn)行的，所以合并不需要執(zhí)行任何操作。 “先付出，然后享受勞動(dòng)成果 ” 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 82 快速排序 ?例如： 13 65 27 50 38 49 55 j i j j 13 65 27 50 49 55 j i i i 13 65 27 50 49 55 i j j j 38 j 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 83 templateclass Type int Partition (Type a[ ], int p, int r){ int i = p, j = r 。 Type x=a[p]。 while (ij) { while (ij amp。amp。 a[j] x) j 。 a[i]=a[j]。 while (ij amp。amp。 a[i]=x) ++i。 a[j]=a[i]。 } a[i] =x。 return i。 } 快速排序 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 84 快速排序算法 void QuickSort (Type a[ ], int p, int r){ if (pr) { int q=Partion(a,p,r) QuickSort (a,p,q1)。 //對(duì)左半段排序 QuickSort (a,q+1,r)。 //對(duì)右半段排序 } } 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 85 快速排序 ?快速排序算法的性能取決于劃分的對(duì)稱性。 最壞情況復(fù)雜度分析 2( ) ( )( 1 ) 1()( 1 ) ( ) 1OnT n OTnT n O nnn??? ?? ? ??? ?最好情況復(fù)雜度分析 ( 1 ) 1()2 ( / 2) (( ) ( l og ))1OnTnT n O nnnT n O n???? ?????平均情況復(fù)雜度分析 ( ) ( l o g )T n O n n?算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 86 2022計(jì)算機(jī)科學(xué)學(xué)院 劉芳 60 各排序算法平均時(shí)間的曲線圖 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 87 快速排序 ?快速排序算法的優(yōu)點(diǎn) ? 算法的 韌性 很強(qiáng)，只要分解不是按照最壞情況進(jìn)行，其排序的結(jié)果就能達(dá)到最優(yōu)。 ? 原地排序 算法 ? 人們可以通過(guò)對(duì) 軸值的選擇 進(jìn)行微調(diào)，就能使算法得到巨大改善，實(shí)驗(yàn)表明：快速排序的速度是合并排序的 2倍。 ?思考：軸值的選??？ ? 傳統(tǒng)的方法 ? 一種安全的做法 ——隨機(jī)選取 ? 中值法（三值中值法） 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 88 隨機(jī)化快速排序 ?基本思想 ? a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。 ?算法描述 ?隨機(jī)數(shù)發(fā)生器 int random(int a,int b){ return rand( )% (b－ a)+a } 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 89 隨機(jī)化快速排序 ?隨機(jī)化的 劃分算法 int randomizedPartion( type a[],int p,int r){ int i=ramdom(p,r)。 swap(a[i],a[p])。 return Partition(a,p,r)。 } 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 90 隨機(jī)化快速排序 ?隨機(jī)化快速排序算法 void QuickSort_random (Type a[ ], int p, int r){ if (pr) { int q=randomizedpartion(a,p,r) QuickSort_random (a,p,q1)。 //對(duì)左半段排序 QuickSort_random t (a,q+1,r)。 //對(duì)右半段排序 } } 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 91 選擇問(wèn)題 ?問(wèn)題提出： ?設(shè)無(wú)序序列 T={r1,r2,…,r n}， T的第 k（ 1≤k≤n ）小的元素定義為 T按升序排列后在第 k個(gè)位置上的元素。 ?對(duì)給定序列 T和一個(gè)整數(shù) k，尋找 T的第 k小的元素的問(wèn)題稱為選擇問(wèn)題。 ?應(yīng)用： ?選擇問(wèn)題的一個(gè)應(yīng)用就是尋找中值元素 。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 92 選擇問(wèn)題 ?應(yīng)用實(shí)例 ——中值濾波 ?在信號(hào)采集過(guò)程中，由于電子設(shè)備的不穩(wěn)定性會(huì)對(duì)獲取的信號(hào)產(chǎn)生噪聲，中值濾波就是一種降噪技術(shù)。 ?一維信號(hào)中值濾波是用 中值 代替規(guī)定位置（一般是原始信號(hào)序列的中心位置）的信號(hào)值。 ?對(duì)二維的數(shù)字圖像而言，中值濾波就是用一個(gè)活動(dòng)窗口沿圖像移動(dòng)，窗口中心位置的象素灰度用窗口內(nèi)所有象素灰度的中值來(lái)代替。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳