數(shù)據(jù)結(jié)構(gòu)排序ppt課件(參考版)
2025-05-03 18:12本頁面
【正文】 本章其他排序方法留給同學(xué)們自學(xué)，如堆排序等?！?基本上是！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！基本上是！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動(dòng)的元素也呈指數(shù)下降，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)，所以速度特別快。數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 ?在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下， 其遞歸樹成為單支樹 ，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。?如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對(duì)兩個(gè)長度減半的子序列進(jìn)行排序，這是最理想的情況。?最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 ?log2(n+1)? 。?可以證明，函數(shù) quicksort的平均計(jì)算時(shí)間也是 O(nlog2n)。因?yàn)榭蛇x任一元素為支點(diǎn)。}對(duì)順序表對(duì)順序表 L進(jìn)行快速進(jìn)行快速排序的操作函數(shù)為：排序的操作函數(shù)為：數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 例 3： 以關(guān)鍵字序列（ 256， 301， 751， 129， 937， 863， 742， 694， 076， 438）為例，寫出執(zhí)行快速算法的 各趟 排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。 }}整個(gè)快速排序的遞歸算法：見教材 P276//長度 1//對(duì)順序表 L中的子序列 r[ low… high] 作快速排序//一趟快排，將 r[ ]一分為二//在左子區(qū)間進(jìn)行遞歸快排，直到長度為 1//在 右子區(qū)間進(jìn)行遞歸快排，直到長度為 1//QSort新的 lowvoid QuickSort ( SqList amp。 QSort ( L, low, pivot1)。YYYNNN一趟快速排序算法流程圖數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 void QSort ( SqList amp。r[i] = r[0]。r[i].key=pivoti。i j amp。r[j].key=pivotj。i ji j amp。r[0]=r[low]。r[i] 0 1 2 3 4 5 6初態(tài) 21 25 49 25* 16 08第 1趟highlow21 0825 1649 25*321pivotkey=2108 2516 49( 08 ， 16 ） 21 （ 25* ， 49， 25 ）25*跑到了前面， 不穩(wěn)定！數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 j從高端 掃描尋找小于pivot的 元素i從低端 掃描尋找大于pivot的 元素i=low。 //返回支點(diǎn)記錄所在位置。 //將比支點(diǎn)大的記錄交換到高端；}r[low]=r[0]。 r[low].key=pivotkey) + +low。 //將比支點(diǎn)小的記錄交換到低端；while(lowhigh amp。 r[high].key=pivotkey ) high。 //取支點(diǎn)的關(guān)鍵碼存入 pivotkey變量while(low high){ //從表的兩端交替地向中間掃描while(lowhigh amp。 r[0]=r[low]。L,int low,int high){ //一趟快排//交換子表 r[low…h(huán)igh] 的記錄，使支點(diǎn)（樞軸）記錄到位，并返回其位置。21， 25， 49， 25*， 16， 08初態(tài)：第 1趟：第 2趟：第 3趟：討論：討論：1. 這種不斷劃分子表的過程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？這種不斷劃分子表的過程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？2. “ 快速排序快速排序 ”” 是否真的比任何排序算法都快？是否真的比任何排序算法都快？08， 16， 21， 25， 25*， (49)2116， 08 ， ( )25， 25*， 49(08)， 16， 21， 25， (25*， 49)數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 ，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？編程時(shí)：① 每一趟的子表的形成是采用從兩頭向中間交替式逼近法；② 由于每趟中對(duì)各子表的操作都相似，主程序可采用遞歸算法。此時(shí)便為有序序列了。心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。?最壞情形： 初始排列逆序， 算法要執(zhí)行 n1趟起泡，第 i趟(1? i? n) 做了 n i 次關(guān)鍵碼比較，執(zhí)行了 ni 次對(duì)象交換。前提： 順序存儲(chǔ)結(jié)構(gòu) 例： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16， 08）， 請(qǐng)寫出冒泡排序的具體實(shí)現(xiàn)過程。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序交換排序的基本思想是：交換排序的基本思想是：數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 1) 冒泡排序基本思路： 每趟不斷將記錄兩兩比較，并按 “前小后大 ”（或 “前大后小 ”）規(guī)則交換。 兩種排序方法的中間狀態(tài)分別描述如后：數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438[256， 301]， 751， 129， 937， 863， 742， 694， 076， 438[256， 301， 751]， 129， 937， 863， 742， 694， 076， 438[129， 256， 301， 751]， 937， 863， 742， 694， 076， 438[129， 256， 301， 751， 937]， 863， 742， 694， 076， 438[129， 256， 301， 751， 863， 937]， 742， 694， 076， 438[129， 256， 301， 742， 751， 863， 937]， 694， 076， 438[129， 256， 301， 694， 742， 751， 863， 937]， 076， 438[076， 129， 256， 301， 694， 742， 751， 863， 937]， 438[076， 129， 256， 301， 438， 694， 742， 751， 863， 937]第 1趟第 2趟第 3趟第 4趟第 5趟第 6趟第 7趟第 8趟第 9趟數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 原始序列： 256，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1