數(shù)據(jù)結(jié)構(gòu)排序ppt課件(編輯修改稿)
2024-11-30 22:18 本頁面
【文章內(nèi)容簡介】 amp。L, int low, int high) //對順序表 [low～ high]作快速排序 { if(lowhigh) //表長大于 1 { pivot_location = Partition(L, low, high)。 //以樞軸為基準(zhǔn)，將順序表一分為二，返回樞軸位置 QSort(L, low, pivot_location 1)。 //對樞軸低端子表遞歸排序 QSort(L, pivot_location + 1, high)。 //對樞軸高端子表遞歸排序 } } 例子程序參見： 快速排序 ? 性能分析： ? 平均時間復(fù)雜度： O(nlogn)，最壞時，如序列恰好有序或恰好逆序時為： O(n2)。 ? 輔助空間： O(logn)，最壞時為 O(n)(實現(xiàn)遞歸算法需要棧空間，最壞時會遞歸 n層 )。但注意存儲記錄的輔助空間只需要 1個 ? 穩(wěn)定性：不穩(wěn)定。 三、選擇排序 ? ★ 每一趟從第 i到第 n個元素中 選取關(guān)鍵字最小的記錄將其放到第 i個位置 (如最小記錄與第 i個記錄交換 ) 趟次 49 38 65 97 76 13 27 49*1 13 38 65 97 76 49 27 49*2 13 27 65 97 76 49 38 49*3 13 27 38 97 76 49 65 49*4 13 27 38 49 76 97 65 49*5 13 27 38 49 49*97 65 766 13 27 38 49 49*65 97 767 13 27 38 49 49*65 76 97簡單選擇排序 ? 算法 1： void Select_Sort(SqList amp。L) { for(i=1。 i。 i++) //i：趟次，即找到的最小元素的目標(biāo)位置。 { //每趟從 [i～ length]中找出最小的元素，與第 i個元素交換 min=i。 //首先假設(shè)子表中首元素最小 for(j=i+1。 j=。 j++) //注意前后兩個循環(huán) 走向相同 if([j].key [min].key) min=j。 if(min!=i) [min] [i]。 //將該記錄與第 i個記錄交換 } } 第 2 趟 13 27 65 97 76 49 38 49 *第 3 趟 13 27 38 97 76 49 65 49 *簡單選擇排序 ? 算法 2(P277)： void Select_Sort(SqList amp。L) { for(i=1。 i。 i++) { j=SelectMinKey(L, i)。 //在 [i..length]中查找 key最小的記錄 if(i!=j) [i] [j]。 //將該記錄與第 i個記錄交換 } } ? 例子程序參見： 簡單選擇排序 ? 提問： ? ？ ? 答：上述算法不穩(wěn)定 (如首元素為 38時 ) 。但找到最小元素后若將其插入到目標(biāo)位置，則算法是穩(wěn)定的！ ? 32154進(jìn)行從小到大的排序，經(jīng)過一趟簡單選擇排序之后的序列怎樣？ ? 答： 12354，如果采用順序移動策略，則為 13254 ? 簡單選擇排序與冒泡排序的區(qū)別：交換數(shù)量減少、趟次增加、不穩(wěn)定。 問題：如何提高選擇的速度以提高性能？ 樹形選擇排序 ? ? 引言：如何減少簡單選擇排序的比較次數(shù)：第二趟找最小的元素時利用前一趟的比較結(jié)果。 ? 例如： 49， 38， 65， 97， 76， 13， 27， 49*，第一趟中存在的比較： 49－ 38， 38－ 65， 38－ 97， 38－ 76， 38－ 13， 13－ 27， 13－ 49*。決出冠軍 13之后，選亞軍只需要比較 38， 27， 49*(因 49，65， 97， 76已與 38比較過 )。如果把兩兩比較作為一種數(shù)據(jù)間的關(guān)系，該操作可以用下圖形象表示： 樹形選擇排序 ? 樹形選擇排序 (錦標(biāo)賽排序 )：首先對 n個記錄的關(guān)鍵字進(jìn)行 兩兩 比較，然后在其中一半較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。利用樹形結(jié)構(gòu)很容易理解和實現(xiàn)。 注意該方法與通過構(gòu)造二叉排序樹來排序不同 (二叉排序樹的非終端結(jié)點存儲有真正的記錄 ) 堆排序 ? ★ 引言：樹形選擇排序需要構(gòu)建一個完全二叉樹 (不是滿二叉樹，為什么？ )，非終端結(jié)點并不存儲元素，輔助空間多。改進(jìn)方法：讓每個結(jié)點都存儲元素，最緊湊的方法是使用 完全二叉樹的順序存儲結(jié)構(gòu)，為了讓樹根關(guān)鍵字值最小，需要改進(jìn)策略。 答：是，小頂堆 堆排序 ? 堆 ： n個元素的序列 {k1,k2,...,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為 堆 (小頂堆 )： ki=k2i且 ki=k2i+1 (i=1,2,...,n/2)。 (或者說滿足 ki=k[i/2], i=2,3,...,n) ? 理解：它對應(yīng)的二叉樹中各結(jié)點都小于兩個孩子結(jié)點(故不是二叉排序樹 )。 提問：序列 123456是堆嗎？ 堆排序 ? 利用堆可以搜尋最小元素，進(jìn)而可用來排序。方法是輸出堆頂元素 (如把堆頂元素與最末元素交換 )，然后把剩余元素調(diào)整為堆，再輸出堆頂元素、再調(diào)整 … ? 利用堆排序要解決兩個問題： ? 如何由一個無序序列建成一個堆 —— 初建堆 ? 輸出堆頂元素后，如何調(diào)整剩余元素成為一個新的堆 —— 堆調(diào)整 或 篩選 堆排序 ? 問題 2的解決方法： 注：排序思路 —— 按圖示過程不斷對 小頂堆進(jìn)行輸出堆調(diào)整，各趟堆調(diào)整全部結(jié)束以后，整個序列將變成一個 從大到小的有序序列 。 堆排序 ? 問題 1的解決方法 (基于堆調(diào)整完成初建堆 )： 堆排序 ? 算法 (注 :要使 排序結(jié)果從小到大 ，要建立
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1