試談數(shù)據(jù)結(jié)構(gòu)研究-資料下載頁
2025-06-22 19:50本頁面
【正文】 ra算法(迪克斯特拉算法,1959)； 權(quán)值為任意值的單源最短路徑問題(固定源點) －BellmanFord算法(貝爾曼－福特算法)； BellmanFord算法的改進(jìn) － SPFA算法； 所有頂點之間的最短路徑問題－FloydWarshall算法(弗洛伊德算法)；6_10 Dijkstra算法 算法 掌握原理 完整程序252。 為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。第7章 內(nèi)排序編號 知識點 類型 掌握程度 代碼要求7_01 排序問題的基本概念 概念 理解 : 在計算機(jī)應(yīng)用軟件中經(jīng)常需要對所管理的各種數(shù)據(jù)進(jìn)行處理，排序往往是這些數(shù)據(jù)處理中需要用到的核心運算。: 內(nèi)排序：如果待排序的記錄個數(shù)較少，整個排序過程中所有的記錄都可以直接存放在內(nèi)存中，這樣的排序叫做內(nèi)排序(internal sorting)。: 外排序：如果待排序的記錄數(shù)量太大，內(nèi)存無法容納所有的記錄，因此排序過程中還需要訪問外存，這樣的排序叫做外排序(external sorting)。: 由于討論的是內(nèi)排序，在大部分情況下本章都是考慮基于順序存儲的排序，即待排序的數(shù)據(jù)是存儲在數(shù)組中。: 記錄(record)：參與排序的元素稱為記錄，記錄是進(jìn)行排序的基本單位。: 序列(sequence)：所有待排序記錄的集合稱為序列。所謂排序就是將序列中的記錄按照特定的順序排列起來。7_02 用系統(tǒng)函數(shù)實現(xiàn)排序 應(yīng)用 掌握方法 完整程序: 在實際編程時，可能不需要自己實現(xiàn)排序算法，直接調(diào)用系統(tǒng)函數(shù)實現(xiàn)排序即可。但這并不意味著本章介紹的排序算法原理、程序?qū)崿F(xiàn)不需要掌握。: 實現(xiàn)排序的系統(tǒng)函數(shù)主要有：qsort、sort函數(shù): qsort函數(shù)： 采用快速排序算法()實現(xiàn)。: sort函數(shù)： STL提供的算法，常常結(jié)合STL中的容器和迭代器使用。7_03 插入法排序 算法 掌握原理 完整程序: 逐個處理待排序的記錄，每個新記錄都要與前面那些已排好序的記錄進(jìn)行比較，然后插入到適當(dāng)?shù)奈恢谩?_04 冒泡法排序 算法 掌握原理 完整程序54204520425042054202402042002冒泡法是不是一定要比較n1趟？不一定！比如前面的例2中，n=8，但實際上只需要進(jìn)行5趟比較，后面2趟沒有進(jìn)行交換。也就是說，如果在某一趟比較過程中，沒有發(fā)現(xiàn) 前一個數(shù)比后一個數(shù)大的情況，即沒有進(jìn)行交換數(shù)據(jù)，那么后面就不需要再進(jìn)行比較了。極端的情況，假設(shè)n個數(shù)已經(jīng)是按從小到大的順序排好了，那么實際上只需要進(jìn)行一趟比較就可以得出結(jié)論了。7_05 選擇法排序 算法 掌握原理 完整程序直接選擇排序法也需要用一個二重循環(huán)來實現(xiàn)，同樣可以帶著以下3個類似問題來理解其思想(有n個數(shù)，要求按照從小到大的順序排序)：1) 要進(jìn)行多少趟選擇？—— 要進(jìn)行n1趟選擇(第0趟，第1趟，…，第n2趟)。因此外循環(huán)的循環(huán)變量i的取值是從0到n1 (不取等號！)。2) 在第i趟里怎么選？—— 第i趟要從a[i], a[i+1], ..., a[n1]中選擇最小的數(shù)，記為a[k]，i=0，1，2，...，n2。首先假設(shè)a[i]就是最小的，然后對a[i+1], ..., a[n1]每個數(shù)都判斷一下是否比當(dāng)前的最小值還要小。因此內(nèi)循環(huán)的循環(huán)變量j的取值是從i+1到n1。3) 在第i趟里怎么交換？—— 每趟選擇最終交換的是a[i]和a[k]。4) 這3種排序算法雖然簡單，但時間復(fù)雜度都比較大，雖然做了很多改進(jìn)，但仍然沒有太大成效(這些改進(jìn)沒有從本質(zhì)上降低算法時間復(fù)雜度)，在平均和最壞情況下的時間復(fù)雜度均為O(n2)。1) 說明：單純地看算法復(fù)雜度O(n2)，其實復(fù)雜度并不高，很多有效算法的時間復(fù)雜度都是O(n2)；但排序問題不同，它的規(guī)模可以達(dá)到很大，比如10000個數(shù)，這時復(fù)雜度為O(n2)的算法的時間劣勢就很明顯了。5) 直接插入和冒泡算法都有一個共同的缺點：只對相鄰的兩個記錄進(jìn)行比較和交換，因此一個記錄只能一步步地向它應(yīng)在的位置移動，效率低下。6) 選擇排序雖然不是比較和交換相鄰記錄，但是在選擇第i小的記錄時也是在剩下的記錄中逐個地進(jìn)行線性比較，它雖然比冒泡法在交換次數(shù)上有很大的改進(jìn)，但比較次數(shù)仍沒有降低，因此總體效率依舊很低。7_06 Shell排序法 算法 掌握原理 完整程序 先將序列轉(zhuǎn)化為若干小序列，在這些小序列內(nèi)進(jìn)行插入排序； 逐漸擴(kuò)大小序列的規(guī)模(即擴(kuò)大小序列中記錄的個數(shù))，而減少小序列個數(shù)，使得待排序序列逐漸處于更有序的狀態(tài)，有利于插入排序操作； 最后，所有序列都合并在原來的大序列中，這個大序列基本有序了(整個序列比較接近于正序狀態(tài))，然后再對整個序列進(jìn)行掃尾直接插入排序，從而完成排序。 然后減少記錄間的間距，從而將原始序列分成更少的子序列，分別進(jìn)行插入排序；…… 重復(fù)下去，直到最后間距減少為1，然后對整個序列進(jìn)行插入排序。: 由于Shell排序按照不斷縮小的增量來將原始序列分成若干個子序列，因此有時也稱為縮小增量排序算法。7_07 快速排序法 算法 掌握原理 完整程序(1) 從待排序序列中選擇一個記錄k作為軸值(pivot)。(2) 將剩余的記錄分割成兩個子序列L和R，L中包含所有小于或等于軸值k的記錄，R中包含所有大于軸值k的記錄。(3) 將L中的所有記錄放在k的左邊，R中的所有記錄放在k的右邊；此時k左邊的記錄都小于或等于k，k右邊的記錄都大于它，因此k正好位于正確位置。(4) 對子序列L和R進(jìn)行快速排序，直到子序列中只含有0或1個記錄。具體實現(xiàn)時，(2)、(3)可同時實現(xiàn)，即在分割的過程就將所有小于或等于軸值k的記錄放到k左邊，將大于它的記錄放到右邊。分割是快速排序算法的關(guān)鍵。7_08 歸并排序法 算法 掌握原理 完整程序17 / 17
語文相關(guān)推薦
鄂ICP備17016276號-1