計概15-08排序與搜尋

15-8.1.1排序(Sort)

定義	將一組資料依需求予以排列順序。
優點	便於閱讀、搜尋、統計分析。
類別1	遞增(Ascending)排序	由小到大排列
	遞減(Descending)排序	由大到小排列
類別2	內部(Internal)排序	在主記憶體(RAM)進行排列，適用於少量資料。
	外部(External)排序	在輔助記憶體(Disk, File)進行排列，適用於大量資料。
類別3	穩定(Stable)排序	同值資料，排序後相對位置與排序前一樣。
	不穩定(Unstable)排序	同值資料，排序後相對位置與排序前不一樣。

 

15-8.1.2穩定排序法

氣泡(Bubble) 排序	1.自第一個元素開始，依序將所有元素與次一個元素比較，若順序不對，則互換位置。 2.比較回合數=元素數n-1 3.最多比較：n*(n-1)/2次 4.時間複雜度：最差時間與平均時間O(n2) 5.需要額外空間O(1) 6.適用於資料量小
插入(Insertion) 排序	1.將待排序元素逐一與已排序元素比較，再將元素放入適當位置。 2.時間複雜度：最差時間與平均時間O(n2) 3.需要額外空間O(1) 4.適用於大部分元素已排序
合併(Merge) 排序	1.採用分而治之(Divide and Conquer)法則 2.拆分  (1)將數列分割為兩個小數列  (2)把分好的兩個小數列，再各自分割為兩個小數列  (3)重複(2)直到每個小數列都只有一個元素 3.合併  (1)排序兩個只有一個元素的小數列，並合併  (2)把兩個排序好的小數列合併，並排序成一個數列  (3)重複(2)直到所有小數列合併成一個大數列 4.時間複雜度：最差時間與平均時間O(n log n) 5.需要額外空間O(n) 6.數列A的長度為m，數列B的長度為n，則合併兩個數列：  最少比較次數 = m或n (若將A長度改為n，則為n)  最多比較次數 = m + n - 1次 (若將A長度改為n，則為2n-1)

 

15-8.1.3不穩定排序法

快速(Quick) 排序	1.採用分而治之(Divide and Conquer)法則 2.數列中任選一個元素做為基準點(pivot)。 3.小於此元素移至基準點左邊，大於此元素移至右邊，相等的任意放。 4.基準點左邊和右邊視為兩個數列，重複上述動作，直到數列剩下一個或零個元素。 5.時間複雜度：最差時間O(n2)，平均時間O(n log n) 6.平均時間最快之內部排序法
選擇(Selection) 排序	1.流程：  (1)從未排序的數列中找出最小值。  (2)將此值取出並加入到已排序數列最後。  (3)重複以上動作，直到未排序數列全部處理完成。 2.比較回合數=元素數n-1 3.最多比較：n*(n-1)/2次 4.時間複雜度：最差時間與平均時間O(n2) 5.需要額外空間O(1) 6.適用於資料量小，效果優於氣泡排序
堆積(Heap) 排序	1.選擇排序的改良 2.將陣列轉換成最大(小)堆積。 3.重複從最大(小)堆積取出數值最大(小)節點，將根節點和最後一個節點交換，再將交換後的最後一個節點移出堆積，讓殘餘的堆積維持最大堆積性質。 4.時間複雜度：最差時間與平均時間O(n log n) 5.需要額外空間O(1)
希爾(Shell) 排序	1.插入排序法的改良 2.選定數個Gap，最後一個Gap一定要是1 3.將待排序元素依指定Gap分組，各組自行插入排序 4.時間複雜度：最差時間O(n2)，平均時間O(n log2 n) 5.需要額外空間O(1)

 

15-8.2.1搜尋(Search)

定義	在一組資料中尋找特定資料。
類別1	內部搜尋	欲搜尋之資料少，可直接載入主記憶體進行搜尋。
	外部搜尋	欲搜尋之資料多，無法一次載入主記憶體進行搜尋，需使用外部輔助記憶體分批處理。
類别2	靜態搜尋	搜尋過程中，資料表格不會有任何異動(新增、刪除、更新)。
	動態搜尋	搜尋過程中，資料表格會經常異動。

 

15-8.2.2搜尋方法

