可視化計算第5章排序與查找a-資料下載頁
2025-05-02 06:20本頁面
【正文】 并排序 ? 歸并排序也叫合并排序是分治法一個非常典型的應(yīng)用 ? 歸并排序法是將兩個或更多個有序表合并成一個新的有序表 ? 如果是將兩個有序表合并成一個有序表，被稱為 2路歸并 36 37 歸并排序 main子圖 38 歸并排序 input子圖（ I） 39 歸并排序 input子圖（ II） 40 歸并算法實現(xiàn)的說明 ? 待排的兩路數(shù)據(jù)存放在一個文件中，文件中的頭兩個數(shù)據(jù)，分別是兩路數(shù)據(jù)的個數(shù)（可以不等長）； ? 在得到線形表的長度后，再用兩個數(shù)組 a[]、b[]保存待排數(shù)據(jù) ? 第一個 排序 循環(huán)過程是對兩個數(shù)組的元素逐個進行比對，并輸出較小的數(shù)據(jù)元素； ? 第二個循環(huán)過程是在比對輸出完成后，仍有一個線形表的數(shù)據(jù)尚未輸出完畢，所以再將有剩余元素的數(shù)組進行輸出 41 歸并排序 merge子圖（ I） 42 歸并排序 merge子圖（ II） 43 排序算法的分析 ? 冒泡排序顯然最容易實現(xiàn)對已經(jīng)存在的無序線形表進行排序，所以最為最常見； ? 插入排序?qū)τ陔S機產(chǎn)生的無序數(shù)據(jù)，可以實現(xiàn)實時排序； ? 歸并排序的前提是存在兩個以上已經(jīng)排序的線形表； ? 桶排序則適用于可以進行分類的數(shù)據(jù)排序； ? 快速排序則是最能體現(xiàn)時間復(fù)雜性優(yōu)化的排序算法，但要關(guān)注其在不同的實現(xiàn)環(huán)境中，可能因空間復(fù)雜性所帶來的問題 44 排序算法的分析 穩(wěn)定性分類 算法名稱 時間復(fù)雜性 空間復(fù)雜性 穩(wěn)定排序 冒泡排序 O(n^2) O(1) 插入排序 O(n^2) O(1) 桶排序 O(n) O(k) 空間 合并排序 O(nlogn) O(n) 空間 不穩(wěn)定排序 快速排序 O(nlogn) 最壞 O(n^2) 穩(wěn)定性分類 算法名稱 時間復(fù)雜性 空間復(fù)雜性 45 End of ch51 46
教學課件相關(guān)推薦
鄂ICP備17016276號-1