【正文】 重新對i1個元素建堆　　heap_adjust(array,0,i1)。 i 0。 i)　　heap_adjust(array,i,len)?！　or(i = (len1)/2?！　　　array[i] = rc。　　array[i] = array[j]。 array[j] array[j+1]) j++。 j 　　{　　if(j len amp?！　r間復雜度 o(nlogn)　　空間復雜度 o(1)　　比較次數(shù)：較多　　*/　　void heap_adjust(int array[],int i,int len)　　{　　int rc = array[i]?！　　　}　　/*堆排序　　算法思想：堆排序(Heap Sort)是指利用堆(heaps)這種數(shù)據(jù)結(jié)構(gòu)來構(gòu)造的一種排序算法。　　merge_sort(array,m+1,t)。　　if (s t)　　{　　m = (s + t )/2。 j++)　　array[j] = arrayDest[j]?！　or(j = iStart。k = n。 k++,i++)　　arrayDest[k] = array[i]?！　　　if (i = m)　　for (。 ++k)　　{　　if (array[i] array[j])　　arrayDest[k] = array[i++]。amp?！　or ( j = m + 1,k = i。　　int iStart = i, iEnd = n。　　}　　}　　}　　/*歸并排序　　算法思想：設(shè)兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成后將R1復制回R[low..high]中。 i++)　　{　　int j =SelectMinKey(array,i,len)。　　}　　void select_sort(int array[],int len)　　{　　for (int i = 0。 i++)　　{　　if (array[ret] array[i])　　{　　ret = i?！　or (int i = iPos?！　eturn low?！　wap(array[low],array[high])。amp?！　wap(array[low],array[high])。amp?！　　　}　　int partition(int array[],int low,int high)　　{　　int pivotkey = array[low]?！　uick_sort(array,low,pivotloc1)?！　∵f歸地解這些子問題，然后將這些子問題的解組合成為原問題的解。　　} while (inc 1)?！　o　　{　　inc = inc/2?！　rray[j+d] = tmp。amp。　　j = j d?！　 = i d。i len。　　}　　/*希爾排序　　算法思想：先將整個待排序記錄分割成若干子序列分別進行直接插入排　　序，待整個序列中的記錄基本有序時，再對全體記錄進行一　　次直接插入排序　　時間復雜度 o(n^2)　　空間復雜度 o(1)　　比較次數(shù) ?　　*/　　void shell_insert(int array[],int d,int len)　　{　　int tmp,j?！　rray[i] = arr_d[pos]。 i++)　　{　　int pos = (i + head )?！　　　}　　}　　for (int i = 0?！　　　arr_d[j1] = array[i]。j++)　　{　　if (array[i] arr_d[j])　　arr_d[j1] =arr_d[j]?！　or (j = head?！　ead =len1?！　ail += 1?！　lse　　break。j0。 i++ )　　{　　if (array[i] arr_d[0])　　{　　int j?！　or (int i = 1?！　rr_d[0] = array[0]。然后從r[2]開始依次插入到d[1]之前或之后的有序序列中?！　　　}　　if(j == 1)　　array[j+1] = tmp?！　lse　　{　　array[j+1] = tmp。j = 0。　　array[i] = array[i1]。i len?！　r間復雜度 o(n^2)　　空間復雜度 o(1)　　比較次數(shù) n(n+1)/2　　*/　　void insert_sort(int array[],int len)　　{　　int tmp,i,j。j++)　　if(array[j] array[j+1])　　swap(array[j],array[j+1])。i )　　{　　for(int j = 0?！　r間復雜度 o(n^2)　　空間復雜度 o(1)　　比較次數(shù) n(n+1)/2　　*/　　void bubble_sort(int array[],int len)　　{　　for (int i = len1 。i++ )　　{　　coutARRAY[I] p ?。 p 　　for (int i = 0 。　　b=tmp?！　mp=a。a,int amp。冒泡排序 插入排序 二路插入排序 希爾排序 快速排序 選擇排序 歸并排序 堆排序算法的C/C++實現(xiàn)　　include 　　using namespace std。有可能第n/2個父節(jié)點交換把后面一個元素交換過去了，而第n/21個父節(jié)點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。在一個長為n 的序列，堆排序的過程是從第n/2開始和其子節(jié)點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩(wěn)定性。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。當元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺；鶖?shù)排序基于分別排序，分別收集，所以其是穩(wěn)定的排序算法。依次類推，直到最高位?！　?6) 基數(shù)排序　　基數(shù)排序是按照低位先排序，然后收集。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞?沒有，合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。　　(5) 歸并排序　　歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。交換a[j]和a[center_index]，完成一趟快速排序。而右邊的j下標一直往左走，當a[j] a[center_index]。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置?！　?3) 插入排序　　插入排序是在一個已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個元素。那么，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間?！　》治鲆幌鲁Ｒ姷呐判蛩惴ǖ姆€(wěn)定性，每個都給出簡單的理由。基數(shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的?！　?/////////////////////////////////////////////穩(wěn)定性分析////////////////////////////////////////////////　　排序算法的穩(wěn)定性，通俗地講就是能保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進行關(guān)鍵字比較的，這樣得出的最終序列就是一個有序序列。　　(5)基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場合，比如撲克牌排序問題等。所以，在歸并排序中，關(guān)注最多的就是2路歸并。堆排序中的堆建立、堆調(diào)整是重要考點?！　溥x擇，是通過“錦標賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大(小)者，最終選出最小(大)數(shù)。這三種方法的不同點是，根據(jù)什么規(guī)則選取最小的數(shù)。　　(3)選擇排序可以分為：簡單選擇、樹選擇、堆排序?！　?2)交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進又可以得到快速排序。這幾種插入排序算法的最根本的不同點，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點?！　∨判蚍椒ǚ诸愑校翰迦?、選擇、交換、歸并、計數(shù)等五種排序方法?；诠１淼目疾辄c有：哈希函數(shù)的設(shè)計，沖突解決方法的選擇及沖突處理過程的描述?！　?3) 基于哈希表的查找算法：　　哈希譯自“hash”一詞，意為“散列”或“雜湊”。鍵樹特別適用于查找英文單詞的場合。 鍵樹(keywordtree)，又稱數(shù)字搜索樹(digitalsearch tree)或字符樹。　　B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸?！　《媾判驑洌喲灾?，就是“左小右大”，它的中序遍歷結(jié)果是一個遞增的有序序列。其中，尤以前兩種結(jié)構(gòu)為重，也有部分名校偏愛考B樹的。注意這三種表下的ASL值以及三種算法的實現(xiàn)。　　有序順序表——二分查找法(注意適用條件以及其遞歸實現(xiàn)方法)。在哈希表上的查找?！　∫话銓earch分為三類：在順序表上的查找。靜態(tài)查找與動態(tài)查找的含義及區(qū)別。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法，注意區(qū)分。二是求圖中每一對頂點之間的最短路徑。概念理解是比較容易的，關(guān)鍵是算法的理解。關(guān)鍵路徑問題是工程進度控制的重要方法，具有很強的實用性?！　『唵蔚卣f，最早時間是通過“從前向后”的方法求的，而最晚時間是通過“從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經(jīng)求出來之后才能進行?！　《亲钤鐣r間是什么意思、如何求?！　?. 關(guān)鍵路徑問題：　　這個問題是圖一章的難點問題。換句話說，一種是“從前向后”的排序，一種是“從后向前”排?！　】疾闀r，一般不要求寫出算法源碼，而是要求根據(jù)這兩種最小生成樹的算法思想寫出其構(gòu)造過程及最終生成的最小生成樹。在考查時，圖一章的算法設(shè)計題常常是基于這兩種基本的遍歷算法而設(shè)計的，比如：“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。在考查時，有的學校是給出一種存儲形式，要求考生用算法或手寫出與給定的結(jié)構(gòu)相對應(yīng)的該圖的另一種存儲形式。圖　　1. 圖的基本概念：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，(強)連通圖，(強)連通分量等概念。二叉樹、樹與森林之所以能有以上的對應(yīng)關(guān)系，全拜二叉鏈表所賜。 樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根(對于森林而言稱作：先序與后序遍歷)。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送分題。對于線索二叉樹，應(yīng)該掌握：線索化的實質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如：查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點就是一類?？碱})。　　(4) 線索二叉樹：　　線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解?！　?3) 可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹算法：　　求葉子個數(shù)，求二叉樹結(jié)點總數(shù)，求度為1或度為2的結(jié)點總數(shù)，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結(jié)點，刪除值為n的某個指定結(jié)點，諸如此類等等等等。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。二叉樹的遍歷算法有三種：先序，中序和后序?！　《鏄涞捻樞虼鎯投骀湵泶鎯Φ母髯詢?yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法?！　?1) 二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)　　考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹(左右子樹無序)的區(qū)別?！　≌莆諏⑾∈杈仃嚨娜M或二元組向十字鏈表進行轉(zhuǎn)換的算法?！　《嗑S數(shù)組和廣義表　　矩陣包括