HTML网页基础语言课件.ppt

《HTML网页基础语言课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章資料排序（Sorting）9-1排序的基礎9-2基本的排序法9-3分割資料的排序法9-4更多的排序法9-1排序的基礎-資料「資料」（Data）是指收集但是沒有經過整理和分析的原始數值、文字或符號，它是資訊的原始型態。電腦將資料儲存成檔案，檔案是一種有組織的資料，各種不同層次的資料組織稱為「資料階層」（DataHierarchy）。9-1排序的基礎-資料階層資料階層一共分成六個階層：最小儲存單位是位元，8個位元組成位元組，數個位元組結合成一個欄位，多個欄位組成記錄，最後將一組記錄儲存成檔案，資料庫是一組相

2、關檔案的集合，如下圖所示：9-1排序的基礎-排序的方法(說明)排序處理的資料主要是針對資料階層檔案中的記錄，依記錄的某些欄位，稱為「鍵值」（Key），以特定規則排列成遞增或遞減順序。學生連絡與成績記錄的資料可以依指定欄位的比較來重新排列記錄順序，例如：使用【成績】欄位重新排列找出成績最高的學生，可以得到最高成績90分，這種比較和重新排列記錄的工作稱為排序，成績欄位值是鍵值。換句話說，排序工作就是執行鍵值的比較和交換，以便將重新排列鍵值的順序。9-1排序的基礎-排序的方法(圖例)9-1排序的基礎-排序的方法(實

3、作)在實作上，C語言可以使用結構陣列來儲存學生資料，筆者僅以整數陣列data[]儲存學生成績的鍵值為例，如下所示：data[0]=85date[1]=77date[2]=90date[3]=65上述陣列data[]可以使用整數值比較大小來將陣列元素依遞減順序排序，排序的結果如下所示：data[0]=90date[1]=85date[2]=77date[3]=65上述陣列data[]已經排序，其大小順序如下所示：data[0]>data[1]>data[2]>data[3]9-1排序的基礎-種類排序方法依儲存媒

4、體可以分為兩種：內部排序法（InternalSorting）和外部排序法（ExternalSorting）。內部排序法是將鍵值儲存在電腦記憶體來執行排序，外部排序法因為鍵值的資料量太大無法全部儲存在記憶體，其排序的過程是使用外部儲存裝置，例如：硬碟或磁帶機儲存排序的鍵值。9-1排序的基礎-分類標準在計算機科學使用的排序演算法，其分類的標準有三種，如下所示：執行效率（ComputationalComplexity）：使用BigOh評估的執行效率，以資料量n來說，其範圍從O(nLogn)到O(n2)。記憶體的使用

5、（MemoryUsage）：排序演算法使用的電腦資源，主要是指額外記憶體空間的使用。穩定性（Stability）：如果排序演算法是一種穩定性演算法，這是指在排序後，重複鍵值的順序並不會改變，仍然保持原來順序。以C語言的結構陣列來說，如果students[5]是陳會安，students[6]是江小魚，其鍵值的成績都是77，在排序後，並不會交換陣列元素，學生陳會安仍然位在江小魚之前，而不會變成江小魚，接著陳會安。9-2基本的排序法9-2-1泡沫排序法9-2-2選擇排序法9-2-3插入排序法9-2-4謝耳排序法9-

6、2-1泡沫排序法-說明在常見的排序法中，最出名的排序法是「泡沫排序法」（BubbleSort），因為這種排序法名稱好記且簡單，將較小鍵值逐漸移到陣列開始，較大鍵值慢慢浮向陣列的最後，鍵值如同水缸的泡沫，慢慢往上浮，故稱為泡沫排序法。泡沫排序法是使用交換方式進行排序。例如：使用泡沫排序法排列樸克牌，就是將牌攤開放在桌上排成一列，將鄰接兩張牌的點數鍵值進行比較，如果兩張牌沒有照順序排列就將交換，直到牌都排到正確位置為止。9-2-1泡沫排序法-過程筆者準備使用字元陣列data[]說明排序過程，比較方式是以英文字母的

7、大小順序為鍵值，走訪一次一維陣列data[]的排序過程，如下表所示：9-2-1泡沫排序法-執行效率泡沫排序法執行效率的最差情況是陣列元素以相反順序排列，若鍵值個數是n，一共需要n-1次的外層迴圈，內層迴圈依外層迴圈遞減，次數依序為：(n-1)、(n-2)、(n-3)、……2、1，總和為n(n-1)/2次的比較和交換，可以得到泡沫排序法的執行效率為O(n2)。泡沫排序法不需要額外的記憶體空間，屬於一種穩定性的排序法，因為元素比較時，相等元素並不會交換。9-2-2選擇排序法-說明「選擇排序法」（Selection

8、Sort）是從排序的鍵值中選出最小的一個鍵值，然後和第一個鍵值交換，接著從剩下鍵值中選出第二小的鍵值和第二個鍵值交換，重覆操作直到最後一個鍵值為止。如果使用樸克牌來說明，就是將每張牌攤開放在桌子上，然後從這些牌中選出最小點數的牌放在手上，接著從桌子上剩下的牌中選擇最小的牌，將它放在手上樸克牌的最後，直到所有樸克牌都放在手上，這時手中的牌就完成排序。9-2-2選擇排序法-過程例如：字元陣列data[]