【正文】 值作為增量。設有兩個哈希函數(shù)分別為 h1和 h2，則選擇的 D(i)=i h2(key)。即當?shù)刂?i發(fā)生沖突時，探測的是 i+h2(key), i+2h2(key), i+3h2(key), ? 的地址。 2．鏈地址法 鏈地址法將哈希表的每一個地址空間定義為一個單鏈表的表頭指針，這個單鏈表的表頭指針包含一個數(shù)據域和一個指針域，其中數(shù)據域用來存儲關鍵字。當發(fā)生沖突時，將所有哈希值相同的關鍵字鏈接在以該哈希地址為表頭指針的鏈表中。采用這種方法永遠不會產生溢出現(xiàn)象，因為鏈表會在新加入關鍵字后擴展。 與開放定址法相比，鏈地址法具有以下優(yōu)點。 (1)處理沖突簡單，并且不會像開放定址法那樣的堆積現(xiàn)象發(fā)生，即哈希值不同的關鍵字之間不會發(fā)生沖突。 (2)適用于無法確定長度的情況。 (3)刪除結點的操作易于實現(xiàn)。 哈希表的查找分析 ? 為了討論哈希表的平均查找長度，需要引入一個概念 —— 裝填因子，其定義如下： ? 通過裝填因子的定義，如果越小則說明表中還有很多的空單元，則發(fā)生沖突的可能性越??；如果越大則說明表越滿，則發(fā)生沖突的可能性越大，在查找時所花費的時間就越大。因此，哈希表的平均查找長度和裝填因子有關。 ? ? 表 中 的 記 錄 數(shù)哈 希 表 的 長 度第 9章 排 序 本章主要內容 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內部排序方法比較 外部排序 插入排序 直接插入排序 折半插入排序 2路插入排序 希爾排序 直接插入排序 ? 直接插入排序 (straight insertion sort)是最簡單的排序方法之一，它定義基本操作是將一個記錄插入到有序表中恰當位置，從而得到一個新的記錄數(shù)增 1的有序表。對于第一個記錄，直接放置即可，從第二個記錄開始執(zhí)行其基本操作，直到所有記錄都插入到有序表中，最后輸出有序表，則排序結束。 下面從效率方面對直接插入排序算法進行分析。 (1)從空間來看，它需要一個記錄的輔助空間用于存放監(jiān)視哨。 (2)從時間來看，排序的基本操作為比較記錄的關鍵字大小和移動記錄。 折半插入排序 ? 在直接插入排序算法中查找插入位置時，采用的是順序查找。前面講到在順序表的查找方法中折半查找要優(yōu)于順序查找方法，所以現(xiàn)在講到的折半插入排序就是用折半查找方法來代替直接插入算法中順序查找方法。 2路插入排序 ? 2路插入排序的做法是用待排序的序列的第一個記錄record[1]將排序任務分成兩部分，第一部分所有記錄比record[1]小，第二部分所有記錄都比 record[1]大。這樣將一個較大的排序任務，分解成兩個較小的排序任務，從而減少記錄的移動次數(shù)。 希爾排序 ? 希爾排序 (Shell’s sort) 又稱為縮小增量排序(diminishing increment sort)。這種插入排序較前幾種排序方法其算法時間復雜度有了較大的改進。該算法使用一個序列 ，叫做增量序列 (increment sequence)，要求 ，并且 ，當 時。 12, , , th h h1 1h? 1 jhh? ij? 交 換 排 序 冒泡排序 快速排序 冒泡排序 ? 冒泡排序算法是交換排序算法中最簡單的一種，這種算法的設計思路已經在名字上體現(xiàn)出來了：關鍵字小的記錄像水中的氣泡一樣，逐趟向上漂浮，每一趟都有關鍵字最大的記錄沉到最下面，最后得到一個排好序的序列。 快速排序 ? 快速排序 (quick sort)是已知排序算法中最快的，平均時間復雜度為 。用快速排序算法對序列 S進行排序可分成以下 4步： (1)如果 S中只有 1或者 0個元素，則返回。 (2)在 S中任意取一個元素 v，稱為樞紐元 (pivot)。 (3)將 S{v}分成兩個不相交集合： 和 。 (4)返回排序結果： 。 2( log )O n n1 { { } | }S x S v x v? ? ? ≤2 { { } | }S x S v x v? ? ? ?1{ q u ic k s o r t ( ) , , q u ic k s o r t}Sv 選 擇 排 序 直接選擇排序 樹形選擇排序 堆排序 直接選擇排序 ? 直接選擇排序算法的思路是，從序列中選擇最小的記錄放在最前面，然后從剩下的記錄中再選擇最小的記錄，排在第二的位置，依次進行，直到將所有的記錄排好序。 樹形選擇排序 ? 樹形選擇排序第一趟對待排列序列中 n個記錄兩兩比較，取較小者，得到一個長度為序列；第二趟在個較小的記錄中再進行比較；依次類推，直到得到最小的記錄。這樣一個過程可以看成一棵樹的構建過程。 堆排序 ? 堆又稱為優(yōu)先隊列，它是至少提供這樣兩組操作的數(shù)據結構：插入 (insert)和刪除最小者 (DeleteMin)。 ? 堆排序的步驟如下： (1)將待排序記錄構造成堆結構。 (2)用堆的 DeleteMin操作獲取最小元素，從堆結構中將其刪去，并將剩余部分調整成堆結構。 (3)重復第 (2)步，直到將所有記錄排好序。 歸 并 排 序 ? 該算法內容就是使用歸并的方法來完成排序，其中歸并操作也是該算法最重要的操作。 ? 歸并操作就是將兩個排好序的序列合并成一個有序的序列。 基 數(shù) 排 序 對于序列 {R1, R2, ?, Rn}。每一個記錄 Ri含有 d個關鍵字( )，如果序列是關于 (k0, k1, ?, kd1)有序的，則對任意 Rp和 Rq(1≤ pq≤ n)，滿足關系式： ( )( ) 其中， k0為最高位關鍵字； kd1為最低位關鍵字。 0 1 1, , , di i ik k k ?0 1 1, , , dp p pk k k ? 0 1 1, , , dq q qk k k ? 各種內部排序方法比較 ? 時間復雜度為 O(n2)的算法有直接插入排序、折半插入排序、二路插入排序、直接選擇排序和冒泡排序，這些排序算法的實現(xiàn)都比較簡單。 ? 時間復雜度為 O(nlog2n)的算法有樹形選擇排序、希爾排序、快速排序、堆排序和歸并排序，這些算法的實現(xiàn)都比較復雜，其中希爾排序中序列的選擇比較繁瑣，快速排序關鍵字的選擇也是難點，堆排序則需要維持一個堆，歸并排序的輔助空間要求比較多。 ? 時間復雜度為 O(n)的排序算法有桶排序和基數(shù)排序。 根據排序算法的穩(wěn)定性，可以將排序算法歸類為以下兩種。 ? (1) 穩(wěn)定的排序算法有直接插入排序、冒泡排序、歸并排序、桶排序和基數(shù)排序。 ? (2) 不穩(wěn)定的排序算法有折半插入排序、二路插入排序、直接選擇排序、樹形選擇排序、希爾排序、堆排序和快速排序。 根據排序算法的復雜性，可以將排序算法歸類為以下兩類。 ? (1) 簡單的排序算法，包括直接插入排序、折半插入排序、二路插入排序、冒泡排序、直接選擇排序和桶排序。 ? (2) 較復雜的排序算法，包括樹形選擇排序、希爾排序、快速排序、堆排序、歸并排序和基數(shù)排序。 一般情況下需要綜合考慮以下幾個因素來選擇合適的排序算法。 ? 對穩(wěn)定性的要求。 ? 問題的規(guī)模，也就是待排序的記錄個數(shù)。 ? 關鍵字的初始狀態(tài)。 ? 對時間和輔助空間的要求。 ? 每一記錄的大小。 在選擇排序算法時遵循以下原則： ? 首先考慮對穩(wěn)定性的要求，如果要求穩(wěn)定，則只能從穩(wěn)定的排序算法中選取，否則可以在所有的排序算法中選取。 ? 其次考慮問題的規(guī)模，如果規(guī)模較大，則選擇平均算法復雜度較好的算法，否則選擇實現(xiàn)較簡單的算法。 ? 第三要考慮初始序列是否為基本有序，如果基本有序則考慮選用在基本有序情況下表現(xiàn)較好的算法，如直接插入排序、冒泡排序或隨機的快速排序。 ? 第四考慮對時間以及輔助空間的要求，如果對輔助空間的要求比較高，則不能選擇空間復雜度較高的算法。 外 部 排 序 選擇外部排序的理由 簡單外部排序算法 多路合并排序 替換 選擇排序 選擇外部排序的理由 ? 外部排序算法比內部排序算法要更依賴于存儲設備。為了更好地說明問題，采用最受限制的存儲介質 —— 磁帶來討論外部排序算法。所需要說明的是，假設至少有 3個磁帶驅動器進行排序工作，其中兩個磁帶進行排序，第三個磁帶進行簡化工作。如果只用一個磁帶進行排序，則任何排序算法訪問磁帶的時間復雜度為 O(N2)。 簡單外部排序算法 ? 簡單排序算法的步驟如下： (1)從磁帶 Ta1上一次性讀取 M個數(shù)據。 (2)在內存中將這 M個數(shù)據進行排序，然后再把這些數(shù)據交替寫到 Tb1上。然后重復第 (1)步，再將得到的 M個已排序的數(shù)據寫到 Tb1上，就這樣交替地寫，直到將磁帶 Ta1上的數(shù)據全部輸出到磁帶 Tb1和Tb2上。 (3)將 Tb1和 Tb2上取下一個順串，并將二者合并，形成一個 2倍長的順串，將結果寫在磁帶 Ta1上。 (4)重復步驟 (3)，交替地將新生成的順串寫在磁帶 Ta1和 Ta2上， 直到 Tb1和 Tb2為空，或者還剩下一個順串。 (5)將 4盤磁帶的磁頭移至開始，并重復步驟 (2)～ (4)，直到得到一個長度為 N的順串。 多路合并排序 k路合并算法也和二路合并算法一樣，采用相同的方式進行排序。但是有一點是不同的， k路合并算法中將已排序的順串進行合并時，過程稍微復雜一些。這里采用優(yōu)先隊列找出待合并順串的最小元素。其主要步驟如下。 ? 假設有 k個順串需要合并。 (1)首先將這 k個順串的第一個元素存入優(yōu)先隊列 Q中。 (2)采用 DeleteMin求出下一個需要寫在磁帶上的元素，并將此元素寫到磁帶上。 (3)將最小元素所在的磁帶的磁頭向前推進，如果此磁帶上仍有元素，則將此元素插入到優(yōu)先隊列中。 (4)重復步驟 (2)～ (3)，直到所有的順串均輸出到磁帶上。 替換 選擇排序 替換 選擇算法的步驟如下。 假設內存一次可以存儲 M條記錄。 (1)將 K(K≤ M，這是由于下面需要用一個死區(qū) (dead space)。這個死區(qū)可以由內存分配，也可以是一個磁帶 )個記錄一次存入一個優(yōu)先隊列中。 (2)執(zhí)行 DeleteMin將最小的記錄寫到輸出磁帶上，再從輸入磁帶上讀入下一個記錄。 (3)如果新讀入的記錄比剛輸出的記錄大，則把此元素添加到輸出隊列中；否則不能把它放入當前的順串中，而是將這個元素存儲在優(yōu)先隊列的死區(qū)。 (4)重復步驟 (2)～ (3)，直到優(yōu)先隊列的大小為零，這樣一個順串就構造完畢。 (5)如果死區(qū)中存在元素，則取出其中的元素，將這些元素作為下一個順串的開始。重復步驟 (2)～ (4)，直到所有的順串構造完畢。