數(shù)據(jù)結(jié)構(gòu)課件(c語言)第10章排序(編輯修改稿)
2025-02-16 06:35 本頁面
【文章內(nèi)容簡(jiǎn)介】 立的兩部分 ，其中 一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小 ，則可 分別對(duì)這兩部分記錄進(jìn)行排序 ，以達(dá)到整個(gè)序列有序。 Data Structure Page 27 2022/2/17 ? 排序過程 對(duì) r[s…… t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針 i和 j，設(shè)樞軸記錄 rp=r[s]， x=，初始時(shí) 令 i=s,j=t； ? 首先， 從 j所指位置向前搜索第一個(gè)關(guān)鍵字小于 x的記錄，并和 rp交換 ； ? 再 從 i所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于 x的記錄，和 rp交換 ； ? 重復(fù)上述兩步， 直至 i==j為止 ； ? 再 分別對(duì)兩個(gè)子序列進(jìn)行快速排序 ， 直到每個(gè)子序列只含有一個(gè)記錄為止 。 Data Structure Page 28 2022/2/17 49 38 65 97 76 13 27 49 27 i 初始關(guān)鍵字： j x 49 j i i 65j 13 i 97j j 49 49 38 65 97 76 13 27 49 初始關(guān)鍵字： 完成一趟排序： 27 38 13 49 76 97 65 49 一次劃分后： ( 27 38 13 ) 49 ( 76 97 65 49 ) 分別進(jìn)行快速排序： ( 13 ) 27 ( 38 ) 49 ( 49 65 ) 76 ( 97 ) ( 13 ) 27 ( 38 ) 49 49 (65) 76 ( 97 ) 快速排序結(jié)束： 13 27 38 49 49 65 76 97 不穩(wěn)定的排序方法 Data Structure Page 29 2022/2/17 一趟快速排序的算法 int Partition ( SqList amp。L, int low, int high){ // 交換順序表 L中子表 r[low..high]中的記錄，樞軸記錄到位，并返回 // 其所在位置，此時(shí)，在它之前（后）的記錄均不大（?。┯谒?。 [0] = [low]。 //用子表的第一個(gè)記錄作樞軸記錄 pivotkey = [low].key。 // 樞軸記錄關(guān)鍵字 while (low high) { // 從表的兩端交替地向中間掃描 while (low high amp。amp。 [high].key = pivotkey) high。 [low++] = [high]。 // 將比樞軸記錄小的記錄移到低端 while (low high amp。amp。 [low].key = pivotkey) ++low。 [high] = [low]。 // 將比樞軸記錄大的記錄移到高端 } // while [low] = [0]。 // 樞軸記錄到位 return low。 // 返回樞軸位置 } // Partition Data Structure Page 30 2022/2/17 快速排序算法 void Qsort(SqList amp。L, int low, int high){ //對(duì)順序表 L中的子序列 [low… high]作快速排序 if (low high) { //長(zhǎng)度大于 1 pivotloc= Partition(L,low,high)。 //將 [low… high]劃分 Qsort(L,low,pivotloc1)。 //對(duì)低子表排序 Qsort(L, pivotloc+1,high)。 //對(duì)高子表排序 } }// Qsort void QuickSort(SqList amp。L){ //對(duì)順序表 L作快速排序 Qsort(L,1,)。 }// QuickSort 時(shí)間復(fù)雜度 T(n)=O(n178。) Data Structure Page 31 2022/2/17 ?算法分析 ? 時(shí)間復(fù)雜度 ? 最好情況（每次總是選到中間值作樞軸） T(n)=O(nlog2n) ? 最壞情況（每次總是選到最小或最大元素作樞軸） T(n)=O(n178。) ? 為防止最差情況的出現(xiàn)， 一般采取 “ 三者取中 ” 法來確定樞軸。即在第一個(gè)記錄和最后一個(gè)記錄，以及中間位置的記錄中，選取值為中間的那個(gè)來作樞軸，這樣就能防止最差情況的出現(xiàn)。 ? 空間復(fù)雜度 ：需?？臻g以實(shí)現(xiàn)遞歸 ? 最壞情況： S(n)=O(n) ? 一般情況： S(n)=O(log2n) ? 對(duì)隨機(jī)的關(guān)鍵字序列，快速排序是 目前被認(rèn)為是最好的排序方法 。 Data Structure Page 32 2022/2/17 選擇排序 ?基本思想 ? 每一趟在 ni+1（ i=1,2,… ,n1）個(gè)記錄中選取關(guān)鍵字最小的記錄， 并將它和第 i個(gè)記錄進(jìn)行互換，從而 使其成為有序序列中第 i個(gè)記錄。 簡(jiǎn)單選擇排序 ?排序過程 ? 首先，通過 n1次關(guān)鍵字比較 ， 從 n個(gè)記錄中找出關(guān)鍵字最小的記錄 ，將它 與第一個(gè)記錄交換 ； ? 再通過 n2次比較 ，從剩余的 n1個(gè)記錄中 找出關(guān)鍵字次小的記錄 ，將它 與第二個(gè)記錄交換 ； ? 重復(fù)上述操作， 共進(jìn)行 n1趟排序后，排序結(jié)束 。 Data Structure Page 33 2022/2/17 13 ( 38 65 97 76 49 27 49 ) 初始： ( 49 38 65 97 76 13 27 49 ) i=1 13 49 i=2 27 38 i=3 i=4 i=5 i=6 13 27 ( 65 97 76 49 38 49 ) 38 65 13 27 38 ( 97 76 49 65 49 ) 49 97 13 27 38 49 ( 76 97 65 49 ) 49 76 13 27 38 49 76 ( 97 65 ) 49 76 65 97 13 27 38 49 76 97 ( 97 ) 49 76 65 76 97排序結(jié)束 13 27 38 49 76 97 65 ( ) 49 76 76 9765 76 穩(wěn)定的排序方法 Data Structure Page 34 2022/2/17 簡(jiǎn)單選擇排序算法 void SelectSort (SqList amp。L){ // 對(duì)順序表 L作簡(jiǎn)單選擇排序 for (i=1。 i。 ++i) { // 選擇第 i 小的記錄，并交換到位 j = i。 for ( k=i+1。 k=。 k++ ) // 在 [i..]中選擇關(guān)鍵字最小的記錄 if ( LT( [k].key , [j].key )) j =k 。 if ( i!=j ) [j] ? [i]。 // 與第 i 個(gè)記錄互換 }// for } // SelectSort 時(shí)間復(fù)雜度 T(n)=O(n178。) Data Structure Page 35 2022/2/17 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ? 記錄移動(dòng)次數(shù) ? 最好情況： 0 ? 最壞情況： 3(n1) ? 比較次數(shù)： )(21)( 211nninni??????? 空間復(fù)雜度 ： S(n)=O(1) Data Structure Page 36 2022/2/17 堆排序 ?堆的定義 ? n個(gè)元素的序列 (k1,k2,…… kn)， 當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆。 221iiiikkkk ???? ??或 221iiiikkkk ???? ??1, 2 , , 2ni ??? ????? 若將 此序列 對(duì)應(yīng)的一維數(shù)組 看成是一個(gè)完全二叉樹 ，則 ki為二叉樹的根結(jié)點(diǎn)， k2i和 k2i+1分別為 ki的 “ 左子樹根 ” 和 “ 右子樹根 ” 。 Data Structure Page 37 2022/2/17 （ 96， 83， 27， 38， 11， 9） （ 13， 38， 27， 50， 76， 65， 49， 97） 96 27 9 11 38 83 13 27 38 49 65 76 50 97 大頂堆 小頂堆 Data Structure Page 38 2022/2/17 ?堆排序 ? 將無序序列建成一個(gè)堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余?n1個(gè)元素重又建成一個(gè)堆，則可得到 n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列 的過程。 ?堆排序需解決的兩個(gè)問題 ： ? 如何由一個(gè) 無序序列建成一個(gè)堆 ？ (初始建堆 ) ? 如何在輸出堆頂元素之后， 調(diào)整 剩余元素，使之 成為一個(gè)新的堆 ？ Data Structure Page 39 2022/2/17 ?第二個(gè)問題解決方法 —— 篩選（以 小頂堆 為例） ? 輸出堆頂元素 之后， 以堆
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1