數(shù)據(jù)結(jié)構(gòu)第7章PPT課件

1、17.1 排序術(shù)語及記號(hào)第1頁/共80頁2術(shù)語關(guān)系是任意的，如通常經(jīng)常使用的小于、大于等關(guān)系或任意的關(guān)系。第2頁/共80頁3術(shù)語第3頁/共80頁4基本操作第4頁/共80頁57.2 三種代價(jià)為O(n2)的排序方法第5頁/共80頁67.2.1 7.2.1 插入排序插入排序 算法思想：逐個(gè)處理待排序的記錄，每個(gè)記錄都要與前面那些已排好序的記錄進(jìn)行比較，然后插入到適當(dāng)?shù)奈恢?。?頁/共80頁77.2.1 教材上插入排序算法交換次數(shù)為交換次數(shù)為3i=3n(n-1)/2=3i=3n(n-1)/2=(n(n2 2) )（一次（一次swapswap需需要交換要交換3 3次）次） 平均情況：平均情況：(n(n2

2、 2) )i=1n-1i=1n-1第7頁/共80頁8改進(jìn)的插入排序算法第8頁/共80頁9改進(jìn)插入排序算法分析i=1n-1第9頁/共80頁10加入監(jiān)視哨的插入排序算法第10頁/共80頁11利用二分法的插入排序 思想： 在插入第i個(gè)記錄時(shí)，前面的記錄已經(jīng)有序。 故可以用二分法查找第i個(gè)記錄的正確位置。第11頁/共80頁127.2.2 起泡排序算法思想： 若序列中有n 個(gè)元素，通常進(jìn)行n -1 趟。 第1 趟，針對(duì)第Vector0 至Vectorn-1個(gè)元素進(jìn)行。第2 趟，針對(duì)第Vector1至Vectorn-1 個(gè)元素進(jìn)行第n-1 趟，針對(duì)第Vectorn-2至Vectorn-1 個(gè)元素進(jìn)行。 每

3、一趟進(jìn)行的過程： 從第一個(gè)元素開始，比較兩個(gè)相鄰的元素。若相鄰的元素的相對(duì)位置不正確，則進(jìn)行交換；否則繼續(xù)比較下面兩個(gè)相鄰的元素。第12頁/共80頁137.2.2 起泡排序 不停地比較相鄰的記錄，如果不滿足排序要求，就交換相鄰記錄，直到所有的記錄都已經(jīng)排好序。第13頁/共80頁14教材上起泡排序算法第14頁/共80頁15起泡排序算法分析 穩(wěn)定 空間代價(jià)：(1)（此章我們僅分析排序所需額外空間開銷） 時(shí)間代價(jià)： 比較次數(shù)： 最佳、最差i=n(n-1)/2=(n2) 交換次數(shù)最多為(n2) ，最少為0，平均為(n2)。 最大，最小，平均時(shí)間代價(jià)均為(n2) 。1i=n-1第15頁/共80頁16優(yōu)化

4、的起泡算法 改進(jìn)：檢查每次起泡過程中是否發(fā)生過交換，如果沒有，則表明整個(gè)數(shù)組已經(jīng)排好序，排序結(jié)束。 避免不必要的比較。第16頁/共80頁17改進(jìn)的起泡排序算法第17頁/共80頁18優(yōu)化起泡排序算法分析第18頁/共80頁197.2.3 直接選擇排序算法思想：找出剩下的未排序記錄中的最小記錄，然后直接與數(shù)組中第i個(gè)記錄交換，比起泡排序減少了移動(dòng)次數(shù)。第19頁/共80頁20直接選擇排序算法第20頁/共80頁21算法分析不 穩(wěn)定 空間代價(jià)：(1) 時(shí)間代價(jià)： 比較次數(shù)： 最好、最壞情況均為(n-i-1)=n*(n-1)/2，即(n2) 交換次數(shù)：最好（自身交換）、最壞3(n-1)（一次swap需要交換

5、3次），故(n) 總時(shí)間代價(jià)：(n2) 。i=0n-2第21頁/共80頁22交換指針，減少交換記錄的次數(shù)第22頁/共80頁23小結(jié)：時(shí)間代價(jià)第23頁/共80頁24小結(jié)：時(shí)間代價(jià)（2） 時(shí)間復(fù)雜度為(n2)的原因： 一個(gè)長(zhǎng)度為n序列平均有n(n-1)/4對(duì)逆置 任何一種只對(duì)相鄰記錄進(jìn)行比較的排序算法的平均時(shí)間代價(jià)都是(n2)第24頁/共80頁257.3 Shell 排序（希爾排序） 直接插入排序的兩個(gè)性質(zhì)： 在最好情況（序列本身已是有序的）下時(shí)間代價(jià)為(n) 對(duì)于短序列，直接插入排序比較有效 Shell排序有效地利用了直接插入排序的這兩個(gè)性質(zhì)第25頁/共80頁26Shell 排序 算法思想： 先