循序(Sequential) 搜尋	1.從第一個資料開始，依序逐一與目標資料比較，直到找到目標資料或所有資料均搜尋完畢為止。 2.優點：程式容易撰寫。資料不須排序。 3.缺點：每次均須從頭到尾搜尋，效率差，平均搜尋次數(n+1)/2次。 4.時間複雜度：最差時間與平均時間O(n)，最佳時間O(1)=1次。 5.適用於少量資料
二元(Binary) 搜尋	1.藉由與中間資料比較，不斷刪去資料前(後)半段，縮減搜尋範圍直到找到目標資料或無資料為止。 2.優點：搜尋效率佳。 3.缺點：資料須事先排序。資料須可直接存取或隨機檔。 4.時間複雜度：最差時間與平均時間O(log n)，最佳時間O(1)=1次。 5.適用於大量資料
二元樹(Tree) 搜尋	1.將數列建立為二元搜尋樹，任一個節點的左子樹都比父節點小，右子樹都比父節點大，且每一個節點的值都不重複。 2.優點：插入與刪除時，只須改變指標。效率高(介於循序法與二分法間)。 3.缺點：資料須事先排序。有左、右兩指標，需較大記憶體空間。 4.時間複雜度：最差時間與平均時間O(n)
內插(Interpolation) 搜尋	1.二分搜尋法的改良。 2.依照資料位置分布，運用直線斜率公式預測資料所在位置，再以二分法方式逼近。公式為(y-y1)/(x-x1)=(y2-y1)/(x2-x1) 3.優點：資料分布平均時，搜尋速度極快。 4.缺點：須計算預測公式。資料須事先排序。 5.時間複雜度：最差時間與平均時間O(n)，最佳時間O(log n)。
雜湊(Hashing) 搜尋	1.應用資料中某欄位之值代入事先設計之雜湊函數，計算資料儲存位置，應用時以資料鍵值(key value)轉換。 2.優點  (1)搜尋速度最快，資料不須事先排序。  (2)搜尋速度與資料量大小無關。  (3)在沒發生碰撞(collision)與溢位(overflow)情況下，只需一次即可讀取。  (4)保密性高，若不知雜湊函數，無法取得資料。 3.缺點  (1)浪費空間(有溢位資料區)，且儲存空間的利用率比循序檔差。  (2)有碰撞問題，當資料檔記錄到一定量時會嚴重影響處理速度存取速度。  (3)程式設計比較複雜。  (4)大量資料無效率。  (5)不適合循序型媒體(磁帶)。

 

15-8.2.3雜湊函數

15-8.2.3.1相關名詞

桶(bucket)	雜湊表中資料的儲存位置，每一位置給定一個唯一的位址(bucket address)。
槽(slot)	每一位置(桶)有多個資料儲存區(槽slot)。每一槽容納一筆紀錄。
碰撞(collision)	當不同之鍵值經雜湊函數計算後，落在相同的位址(bucket address)。
溢位(overflow)	鍵值經雜湊函數計算後，相對應之位址(bucket)已裝滿。

 

15-8.2.3.2計算方法

15-8.2.3.2.1中間平方法(mid-square)

方法	鍵值平方後，取出中間某些位元當作資料的儲存位址。
範例	鍵值k=510324，儲存空間(桶數目)為104，取四位數(0000~9999)，則雜湊函數h(k)=k2取中間四位數=260430584976取中間四位數=3058

 

15-8.2.3.2.2折疊法(folding)

方法	將鍵值分為數段，除最後一段外，其餘各段皆等長(等於儲存空間，桶數目)。再將各段相加，可得對應之位址。
範例	1.位移折疊(shifting folding)：將各段直接相加。   鍵值123203241112205 → 123,203,241,112,205 → 884 2.邊界折疊(folding at the boundaries)：將奇數段或偶數段反轉後相加。   鍵值123203241112205 → 123,203,241,112,205 → 偶反轉 → 123,302,241,211,205 →1082

 

15-8.2.3.2.3除法(division)

方法	h(X) = X mod M。位址介於0~M-1。M使用質數，避免因數消去問題。
範例	鍵值數列{X}={15,29,52,100,200}，除數M=13 h(15) = 15 mod 13 = 2 h(29) = 29 mod 13 = 3 h(52) = 52 mod 13 = 0 h(100) = 100 mod 13 = 9 h(200) = 200 mod 13 = 5

 

15-8.2.3.2.4數字分析法(digital analysis)

方法	先對資料鍵值之分布情形詳細分析，再設計雜湊位址。
範例	1.目視數字分析：利用目視將鍵值各位數分布不均的數字刪除，其餘保留為雜湊位址。 2.統計數字分析：運用統計方法分析鍵值各位數的分布情形，求出雜湊位址。

 

15-8.2.3.3解決溢位(overflow handling)的方法

15-8.2.3.3.1線性探測法(linear probing)：又稱線性開放定址(linear open addressing)

方法	將雜湊位址視為環狀空間，當溢位發生時，以線性方式找下一個空的儲存空間將資料存入。
優點	容易使用。
缺點	產生主要群集：一群資料有相近的雜湊位址，長時間執行會增加平均搜尋時間。

 

15-8.2.3.3.2鏈結串列(chaining)

方法	將碰撞之資料放到溢位資料區(overflow data area)，並用指標連結。
優點	容易使用。
缺點	需求溢位資料區，需使用指標函數。

 

15-8.2.3.3.3平方探測(quadratic probing)

方法	當h(X)位址發生溢位時，下一次探測位址為(h(X)+i2) mod b與(h(X)-i2) mod b 1≦i≦(b-1)/2，b為4j+3型式之質數。
優點	改善線性探測法的主要群集問題。

 

15-8.2.3.3.4再雜湊(rehashing)

方法	事先設計一套雜湊函數h1、h2、h3、…、hn，當溢位時先使用h1，再發生溢位則依序使用h2、h3、…、hn，直至沒溢位發生或沒雜湊函數。