【正文】 O(log2n)。：每一趟在待排序的記錄中選出關(guān)鍵字最小的記錄，依次存放在已排序好的記錄序列的最后。 直接選擇排序：初始時，R[1..n]為無序區(qū)，R[1]為空；第一趟是在R[1..n]中選出最小的記錄與R[1]交換，R[1]為有序區(qū)；第二趟是在R[2..n]中選出最小的記錄與R[2]交換，R[1..2]為有序區(qū)。時間復(fù)雜度O(n2)，是不穩(wěn)定的。初始情況是有序區(qū)為空，無序區(qū)中R[1..n]，第一趟從R[1..n]選擇最小記錄與R[1]交換。 堆排序：是對直接選擇排序的改進，是一種樹形選擇排序?；舅枷耄涸谂判蜻^程中，將記錄數(shù)組R[1..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當前無序區(qū)中選擇關(guān)鍵字最大或最小記錄。每一趟排序：將當前無序區(qū)調(diào)整為一個大根堆，選取關(guān)鍵字最大的堆頂記錄，將他和無序區(qū)中最后一個記錄交換。堆排序是一個不斷建堆的過程。構(gòu)造堆的過程：R[1]作為二叉樹的根，R[2..n]依次逐層從左到右順序排列，構(gòu)成一棵完全二叉樹，任意結(jié)點R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R?i/2?，此稱為篩選法。從?n/2?開始。每一趟的時間復(fù)雜度是O(log2n)，整個堆排序的時間復(fù)雜度是O(nlog2n)。：首先將待排序文件看成n個長度為1的有序子文件，把這些子文件兩兩歸并，得到?n/2?個長度為2的有序子文件，然后再將他們兩兩歸并，如此反復(fù)，直到得到一個長度為n的有序文件，此稱為二路歸并排序。每一趟歸并排序的時間復(fù)雜度是O(n)，所以總的時間復(fù)雜度是O(nlog2n)。：前面方法都至少需要進行?nlogn?次比較，而分配排序?qū)r間復(fù)雜度降為O(n)。 箱排序(桶排序)：基數(shù)排序：是對箱排序的改進和推廣。箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子數(shù)目太多。每個分量可能取值的個數(shù)rd稱為基數(shù)，基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵字的類型而異。d趟箱排序?；鶖?shù)排序中，沒有進行關(guān)鍵字的比較和記錄的移動，而只是掃描鏈表和進行指針賦值，所以排序的時間主要用在修改指針上，初始化鏈表時間為O(n)。：本章除基數(shù)排序外，都是在順序表上實現(xiàn)的。時間復(fù)雜度空間復(fù)雜度穩(wěn)定性插入直接插入O(n2)O(1)穩(wěn)定希爾排序O(nlog2n)或O()O(1)不穩(wěn)定交換冒泡排序O(n2)O(1)穩(wěn)定快速排序O(nlog2n)O(log2n)不穩(wěn)定選擇直接選擇O(n2)O(1)不穩(wěn)定堆排序O(nlog2n)O(1)不穩(wěn)定歸并排序歸并排序O(nlog2n)O(n)穩(wěn)定分配排序基數(shù)排序O(d*(rd+n))rd是基數(shù)，O(rd+n)穩(wěn)定箱排序選取排序方法時需要考慮的主要因素：a、待排序的記錄個數(shù)，b、記錄本身的大小和存儲結(jié)構(gòu)，c、關(guān)鍵字的分布情況，d、對排序穩(wěn)定性的要求，e、時間和空間復(fù)雜度要等排序方法的選?。篴、若待排序的一組記錄數(shù)目n較小(如n≤50)時，可采用插入排序或選擇排序；b、n較大時，則應(yīng)采用快速排序、堆排序或歸并排序；c、若待排序記錄按關(guān)鍵字基本有序時，則宜選用直接插入排序或冒泡排序；d、當n很大，而且關(guān)鍵字位數(shù)較少時，采用鏈式基數(shù)排序較好；e、關(guān)鍵字比較次數(shù)與記錄的初始排列順序無關(guān)的排序方法是選擇排序。一般的排序方法都可以在順序結(jié)構(gòu)上實現(xiàn)，當記錄本身信息量較大時，可采用鏈式存儲結(jié)構(gòu)。插入、歸并、基數(shù)排序易于在鏈表上實現(xiàn)；快速排序和堆排序可以提取關(guān)鍵字建立索引表，然后對索引表進行排序。第八章：查找，是數(shù)據(jù)處理中經(jīng)常使用的一種重要運算。 查找也分為內(nèi)查找和外查找。 運算查找的主要操作是關(guān)鍵字的比較，因此把查找過程中的平均比較次數(shù)(也稱為平均查找長度)作為衡量算法效率優(yōu)劣的標準。：順序查找和二分查找 順序查找又稱線性查找：查找成功的平均查找長度(n+1)/2，即約為表長的一半。如果查找成功和不成功機會相等，那么平均查找長度3(n+1)/4。優(yōu)點是簡單，對表的結(jié)構(gòu)無任何要求，無論是順序存儲和鏈式存儲、無論是否有序，都同樣適用，缺點是效率低。 對于有序表來說，該算法的平均查找長度是(n+1)/2。二分查找(折半查找)：要求查找對象的線性表必須是順序存儲結(jié)構(gòu)的有序表。查找過程是遞歸的。樹中每個子樹的根節(jié)點對應(yīng)當前查找區(qū)間的中位記錄R[mid]，它的左子樹和右子樹分別對應(yīng)區(qū)間的左子表和右子表，通常將此樹稱為二叉判定樹。由于二分查找是在有序表上進行的，所以其對應(yīng)的判定樹必定是一棵二叉排序樹。二叉判定樹一定是二叉排序樹，二叉排序樹又稱為二叉查找樹。 從判定樹上可見，關(guān)鍵字比較的次數(shù)恰好為該結(jié)點在樹中的層數(shù)。因此，二分查找算法在查找成功時進行關(guān)鍵字比較的次數(shù)最多不超過判定樹的深度。查找成功時的平均查找長度 (n+1)/nlog2(n+1)1，當n很大時，可近似用log2(n+1)1表示。因為判定樹度數(shù)小于2的結(jié)點只可能在最下面的兩層，所以n個結(jié)點的判定樹的深度和n個結(jié)點的完全二叉樹的深度相同，即為?log2(n+1)??？梢?，二分查找的最壞性能和平均性能相當接近。二叉判定樹的輸出：每次以?(low+high)/2?為根建樹。(分塊查找)：是一種介于順序查找和二分查找之間的查找方法。要求分塊有序，前一塊的最大關(guān)鍵字小于后一塊的最小關(guān)鍵字，抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成索引表。 分塊查找的基本思想是：首先查找索引表，可用二分查找或順序查找，然后在確定的塊中進行順序查找。平均查找長度：二分查找log(n/s+1)+s/2， 順序查找(s2+2s+n)/2s。 順序查找缺點是n較大時，查找成功約為(n+1)/2，失敗需要比較n+1次。 二分查找成功時約為log2(n+1)1，但是他要求表以順序存儲且按關(guān)鍵字有序，適用于表不易變動且又經(jīng)常查找的情況。 分塊查找的優(yōu)點是，在表中插入或刪除一個記錄時，只要找到該記錄所屬的塊，就可以在該塊內(nèi)進行插入或刪除操作，因為塊內(nèi)記錄是無序的，所以插入或刪除比較容易，無需移動大量記錄。主要缺點是需要增加一個輔助數(shù)組的存儲空間和將初始表塊排序的運算，它也不適用于鏈式存儲結(jié)構(gòu)。 上述三種查找的時間復(fù)雜度分別是O(n)、O(log2n)和O(n的平方根)(二叉查找樹)：或者是一棵空樹，或者具有下面性質(zhì)：a、若右子樹非空，則右子樹上所有結(jié)點的值均大于根節(jié)點的值。b、若左子樹非空，則左子樹上所有結(jié)點的值均小于根節(jié)點的值。c、左右子樹本身又各是一棵二叉排序樹。 由此可得，按中序遍歷二叉排序樹所得到的遍歷序列是一個遞增有序序列。同樣一組關(guān)鍵字序列，由于其輸入順序不同，所得到的二叉排序樹也有所不同，含有n個結(jié)點的二叉排序樹不是唯一的。 構(gòu)造二叉排序樹的真正目的并不是為了排序，而是為了更好地查找，又稱為二叉查找樹。二叉排序樹的查找與給定值的比較次數(shù)不會超過樹的深度。若二叉排序樹是一顆理想的平衡樹或接近理想的平衡樹，則時間復(fù)雜度為O(log2n)，若退化為一棵單支樹，則時間復(fù)雜度為O(n)。 二叉排序樹的刪除：被刪除結(jié)點為p，其父結(jié)點為f。具體操作為：a、若p是葉子結(jié)點，直接刪除p；b、若p只有一棵子樹(左子樹或右子樹)，直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。即p是左子樹則p的子樹變?yōu)閒的左子樹；c、若p既有左子樹又有右子樹，任選一種方法：(1)、用p的直接前驅(qū)結(jié)點代替p，即從p的左子樹中選擇值最大的結(jié)點s放在p的位置(用結(jié)點s的內(nèi)容替換結(jié)點p內(nèi)容)，然后刪除結(jié)點s。s是p的左子樹中最右邊的結(jié)點且沒有右子樹；(2)、用p的直接后繼結(jié)點代替p，即從p的右子樹中選擇值最小的結(jié)點s放在p的位置(用結(jié)點s的內(nèi)容替換結(jié)點p內(nèi)容)，然后刪除結(jié)點s。s是p的右子樹中最左邊的結(jié)點且沒有左子樹。在二叉排序樹上實現(xiàn)插入和查找操作的平均時間復(fù)雜度為O(log2n)，但在最壞得情況下，會變成O(n)。平衡二叉樹：既能滿足BST性質(zhì)又能保證二叉排序樹的深度在任何情況下均為O(log2n)。 一棵m(m≥3)階的B樹，或為空樹，或為滿足下列性質(zhì)的m叉樹 a、每個結(jié)點至少包含下列信息域；b、每個結(jié)點至多有m棵子樹；c、若樹為非空，則根結(jié)點至少有1個關(guān)鍵字，至多有m1個關(guān)鍵字。因此，若根結(jié)點不是葉子，則它至少有兩顆子樹。d、每個非根結(jié)點中所含的關(guān)鍵字個數(shù)滿足：?m/2?1≤n≤m1，因為每個內(nèi)部結(jié)點的度數(shù)正好是關(guān)鍵字總數(shù)加1，所以處根結(jié)點之外的所有非終端結(jié)點至少有?m/2?棵子樹，至多有m棵子樹。在B樹上插入和刪除元素的運算比較復(fù)雜，它要求進行運算后的結(jié)點中關(guān)鍵字個數(shù)≥?m/2?1， 在B樹進行查找包括兩種基本操作：在B樹中查找結(jié)點、在結(jié)點中查找關(guān)鍵字。+樹是一種文件組織的B樹的變形樹，通常有兩個頭指針root和sqt，前者指向根結(jié)點，后者指向關(guān)鍵字最小的葉子結(jié)點。因此可對B+樹進行兩種查找運算：一種是從最小關(guān)鍵字起進行順序查找，一種是從根結(jié)點開始進行隨機查找。，是一種由關(guān)鍵字到地址的直接轉(zhuǎn)換方法。散列存儲中使用的函數(shù)稱為散列函數(shù)或哈希函數(shù)，散列地址或哈希地址，散列表或哈希表。具有相同散列地址的關(guān)鍵字稱為同義詞。沖突的頻度除了與散列函數(shù)H相關(guān)外，還與散列表的填滿程度相關(guān)。如何盡量避免沖突和沖突發(fā)生后如何解決沖突，就成了散列存儲的兩個關(guān)鍵問題。散列函數(shù)的目標是使散列地址盡可能均勻的分布在散列空間上，同時使計算盡可能簡單。直接地址法：計算簡單，并且沒有沖突。適合于關(guān)鍵字的分布基本連續(xù)的情況。數(shù)字分析法：從中提取數(shù)字分布比較均勻的若干位作為散列地址。除余數(shù)法：p最好取小于或等于表長m的最大素數(shù)。這是一種最簡單也最常用的方法。平方取中法： 折疊法：把關(guān)鍵字分割成位數(shù)相同的幾段，分為移位疊加和邊界疊加。：開放定址法和拉鏈法。開放定址法：線性探查法、二次探查法和雙重散列法(幾種方法中最好的方法)。二次探查法：d+12，d12，d+22，d22拉鏈法：存儲結(jié)構(gòu)是鏈表時常用。把具有相同散列地址的關(guān)鍵字值放在同一個單鏈表中，稱為同義詞鏈表。有m個散列地址就有m個鏈表。用拉鏈法處理沖突比開放定址法多占用一些存儲空間用作鏈表指針，但它可以減少在插入和查找過程中關(guān)鍵字的平均比較次數(shù)(平均查找長度)。，順序查找和二分查找所需要進行的關(guān)鍵字僅取決于表長，而散列表查找所需要進行的比較次數(shù)和待查結(jié)點有關(guān)。散列表查找，計算查找成功的平均查找長度時，除數(shù)是結(jié)點的個數(shù)，而在計算查找不成功的平均查找長度時，除數(shù)卻是表長。開放定址法：裝填因子α≤1。拉鏈法：α可以大于1，但一般取α≤1。 20