6、將序列轉(zhuǎn)化為若干小序列，在這些小序列內(nèi)進(jìn)行插入排序 逐漸擴(kuò)大小序列的規(guī)模，而減少小序列個(gè)數(shù)，使得待排序序列逐漸處于更有序的狀態(tài) 最后對(duì)整個(gè)序列進(jìn)行掃尾直接插入排序，從而完成排序第26頁/共80頁27Shell 排序第27頁/共80頁28shell排序算法（增量除以2遞減） inssort2(A, n, 1);第28頁/共80頁29算法分析不 穩(wěn)定 空間代價(jià)：(1) 時(shí)間代價(jià)： 增量每次除以2遞減，則為(n2) 選擇合適的增量序列，可以使時(shí)間代價(jià)接近：(n) 。第29頁/共80頁30Shell排序增量選擇問題 增量每次除以2遞減時(shí)，效率仍然為(n2) 問題：選取的增量之間并不互質(zhì) 間距為2k-1

7、的子序列都是由那些間距為2k的子序列組成的 上一輪循環(huán)中這些子序列都已經(jīng)排過序了，導(dǎo)致處理效率不高第30頁/共80頁31 Hibbard增量序列 2k -1，2k-1 -1，7，3，1， Shell(3)和Hibbard增量序列的Shell排序的效率可以達(dá)到(n3/2) 選取其他增量序列還可以更進(jìn)一步減少時(shí)間代價(jià)第31頁/共80頁327.4 快速排序 分治法排序：將原始數(shù)組分為若干個(gè)子部分，然后分別進(jìn)行排序。 分治策略的實(shí)例 BST查找、插入、刪除算法 快速排序、歸并排序 二分檢索 主要思想 劃分 求解子問題(子問題不重疊) 綜合子問題解，成為問題的解第32頁/共80頁33快速排序算法思想算法

8、思想：若序列中有n 個(gè)元素，任選一個(gè)關(guān)鍵字作為軸值，將序列分成兩部分。其中左半部分的結(jié)點(diǎn)的關(guān)鍵字小于等于軸值，右半部分的結(jié)點(diǎn)的關(guān)鍵字大于軸值，然后對(duì)左右兩部分分別進(jìn)行類似的處理，直至排好序?yàn)橹?。關(guān)鍵問題：選擇軸值（pivot）將序列劃分為兩個(gè)子序列L和R，使得L中所有記錄都小于或等于軸值，R中記錄都大于軸值對(duì)子序列L和R遞歸進(jìn)行快速排序第33頁/共80頁34快速排序示例第34頁/共80頁35軸值選擇分割過程 整個(gè)快速排序的關(guān)鍵，軸值位于正確位置，分割后使得： L中所有記錄位于軸值左邊 R中記錄位于軸值右邊軸值選擇 盡可能使L，R長(zhǎng)度相等 選擇策略： 選擇最左邊記錄 隨機(jī)選擇 選擇平均值第35頁

9、/共80頁36一次分割過程 選擇軸值并存儲(chǔ)軸值 最后一個(gè)元素放到軸值位置 初始化下標(biāo)i, j，分別指向頭尾 i遞增直到遇到比軸值大的元素，將此元素覆蓋到j(luò)的位置； j遞減直到遇到比軸值小的元素，將此元素覆蓋到i的位置 重復(fù)上一步直到i=j，將軸值放到i的位置，完畢第36頁/共80頁37快速排序?qū)嵗S值60606060606060第37頁/共80頁38快速排序算法（教材 p149-150 ) return (i+j)/2; return (i+j)/2; 第38頁/共80頁39快速排序算法（教材 p150 )第39頁/共80頁40軸 值 選 在 最 左第40頁/共80頁41快速排序算法分析（1）

