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