第六章演算法.ppt.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 【舉例】 假設我們現在有8筆資料要進行排序，分別是8,1,5,7,4,3,6,2 請利用合併排序法由小到大進行排序。 【圖解說明】 首先，每一筆資料分為一組，所以8筆資料，分為8組 第一回合：作法就是2個分為1組，並且由小到大排序。因此，分為4組 第二回合：作法就是4個分為1組，並且由小到大排序。因此，分為2組 第三回合：作法就是8個分為1組，並且由小到大排序。因此，最後就 合併成1組。亦即完成合併排序了。 6-6.7 基數排序法 (Radix Sort ) 【定義】 1.先將n筆數字資料依個位數來加以分類，並分別放入由數字0,1,2,...9 的暫存陣列Temp[10][n]中，再由數字的順序放回原陣列。則此時的 資料已依個位數大小由小到大排序。 2.將n筆數字資料依十位數來加以分類，並分別放入由數字0,1,2,...9的 暫存陣列Temp[10][n]中，再由數字的順序放回原陣列。則此時的資 料已依十位數和個位數大小由小到大排序。 3.同理再做百位數、千位數、...即可得由小到大排序好的數字。 【實例】 假設我們現在有10筆資料(Base=10)要進行排序， 分別是79, 8, 6, 93, 59, 84, 55, 9, 71, 33 請利用基數排序法由小到大進行排序。 【圖解說明】 先備知識如下： 1.由於Base = 10，因此，我們必須準備 10個桶子，編號為 0 ~ 9 2.由於10筆資料中，最大的數值是93，有二個位數，因此，我們必須 要進行2個回合才會完成排序(Sort)工作 3.在進行排序時，必須從最低位數 (個位數) 開始執行各回合 【步驟】 步驟一：把每個整數依其「個位數」為主排序 由於，我們必須將這10筆資料依「個位數」順序分配到桶子中。 因此，我們就可以得到第一回合後的結果。 第一回合的排序結果為：71,93,33,84,55,6,8,79,59,9 79, 8, 6, 93, 59, 84, 55, 9, 71, 33 步驟二：把每個整數依其「十位數」為主排序 (並且將步驟一的結果當作步驟二的輸入資料來源) 接下來，我們必須再將「第一回合的排序結果」的那10筆資料依「十位數」順序分配到桶子中。 因此，我們就可以得到第二回合後的結果。 第二回合的排序結果為：6,8,9,33,55,59,71,79,84,93 71, 93, 33, 84, 55, 6, 8, 79, 59, 9 6-7 搜尋演算法 【定義】是指在一群資料中找尋所要的特定資料。當資料量很龐大時，如何快速搜尋到資料是本章所要探討的重點。 【分類】若依資料量大小來區分，搜尋可分兩類： 1.內部搜尋：例如「二分搜尋法」與「內插搜尋法」。 2.外部搜尋：例如「循序搜尋法」。 【示意圖】 【定義】欲找尋的資料量較小時，可以直接全部載入記憶體中來進行 搜尋的動作。 【適用時機】資料量較少者。 【圖解】 一、內部搜尋 資料量較少 主記憶體 全部一次載入 【定義】若要找尋的資料量較大時，無法一次將全部內容置於主記憶體 內，而需使用到外部的輔助記憶體來分批處理。 【適用時機】資料量較大者。 【圖解】 二、外部搜尋 資料量較大 主記憶體 輔助記憶體 無法一次載入 6-7.1 循序搜尋法(Sequential Search) 【定義】 又稱為線性搜尋(Linear Search) ，它是指從第一個資料項開始依序取出與「鍵值Key」相互比較，直到找出所要的元素或所有資料均已找完為止。 【圖解說明】 【優點與缺點】 【優點】 1.程式容易撰寫。 2.資料不須事先排序。 【缺點】 搜尋效率較差(平均次數= )，因為不管資料順序為何，每次都必須要從頭到尾拜訪一次。 【演算法】 【作法】 6-7.2 二分搜尋法(Binary Search) 【定義】 先將資料分割成兩部份，再利用「鍵值」與「中間值」來比較大小， 如果鍵值小於中間值，則可確定要找的資料在前半段的元素中，如 此分割數次直到找到為止。 【圖解】 【適用時機】事先已經排序完成。 【優點】搜尋效率較佳(平均次數= )。 【缺點】1.資料必須事先排序。