10、n-1k=1 不穩(wěn)定算法 時(shí)間復(fù)雜度（交換次數(shù)遠(yuǎn)小于比較次數(shù)，主要考慮比較次數(shù)） 最差情況：軸值總是為當(dāng)前序列的最小值或者最大值。 k=(n2).軸值10，共比較7次軸值20，共比較6次 軸值60 ，共比較2次軸值70 ，共比較1次原因：軸值選擇不當(dāng)。改進(jìn)：隨機(jī)選取軸值或最左、最右、中間三個(gè)元素中的值處于中間的作為軸值，通?？梢员苊庾顗那闆r。第41頁/共80頁42快速排序算法分析（2） 最佳情況：軸值總是將當(dāng)前序列均分為2個(gè)子序列。 共經(jīng)過logn次分割，故(nlog n)第42頁/共80頁43快速排序算法分析（3） 假設(shè)在每次分割時(shí)，軸值處于最終排序好的數(shù)組中位置的概率是一樣的。 也就是說，

11、軸值將數(shù)組分成長(zhǎng)度為0和n-1，1和n-2，的子序列的概率是相等的，都為1/n 長(zhǎng)度為n的序列，時(shí)間為T(n) ，T(0) = T(1) =1，設(shè)選擇軸值時(shí)間為常數(shù) 分割時(shí)間為cn 分割后長(zhǎng)度分別為k 和n-1-k 對(duì)子序列進(jìn)行快速排序所需時(shí)間分別為T(k)和T(n-1-k) 求解遞推方程T(n)= cn +1/n*(T(k)+T(n1k)= cn +2/n*T(k)n-1k=0n-1k=0第43頁/共80頁44快速排序算法分析（4） 最差情況： 時(shí)間代價(jià)： (n2) 空間代價(jià)（系統(tǒng)占用堆?？臻g代價(jià)）： (n) 最佳情況： 時(shí)間代價(jià)：(nlog n) 空間代價(jià)：(log n) 平均情況： 時(shí)間

12、代價(jià)：(nlog n) 空間代價(jià)：(log n)第44頁/共80頁45優(yōu)化的快速排序可能優(yōu)化： 軸值選擇 小子串不遞歸 子數(shù)組小于某個(gè)長(zhǎng)度（閾值n=9）時(shí)，不遞歸 塊與塊之間有序 最后對(duì)整個(gè)數(shù)組進(jìn)行一次插入排序 消除遞歸 避免進(jìn)出棧、恢復(fù)斷點(diǎn)等工作。速度加快。第45頁/共80頁467.5 歸并排序算法思想 簡(jiǎn)單地將原始序列劃分為兩個(gè)子序列 分別對(duì)每個(gè)子序列遞歸排序 最后將排好序的子序列合并為一個(gè)有序序列，即歸并過程第46頁/共80頁477.5 歸并排序第47頁/共80頁48歸并排序算法（教材p154） else if (Comp:lt(tempi1, tempi2) else if (Comp

13、:lt(tempi1, tempi2) Acurr = tempi1+; Acurr = tempi1+; else Acurr = tempi2+; else Acurr = tempi2+;第48頁/共80頁49優(yōu)化歸并排序 同優(yōu)化的快速排序一樣，對(duì)基本已排序序列直接插入排序 歸并時(shí)從兩端開始處理，向中間推進(jìn)第49頁/共80頁50優(yōu)化歸并排序算法 tempright-j+1 = Aj+mid; tempright-j+1 = Aj+mid; for (i=left,j=right, for (i=left,j=right,k=leftk=left; ; k k=right; k+) =ri

14、ght; k+) /歸并歸并 if (tempi tempj) Ak = tempi+; if (tempi tempj) Ak = tempi+; else Ak = tempj-; else Ak = tempj-; 第50頁/共80頁51歸并排序算法分析穩(wěn)定設(shè)需排序元素的數(shù)目為n，遞歸的深度為logn（簡(jiǎn)單起見，設(shè)n是2的冪），第一層遞歸是對(duì)一個(gè)長(zhǎng)度為n的數(shù)組排序，下一層是對(duì)兩個(gè)長(zhǎng)度為n/2的子數(shù)組排序，最后一層對(duì)n個(gè)長(zhǎng)度為1的子數(shù)組排序?？臻g復(fù)雜度：S(n)=(n)時(shí)間復(fù)雜度：不依賴于原始輸入序列T(n)=(nlog2n)也適用于：外部排序第51頁/共80頁527.6 堆排序第52頁/

15、共80頁53堆排序算法 第53頁/共80頁54Heapsort Example (1)第54頁/共80頁55Heapsort Example (2)第55頁/共80頁56堆排序算法分析第56頁/共80頁577.7 分配排序和基數(shù)排序第57頁/共80頁587.7 分配排序和基數(shù)排序 不需要進(jìn)行紀(jì)錄之間兩兩比較 需要事先知道記錄序列的一些具體情況 事先知道序列中的記錄都位于某個(gè)小區(qū)間段0，m)內(nèi) 將具有相同值的記錄都分配到同一個(gè)桶中，然后依次按照編號(hào)從桶中取出記錄，組成一個(gè)有序序列第58頁/共80頁59分配排序第59頁/共80頁60基數(shù)排序Radix Sort 第60頁/共80頁61基數(shù)排序算法

16、for (j=0; jn; j+) Aj = Bj; for (j=0; jn; j+) Aj = Bj; /將記錄復(fù)制回將記錄復(fù)制回A A 第61頁/共80頁62Radix Sort Example第62頁/共80頁63基數(shù)排序算法效率第63頁/共80頁64第四章中基數(shù)排序問題解答第64頁/共80頁65第四章中基數(shù)排序問題解答續(xù)第65頁/共80頁66第四章中基數(shù)排序問題解答續(xù)第66頁/共80頁677.8 對(duì)各種排序算法的實(shí)驗(yàn)比較 1第67頁/共80頁68Empirical Comparison 2第68頁/共80頁69Empirical Comparison 3第69頁/共80頁707.9

17、排序問題的下限第70頁/共80頁71插入排序的判定樹第71頁/共80頁72基于比較的排序問題的下限第72頁/共80頁73排序問題的時(shí)間代價(jià)第73頁/共80頁74第七章小結(jié)u 排序的基本概念u 關(guān)鍵碼、初始關(guān)鍵碼排列u 時(shí)間代價(jià)：關(guān)鍵碼比較次數(shù)、數(shù)據(jù)移動(dòng)次數(shù)u 穩(wěn)定性u(píng) 輔助空間代價(jià)，u 用實(shí)例表明直接插入排序的過程u 直接插入排序算法u排序的性能分析當(dāng)待排序的關(guān)鍵碼序列已經(jīng)基本有序時(shí)，用直接插入排序最快 第74頁/共80頁75小結(jié)u 用實(shí)例表明起泡排序和快速排序的過程u 起泡排序的算法 u 快速排序的遞歸算法和用棧實(shí)現(xiàn)的非遞歸算法 快速排序是一個(gè)遞歸的排序法 當(dāng)待排序關(guān)鍵碼序列已經(jīng)基本有序時(shí)，

18、快速排序顯著變慢。u 用實(shí)例表明直接選擇排序、堆排序的過程u 直接選擇排序和堆排序的算法u 兩種選擇排序的性能分析 用直接選擇排序在一個(gè)待排序區(qū)間中選出最小的數(shù)據(jù)時(shí)，與區(qū)間第一個(gè)數(shù)據(jù)對(duì)調(diào)，不是順次后移。這導(dǎo)致方法不穩(wěn)定。在堆排序中將待排序的數(shù)據(jù)組織成完全二叉樹的順序存儲(chǔ)。第75頁/共80頁76小結(jié)u 用實(shí)例表明二路歸并排序的過程u 歸并排序的優(yōu)化算法u 該算法的性能分析 歸并排序可以遞歸執(zhí)行 歸并排序需要較多的附加存儲(chǔ)。歸并排序?qū)Υ判蜿P(guān)鍵碼的初始排列不敏感，故排序速度較穩(wěn)定。第76頁/共80頁77小結(jié)算法名稱算法名稱最大時(shí)間最大時(shí)間代價(jià)代價(jià)平均時(shí)間平均時(shí)間最小時(shí)間最小時(shí)間輔助空間輔助空間代價(jià)代價(jià)穩(wěn)定穩(wěn)定性性直接插入直接插入排序排序(n2)(n2)(n2)(1)穩(wěn)定穩(wěn)定二分法插二分法插入排序入排序(n2)(n2)(nlogn)(1)穩(wěn)定穩(wěn)定冒泡排序冒泡排序(n2)(n2)(n2)(1)穩(wěn)定穩(wěn)定優(yōu)化的冒優(yōu)化的冒泡排序泡排序(n2)(n2)(n)(1)穩(wěn)定穩(wěn)定選擇排序選擇排序(n2)(n2)(n2)(1)不穩(wěn)不穩(wěn)定定第77頁/共80頁78小結(jié)算法名稱算法名稱最大時(shí)間最