數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁
2025-04-30 18:12本頁面
【正文】 =pivotkey ) high。 r[low]=r[high]。 //將比支點小的記錄交換到低端；while(lowhigh amp。amp。 r[low].key=pivotkey) + +low。 r[high]=r[low]。 //將比支點大的記錄交換到高端；}r[low]=r[0]。 //支點記錄到位；return low。 //返回支點記錄所在位置。}//Partition數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 Low=high=3， 本趟停止，將支點定位并返回位置信息例 2： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16，08）， 請寫出快速排序算法的一趟實現(xiàn)過程。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ù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 j從高端 掃描尋找小于pivot的 元素i從低端 掃描尋找大于pivot的 元素i=low。 j=high。r[0]=r[low]。 pivot=r[low].key。i ji j amp。amp。r[j].key=pivotj。r[i] = r[j]。i j amp。amp。r[i].key=pivoti。r[j] = r[i]。r[i] = r[0]。return ok。YYYNNN一趟快速排序算法流程圖數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 void QSort ( SqList amp。L, int low, int high ) { if ( low high) { pivot = Partition ( L, low, high )。 QSort ( L, low, pivot1)。 QSort ( L, pivot+1, high )。 }}整個快速排序的遞歸算法：見教材 P276//長度 1//對順序表 L中的子序列 r[ low… high] 作快速排序//一趟快排，將 r[ ]一分為二//在左子區(qū)間進行遞歸快排，直到長度為 1//在 右子區(qū)間進行遞歸快排，直到長度為 1//QSort新的 lowvoid QuickSort ( SqList amp。L) {QSort (L, 1, )。}對順序表對順序表 L進行快速進行快速排序的操作函數(shù)為：排序的操作函數(shù)為：數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 例 3： 以關(guān)鍵字序列（ 256， 301， 751， 129， 937， 863， 742， 694， 076， 438）為例，寫出執(zhí)行快速算法的 各趟 排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438第 1趟第 2趟第 3趟第 4趟256， 301， 751， 129， 937， 863， 742， 694， 076， 438076， 129， 256， 751， 937， 863， 742， 694， 301， 438要求模擬算法實現(xiàn)步驟256076 301129 751256， ， ， 438， 301， 694， ， ， 863， 937751076， 129， 256， 438， 301， 694， 742， 751， 863， 937， ， ， 301， ， ， ， ， ，438076， 129， 256， 301， 438， 694， 742， 751， 863， 937時間效率：時間效率： O(nlog2n) —— 因為每趟確定的元素呈指數(shù)增加因為每趟確定的元素呈指數(shù)增加空間效率：空間效率： O（（ log2n）） —— 因為算法的遞歸性，要用到?？臻g因為算法的遞歸性，要用到棧空間穩(wěn)穩(wěn) 定定 性：性： 不穩(wěn)定不穩(wěn)定 —— 因為可選任一元素為支點。因為可選任一元素為支點。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 快速排序算法詳細分析：?快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù) （新的 low和 high） 。?可以證明，函數(shù) quicksort的平均計算時間也是 O(nlog2n)。 實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個 。?最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 ?log2(n+1)? 。 因此，要求存儲開銷為 o(log2n)。?如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。此時，快速排序的趟數(shù)最少。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 ?在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下， 其遞歸樹成為單支樹 ，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經(jīng)過 n1 趟才能把所有對象定位，而且第 i 趟需要經(jīng)過 ni 次關(guān)鍵碼比較才能找到第 i 個對象的安放位置，總的關(guān)鍵碼比較次數(shù)將達到 n2/2? 快速排序是一個 不穩(wěn)定 的排序方法數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 討論 2. “ 快速排序 ” 是否真的比任何排序算法都快？設(shè)每個子表的支點都在中間（比較均衡），則：第 1趟比較，可以確定 1個元素的位置；第 2趟比較（ 2個子表），可以再確定 2個元素的位置；第 3趟比較（ 4個子表），可以再確定 4個元素的位置；第 4趟比較（ 8個子表），可以再確定 8個元素的位置； ……只需 ?log2n? ＋ 1趟便可排好序。———— 基本上是！因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的！基本上是！因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程時使用了交替逼近技巧，更進一步減少了移動次數(shù)，所以速度特別快。教材 P276有證明：快速排序的平均排序效率為 O(nlog2n)；但最壞情況 (例如已經(jīng)有序 )下仍為 O(n2),改進措施見 P277。本章其他排序方法留給同學們自學，如堆排序等。
教學課件相關(guān)推薦
鄂ICP備17016276號-1