課程名稱：程式設計 授課老師：________

Presentation on theme: "課程名稱：程式設計 授課老師：________"— Presentation transcript:

1 課程名稱：程式設計 授課老師：________
第 六 章 陣列 課程名稱：程式設計 授課老師：________ 2017/9/9

2 本章學習目標 1.讓讀者瞭解變數與陣列在記憶體中的表示方式。 2.說明陣列資料結構配合迴圈演算法來提高程式的執行效率。
3.說明一維、二維及多維陣列之適時時機。 2017/9/9

3 本章內容 6-1 陣列的觀念 6-2 使用陣列的好處 6-3 陣列的宣告與儲存方式 6-4 二維陣列的觀念 6-5 多維陣列的觀念
6-7 氣泡排序法(Bubble Sort) 6-8 選擇排序法（Selection Sort） 6-9 插入排序 ( Insertion Sort ) 6-10 快速排序 ( Quick Sort ) 6-11 堆積排序 ( Heap Sort ) 6-12 謝耳排序 ( Shell sort ) 6-13 合併排序 ( Merge Sort ) 6-14 基數排序 ( Radix Sort ) 6-15 搜尋(Search) 6-16 循序搜尋法 (Sequential Search) 6-17 二分搜尋法(Binary Search) 6-18 課後評量 2017/9/9

4 6-1 陣列的觀念        何謂陣列呢？陣列是指一群具有相同名稱及資料型態的變數之集合。由於整個陣列中的變數均具有相同的名稱, 因此若要存取陣列中的變數, 我們只需要透過陣列的編號(註標)來指定變數即可。 2017/9/9

5 陣列與變數的功能都是用來儲存資料，但所不同的是每一個變數只能儲存一項資料，而陣列則是由一連串的主記憶體空間組合而成，所以可以同時連續儲放多項資料，亦即一次可宣告很多個變數，而不用一個一個宣告。因此，可以少寫許多行程式，並且增加程式的可讀性及彈性。 2017/9/9

6 例如,我們需要3個整數變數來存放資料時,  我們就必須要宣告成 Dim x,y ,z as Integer, 亦即利用x, y及z三個變數來存放3個整數。問題來了，若我們今天需要50個整數變數來存放資料呢 ? 要如何為這50個變數來取名，這真是一大頭痛的問題?解決方法：利用「陣列」。 2017/9/9

7 【例如】假設我們需要10個整數變數來存放資料時，那就必須要宣告一個A陣列為整數型態，其註標是按照順序排列從0~9共有10項，其含義如下：
【說明】 (1)Dim A(9)表示宣告A陣列內共有9+1=10個陣列元素，也就是 有10個變數，分別為A(0)、A(1)、A(2)……A(9)。 (2)每一個陣列元素可以存放一筆資料。 2017/9/9

8 (3)陣列內容的存取，通常是以迴圈指令配合輸入或輸出指令來進行， 如下片段程式。
說明： 註標是以一個數字表示，註標0是代表陣列的第一個元素，註標1代表陣列的第二個元素，......，以此類推，則陣列的第n個元素則以註標n-1 代表。例如在上表中，第2個元素A(1)，其註標為1。 2017/9/9

9 6-2 使用陣列的好處 如果現在有十筆資料要用Console.Write 列印出來，我們就必須寫下列的程式： A="國立台灣大學"
B="國立清華大學" C="國立交通大學" D="國立台灣科大" E="國立高雄師大" F="國立成功大學" G="國立中興大學" H="國立中央大學" I="國立屏東科技大學" J="國立第一科技大學“ 2017/9/9

10 2017/9/9

11 (1) 利用索引值（Index）可以快速的存取資料。 (2) 一次可以處理大批的資料。 (3) 較容易表達資料處理的技巧。
以上連續寫了10次的Console.Write敘述，已經有一點累了，但是如果您想設計一個程式是想把全國的各大專院校的校名全部Console.Write的話，這下子可要挑燈夜戰，三天三夜，不能睡覺了。因此，使用陣列的優點如下： (1) 利用索引值（Index）可以快速的存取資料。 (2) 一次可以處理大批的資料。 (3) 較容易表達資料處理的技巧。 2017/9/9

12 2017/9/9

13 2017/9/9

14 6-3 陣列的宣告與儲存方式 6-3.1陣列的宣告 【語法】Dim 陣列名稱(陣列大小) As 資料型態 【說明】
6-3 陣列的宣告與儲存方式 6-3.1陣列的宣告 【語法】Dim 陣列名稱(陣列大小) As 資料型態 【說明】 (1)「陣列名稱」的命名規則和一般變數相同。 (2)「陣列大小」必須是一數字型態。 【舉例】變數宣告與陣列宣告的差異 (1) 變數宣告 宣告三個變數(A,B,C)為整數型態，如右所示： Dim A, B, C As Integer 以上三個變數只能各儲存一項資料，並且變數與變數之間都是個別 獨立的記憶體空間。 2017/9/9

15 以上所配置位置是連續的記憶體空置，可以讓我們連續儲存的多項資料，並且資料與資料之間都是按照順序排列的記憶體空間。 A陣列 A(0) A(1)
(2) 陣列宣告 宣告一個A(2)的陣列，如下所示： DIM A(2) AS Integer ‘ 宣告一維陣列A，共有A(0)、A(1)、A(2)三個元素此時，主記憶體就會即時配置3個位置，如下圖所示： 　　 以上所配置位置是連續的記憶體空置，可以讓我們連續儲存的多項資料，並且資料與資料之間都是按照順序排列的記憶體空間。 A陣列 A(0) A(1) A(2) 2017/9/9

16 6-3.2 陣列的儲存方式 當宣告完成一個陣列名稱之後便可以開始儲存資料，其方法則直接在陣列名稱之後加上“資料順序”即可。 2017/9/9

17 接下來，請依序輸入五位同學的成績到陣列中，並計算及輸出「總和」。
【實例】 如果想要記錄五位學生的成績，原來方法必需要使用五個不同變數名稱來存放成績，由於這些成績都是屬於同性質的資料，就可以宣告一個陣列名稱為A的整數陣列，共含有五個陣列元素，其寫法： Dim A(4) As Integer 接下來，請依序輸入五位同學的成績到陣列中，並計算及輸出「總和」。 2017/9/9

18 2017/9/9

19 2017/9/9

20 2017/9/9

21 牛刀小試2：承上一題實例，請依序輸入五位同學的成績到陣列中， 並計算及輸出「總合」及「平均成績」。
2017/9/9

22 6-3.3 陣列的註標觀念 在陣列中的註標，其預設值從0開始，我們不可以自行定義起始註標，但終止註標則可以自行定義。這是VB2010與VB6.0最主要的不同點。 【語法】Dim 陣列名稱(M To N) [As 資料型態] 【說明】M是起始註標，N是終止註標， N必須≧M ，其中M一定是0，不能為負值或大於0的值。 【例如】 Dim A(0 To 10) '表示範圍：0 ~ 10 '共有10+1=11項 2017/9/9

23 6-3.4 使用陣列的注意事項 雖然陣列比變數來得有彈性，但是，也要注意以下事項： 1.不能夠一次讀取或指定整個陣列的資料。
現在寫一個程式，利用A陣列來存放數字10。 (1)直覺想法：以下的方法是錯誤 不能直接指定給陣列名稱 Dim A(50) A=10 原因：想把整個陣列的資料都指定為10時，電腦會產生錯誤Error。 不能直接指定給陣列名稱 2017/9/9

24 可利用迴圈來控制，使數值10逐一的存到陣列中 Dim A(50) For x=0 To 50 A(x)=10 Next
(2)正確方法：可把程式改為如下： 可利用迴圈來控制，使數值10逐一的存到陣列中 Dim A(50) For x=0 To 50 A(x)=10 Next 可利用迴圈來控制，使數值10逐一的存到陣列中 2017/9/9

25 2.在使用多維陣列時，最多不可以超過60維陣列。 3.用來指定某一項資料的註標不能超過陣列的註標範圍。
例如：Dim A(50) '宣告一個陣列A其註標是從0~50 　　　A(-1)= '註標是 –1，超出陣列A的範圍 　　　A(51)= '註標是 51，超出陣列A的範圍 4.陣列的註標範圍是-32768~+32767，不可以是小數。 2017/9/9

26 6-3.5 陣列的初值設定 【語法】Dim 陣列名稱() As 資料型別 ={陣列初值串列} 【說明】
A(0)=1 : A(1)=2 : A(2)=3 :A(3)=4 : A(4)=5， 其寫法如下： Dim A( ) As Integer = {1,2,3,4,5} 2017/9/9

27 (2)宣告一個A(2,2)的二維整數陣列，其初值分別為： A(0,0)=1 : A(0,1)=2 : A(0,2)=3
Dim A(,) As Integer={{1,2,3},{4,5,6},{7,8,9}} 2017/9/9

28 宣告陣列時明確指定陣列大小，此時不允許在宣告陣列的同時設定初值。
【注意】 宣告陣列時明確指定陣列大小，此時不允許在宣告陣列的同時設定初值。 下面例2為錯誤的寫法。 例1. Dim A( ) As Integer={1,2,3,4,5} '正確 例2. Dim A(4) As Integer={1,2,3,4,5} '錯誤 2017/9/9

29 6-4 二維陣列的觀念 在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般的問題都可以順利的處理，但是對於比較複雜的問題時，那就必須要使用二維陣列來處理。否則會增加程式的複雜度。例如：計算4位同學的5科成績之總分與平均等問題。 【語法】Dim 陣列名稱 (M,N) AS 資料型態 【說明】M代表列數，N代表行數 2017/9/9

30 【存取方法】利用二維陣列中的兩個註標來表示。
【例如】Dim A(3,4) As Integer ' 列註標表示範圍： 0~3 共有4列 ' 行註標表示範圍： 0~4 共有5行 在宣告之後，主記憶的邏輯配置如下所示： 【存取方法】利用二維陣列中的兩個註標來表示。 行 列 第0行 第1行 第2行 第3行 第4行 第0列 Score (0,0) Score (0,1) Score (0,2) Score (0,3) Score (0,4) 第1列 Score (1,0) Score (1,1) Score (1,2) Score (1,3) Score (1,4) 第2列 Score (2,0) Score (2,1) Score (2,2) Score (2,3) Score (2,4) 第3列 Score (3,0) Score (3,1) Score (3,2) Score (3,3) Score (3,4) 2017/9/9

31 【舉例】假設老師平時記錄了學生的考試成績，並記錄在二維表格中， 如下所示：
問題一：請利用二維陣列的方式來求出「雄雄」同學的五科成績的總分 與平均成績。 【解答】 姓名 國文 英文 數學 資料庫 程式設計 張三 65 85 78 75 69 李四 66 55 52 92 47 王五 99 63 73 86 雄雄 77 88 91 100 01 02 03 04 05 06 07 08 09 10 11 12 13 14 Public Class Form1 Private Sub Button1_Click(……) Handles Button1.Click '宣告及初值設定 Dim Total, Aver As Integer Dim Score(,) As Integer = {{65, 85, 78, 75, 69}, {66, 55, 52, 92, 47}, {75, 99, 63, 73, 86}, {77, 88, 99, 91, 100}} '處理(算出總合) Total = Score(3, 0) + Score(3, 1) + Score(3, 2) + Score(3, 3) + Score(3, 4) Aver = Total / '算出平均 '輸出 MsgBox("總和=" & Total) MsgBox("平均=" & Aver) End Sub End Class 2017/9/9

32 【舉例】假設老師平時記錄了學生的考試成績，並記錄在二維表格中， 如下所示：
問題二：請利用二維陣列的方式來計算出「每一科目」的平均分數。 【解答】 姓名 國文 英文 數學 資料庫 程式設計 張三 65 85 78 75 69 李四 66 55 52 92 47 王五 99 63 73 86 雄雄 77 88 91 100 01 02 03 04 05 06 07 08 For j = 0 To '控制列數 For i = 0 To 3 '控制行數 Sum(j) = Sum(j) + Score(i, j) '計算出每一科目的總分數 Next j For j = 0 To 4 Average(j)=Sum(j) / '計算出每一科目的平均分數 Next i 2017/9/9

33 【舉例】假設老師平時記錄了學生的考試成績，並記錄在二維表格中， 如下所示：
問題三：請利用二維陣列的方式來計算出「每一位學生」平均成績。 【解答】 姓名 國文 英文 數學 資料庫 程式設計 張三 65 85 78 75 69 李四 66 55 52 92 47 王五 99 63 73 86 雄雄 77 88 91 100 01 02 03 04 05 06 07 08 For i = 0 To '控制列數 For j = 0 To 4 '控制行數 Sum(i) = Sum(i) + Score(i, j) '計算出每一位同學的總成績 Next j Next i For i = 0 To 3 Average(i)=Sum(i) / '計算出每一位同學的平均成績 2017/9/9

34 6-5 多維陣列的觀念 當陣列的維度是二維以上時，就稱為多維陣列。而其中最常見是三維陣列，其圖形為三度空間的立體圖形，並且我們可以將三維陣列視為多個二維陣列的組合。 【語法】Dim 陣列名稱 (L,M,N) AS 資料型態 【說明】L代表二維陣列個數 M代表列數 N代表行數 2017/9/9

35 【例如】Dim Score (2,3,4) As Integer ' 二維陣列的個數： 0~2 共有3個二維陣列
' 列註標表示範圍： 0~3 共有4列 ‘ 行註標表示範圍： 0~4 共有5行 【舉例】設計一個某高中，3次月考，全班4位同學的5個科目成績。 利用三維陣列來存取每位學生的成績。 Dim Score(2 , 3 , 4) As Integer 月考次數 學生人數 科目數 2017/9/9

36 【說明】此例子中Score陣列共有三個註標，故Score陣列是一個三維陣列。宣告Score是由3個(0~2)二維陣列，每個二維陣列包含4列(0~3)，5行(0~4)組合而成的整數三維陣列。並且共計有(2+1)×(3+1)×(4+1)＝60元素。如下圖所示： 2017/9/9

37 6-6 排序(Sorting) 【定義】 指將一組資料依使用者的需要予以重新安排其順序。而資料在經過排序之後，其優點為容易閱讀、利於統計分析及可以快速搜尋所要的資料等等。 在「資料結構」課程中，排序法可分為兩大類： 第一類：內部與外部排序法 第二類：穩定與不穩定排序

38 第一類：內部與外部排序法 1.內部排序法(Internal Sort)：又稱為「陣列排序」
【定義】是指要排序的資料全部都是在主記憶體(RAM)內完成。 【適用時機】資料量較少者。 【圖解】 全部一次載入 資料量較少 主記憶體

39 2.外部排序法(External Sort)：又稱為「檔案排序」
【定義】 排序的工作是在輔助記憶體內完成。由於檔案太大，使得要排序 的資料無法一次全部載入到主記憶體中，而排序進行時，須藉助 輔助記憶體存取才能完成。 【適用時機】資料量較大者。 【圖解】 無法一次載入 資料量較大 主記憶體 輔助記憶體

40 第二類：穩定與不穩定排序 1.穩定排序(Stable Sorting) 【定義】如果鍵值相同之資料在排序後的相對位置和排序前相同時，
則稱為穩定排序。 【例如】 (1)排序前：3,5,19,1,3+,10 (兩個相同鍵值3，故第二個鍵值3寫成3+) (2)排序後：1,3,3+,5,10,19 (∵兩個3的相對位置在排序前後是相同的)

41 第二類：穩定與不穩定排序 2.不穩定排序(UnStable Sorting) 【定義】如果鍵值相同之資料在排序後的相對位置和排序前是不相同
時，則稱為不穩定排序。 【例如】 (1)排序前：3,5,19,1,3+,10 (兩個相同鍵值3，故第二個鍵值3寫成3+) (2)排序後：1,3+,3,5,10,19 (∵兩個3的相對位置在排序前後是不相同)

42 各種排序的比較 排序方式 最壞時間 平均時間 穩定度 額外空間 備註說明 氣泡排序 (Bubble Sort) O( n2 ) 穩定
選擇排序 (Selection Sort) 不穩定 插入排序 (Insertion Sort) 大部份已排序者較好 薛爾排序 (Shell Sort) O( ns ) 1<s<2 O(n log2 n) s是分組 快速排序 (Quick Sort) O(n log2 n ) O( log n ) ~ O( 1 ) n大時較好 堆積排序 (Heap Sort) 合併排序 (Merge Sort) O( N ) 常用於外部排序 基數排序 (Radix Sort) O (n logr B ) O(n logbk) ~O( n ) O ( n * b ) k:箱子個數 b:基數 在上表中的各種排序法中，除了選擇、快速及堆積排序法之外，其餘都屬於穩定排序法。

43 6-7 氣泡排序法(Bubble Sort) 【定義】
是指將兩個相鄰的資料相互做比較，若比較時發現次序不對，則將兩個資料互換，並且資料依序由上往下比，而結果則會依序由下往上浮起，猶如氣泡一般。 引言：在日常生活中，我們常常會根據某些要求做簡單的排序，而在資料結構中最普遍也最簡單的應該就是 氣泡排序法。

44 【原理】 逐次比較兩個相鄰的資料，按照排序的條件交換位置，直到全部資料依序排好為止。其排序過程。如下圖所示： 比較次數為4次 由小到大 or
由大到小 【原理】 逐次比較兩個相鄰的資料，按照排序的條件交換位置，直到全部資料依序排好為止。其排序過程。如下圖所示： 首先五筆資料，分別為(3,7,1,6,8)放在陣列A0,A1,A2,A3,A4共5個位置中，假設我們的排序條件為由小到大，則 必須要判斷「左邊元素」是否大於「右邊元素」，如果是話，則必須要進行交換動作，亦即左邊元素與右邊元素 要交換位置，否則就保留在原來位置。 例如：左邊元素3與右邊元素7比較，發現左邊元素3比右邊元素7小，故保留在原來位置， 接著，左邊元素7與右邊元素1比較，發現左邊元素7比右邊元素1大，因此，左邊元素7與右邊元素1要交換位置， 所以，在上圖中，每一回合完成之後，就會找出一個最大值，例如：第一回合完成之後，找出8 比較次數為4次

45 比較次數為3次 由於我們的排序條件為由小到大，則必須要判斷「左邊元素」是否大於「右邊元素」，如果是話，
則必須要進行交換動作，亦即左邊元素與右邊元素要交換位置，否則就保留在原來位置。 在第二回合完成之後，找出7，以此類推。猶如氣泡一般，由下往上浮起。

46 比較次數為2次 比較次數為1次 由於我們的排序條件為由小到大，則必須要判斷「左邊元素」是否大於「右邊元素」，如果是話，
則必須要進行交換動作，亦即左邊元素與右邊元素要交換位置，否則就保留在原來位置。 在第二回合完成之後，找出7，以此類推。猶如氣泡一般，由下往上浮起。

47  氣泡排序法的演算法如下： 01 02 03 04 05 06 07 08 09 10 11 12 13 14 Procedure BubSort(int A[], int n) begin for (i=n-1; i>=1; i--) //排序n-1個回合 { for (j =0; j <=i-1; j++) //從第0個元素開始掃瞄 if (A[j] > A[j+1]) //判斷左邊元素是否大於右邊元素 { // A[j] 與 A[j+1]交換 Temp = A[j]; A[j] = A[j+1]; A[j+1] = Temp; } end End Procedure 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

48 請利用氣泡排序法由小至大來寫出排序的過程。 【解答】附書光碟中，檔名：ch6-7b.sln
【老師上課動態展示】檔案在附書光碟中。 輸入資料：3, 7, 9, 6, 8, 5 請利用氣泡排序法由小至大來寫出排序的過程。 【解答】附書光碟中，檔名：ch6-7b.sln 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

49 6-8 選擇排序法（Selection Sort）
【定義】 先以某一數值為基準，再由左至右掃瞄比目前大或小的數字，找到時，先記錄其位置或索引值，待確定後再進行資料的交換，而這樣的方法我們稱之為選擇排序法（Selection Sort）。 引言：在氣泡排序法中，每找到一個比目前數值大或小的數字時，就必須執行資料的交換，這樣的方法容易將時間浪費在資料的交換上。因此我們可採用改良的方式就是選擇排序法。

50 【原理】 第一回合由資料中選取最小的資料和第一個資料對調、第二回合由資料中選取第二小的資料和第二個資料對調 (因最小的資料已排到第一個位置)、依此循環直到最後一個資料，即完成資料的排序。如下圖所示： 說明：1.第一回合找出方框中的最小值。 2.將最小值與目前陣列元素互換。

51  「選擇排序法」的演算法如下： 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 Procedure SelSort(int A [], int n) Begin for (i = 0; i < n - 1; i++) //控制排序n-1個回合 { Min = i; //設定最小值索引 for (j = i + 1; j <= n; j++) //從第1個元素開始掃瞄 if (A[Min]>A[j]) //如果左邊元素大於右邊元素 Min = j; //則重新設定最小值索引 { //並進行兩個的資料交換位置 Temp = A[i]; A[i] = A[Min]; A[Min] = Temp; } End End Procedure

52 請利用選擇排序法由大至小來寫出排序的過程。 【解答】附書光碟中，檔名：ch6-8b.sln
【老師上課動態展示】檔案在附書光碟中。 輸入資料：25,57,48,37,12,92,86,33 請利用選擇排序法由大至小來寫出排序的過程。 【解答】附書光碟中，檔名：ch6-8b.sln 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

53 6-9 插入排序 ( Insertion Sort )
【定義】 是指每一次排序時都必須要往後拿一筆記錄，插入到前面已經排序好的記錄中。像是玩樸克牌一樣，我們將牌分作兩堆(第一堆為已排序，第二堆則尚未排序)，每次從第二堆牌中抽出第一張牌，然後插入到第一堆牌的適當位置。如下圖所示。

54 【原理】 是指將陣列中的元素(未排序)，逐一與已排序好的資料作比較，再將該陣列元素插入適當的位置。其排序原理如下所示：
每次從第二堆中抽出第一數字，然後插入到第一堆的適當位置。

55 請利用插入排序法由小至大來寫出排序的過程。 【解答】附書光碟中，檔名：ch6-9b.sln
【老師上課動態展示】檔案在附書光碟中。 輸入資料：25,57,48,37,12,92,86,33 請利用插入排序法由小至大來寫出排序的過程。 【解答】附書光碟中，檔名：ch6-9b.sln 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

56 6-10 快速排序 ( Quick Sort ) 【定義】
快速排序法又稱分割交換排序法，其觀念是先在資料中找到一個中間值，把小於中間值的資料放在左邊，而大於中間值的資料放在右邊，再以同樣的方式分別處理左右兩邊的資料，直到完成為止。

57 【作法】 1. 取第一個記錄的鍵值 K0 當作中間值 。 2. 由左而右，找到第一個 Ki，使得Ki≧K0。
由右而左，找到第一個Kj，使得 Kj ≦K0。 <亦即從左找比它大，從右找比它小的數字> ３. 若 i < j 則 Ki 與Kj 對調位置，並繼續執行步驟2. 否則，K0與 Kj 對調位置，此時以j為基準點將此記錄資料串列分為左右 兩部份。並以遞迴方式分別為左右兩半進行排序，直至完成排序。其排序 過程如下所示： 原始資料：26,5,37,1,61,11,59,15,48,19 K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 26 5 37 1 61 11 59 15 48 19 i=2 j=9 Ki KJ

58 其排序過程如下所示： 原始資料：26,5,37,1,61,11,59,15,48,19 從左找比K0大，從右找比K0小的數字，因為i<j所以Ki與Kj交換。因此，繼續比較下去： 因為i>j所以K0與Kj交換。並且以j=5為基準點分割成左右兩部份。 同樣的步驟，在各子集合中，將找出第一個鍵值K0 當作中間值，並且將小於K0的資料放在左半邊，而大於K0的資料放在右半邊，直到全部完成為止。 K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 26 5 37 1 61 11 59 15 48 19 i=2 j=9 K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 26 5 19 1 61 11 59 15 48 37 i=4 j=7 K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 26 5 19 1 15 11 59 61 48 37 j=5 i=6 K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 [11 5 19 1 15] 26 [59 61 48 37] K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 [1 5] 11 [19 15] 26 [59 61 48 37]

59 注意：每一回合只能處理一個子集合，其完整的排序過程如下所示：
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7 Pass 8 Pass 9 [ ] [ ] [1 5] 11 [19 15] 26 [ ] 1 [5] 11 [19 15] 26 [ ] [19 15] 26 [ ] [15] [ ] [ ] [48 37] 59 [61] [37] [61] [61] PASS1在前一頁已經有詳細說明過了，接下來進行PASS2，同樣的步驟， 在各子集合中，將找出第一個鍵值K0 當作中間值，並且將小於K0的資料放在左半邊， 而大於K0的資料放在右半邊，直到全部完成為止。

60 【老師上課動態展示】檔案在附書光碟中。 附書光碟中，檔名：ch6-10a.sln
由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

61 6-11 堆積排序 ( Heap Sort ) 【定義】 堆積排序法就是利用堆積樹的樹根與最後一個節點交換，再重新建立堆積樹，直到只剩下最後一個節點為止，排序也完成了。 堆積排序法是選擇排序法的改良版，目的是為了減少選擇排序法的比較次數。

62 【特性】 1. 堆積樹是一棵完整二元樹(Complete Binary Tree)。 2. 每一個節點之值均大於或等於它的兩個子節點之值。
由於堆積排序法就是利用堆積樹的樹根與最後一個節點交換，再重新建立堆積樹，因此，我們來說明堆積樹的特性。 在圖(A)中，它的每一個節點之值均大於或等於它的兩個子節點之值，例如：樹根80大於左子樹的40及右子樹的60 而左子樹的樹根40又大於左子樹的20及右子樹的30 而右子樹的樹根60又大於左子樹的45及右子樹的55，並且樹根80是堆積樹中最大的。因此，圖 (A)是堆積樹 但是，圖(B)違反的堆積樹特性的第二條規則，也就是每一個節點之值均大於或等於它的兩個子節點之值。 也就是，而左子樹的樹根40卻小於左子樹的70及右子樹的65。因此，圖 (B)不是堆積樹

63 【作法】 將原始資料( x1 , x2 , x3 , ... , xn )轉換成完整二元樹。如下圖所示
2. 將完整二元樹化為堆積樹 ( heap tree ) 。 3. 將樹根與最後一個節點交換。 4. 二元樹其他鍵值重複依照步驟(2)與步驟(3)的方法交換， 直到只剩下最後一個節點為止。

64 【老師上課動態展示】檔案在附書光碟中。(ch6-11.sln) 【實例】先產生10個亂數值，其範圍為10~100之間，再利用
「堆積排序法」進行排序。 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

65 6-12 謝耳排序 ( Shell sort ) 【定義】由D.L. Shell所提出，方法是插入排序法演進而來，其目的是用來減少插入排序法中元素搬移的次數，增快排序的速度。 【作法】 利用某一間隔值來分割資料，再利用插入排序法進行排序。 若有n筆資料要進行排序時，先求出初始間隔值 Gap = 3. 依照間隔值將資料分割成數個區塊。 4. 再利用插入排序法針對數個區塊內的資料進行排序 5. 最後，再縮小間隔值範圍，重複步驟3與步驟4，直到間隔值Gap=1， 排序即可完成。 [n Div 2]代表n除以2之後，取下限

66 【舉例】 請利用「謝耳排序法 」來排序以下的資料： 原始資料：5 9 6 3 4 2 1 7 8 【解答】
原始資料： 【解答】 1. 初始間隔值 Gap = =4 (1)依照間隔值將資料分割為四個部份，分別為(5,4,8)(9,2)(6,1)(3,7) (2)再利用插入排序法來排序，其結果如下：(4,5,8)(2,9)(1,6)(3,7)

67 2.再縮小間隔值Gap= =2 (1)依照間隔值將資料分割為二個部份，分別為(4,1,5,6,8)(2,3,9,7) (2)再利用插入排序法來排序，其結果如下：(1,4,5,6,8)(2,3,7,9) 3.再縮小間隔值Gap= =1，最後再利用插入排序法來排序

68 【老師上課動態展示】檔案在附書光碟中。(ch6-12.sln) 【實例】先產生10個亂數值，其範圍為10~100之間，再利用
「謝耳排序法」進行由小到大排序。 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

69 6-13 合併排序 ( Merge Sort ) 【定義】 合併排序適用於內部排序和外部排序，也是一種典型的「分而治 之」的方法。 【作法】
1. 將 N個長度為 1 的鍵值成對地合併長度為 2 的鍵值組。 2. 將 N/2個長度為 2 的鍵值成對地合併長度為 4 的鍵值組。 3. 將鍵值組成對地合併，直到合併成一組長度為 N 的鍵值組為止。 如下圖所示。 N個長度為1: 是指n筆資料 合併長度為 2 ：是指2筆資料為一組 假設我們有8筆資料，所以n代入8，則

70 【舉例】<偶數個資料> 請利用「合併排序法」由小至大來寫出以下資料之排序的過程。
原始資料：25,57,48,37,12,92,86,33 【解答】 <準備動作> [25 , 57][48 , 37][12 , 92][86 , 33] <第一回合> [25 , 57][37 , 48][12 , 92][33 , 86] <第二回合> [25 , 37 , 48 , 57][12 , 33 , 86 , 92] <第三回合> [12 , 25 , 33 , 37 , 48 , 57 , 86 , 92] 準備動作：如果資料個數為偶數時，則將 8筆資料，以成對的方式合併成2個一組的鍵值。 Pass 1: 將 2個一組的數字進行排序。亦即小的放左邊，大的放右邊。 Pass 2: 再將4個長度為 2 的鍵值成對地合併長度為 4 的鍵值組，並進行排序。亦即小的放左邊，大的放右邊。 Pass 3: 直到合併成一組長度為 8 的鍵值組為止。

71 【舉例】<奇數個資料> 請利用「合併排序法」由小至大來寫出以下資料之排序的過程。 原始資料： 37,57,32,23,15
【解答】 <準備動作> [37 , 57][32 , 23][15] <第一回合> [37 , 57][23 , 32][15] <第二回合> [23 , 32 , 37 , 57][15] <第三回合> [15 , 23 , 32 , 37 , 57] 準備動作：如果資料個數為「奇數」時，則將 7筆資料，以成對的方式將前面6筆合併成2個一組的鍵值，而第7筆則單獨一組 Pass 1: 將 2個一組的數字進行排序。亦即小的放左邊，大的放右邊。 Pass 2:再將2個長度為 2 的鍵值成對地合併長度為 4 的鍵值組，並進行排序。亦即小的放左邊，大的放右邊。 Pass 3: 最後的第5筆資料，再與前4筆已經排序好的資料進行合併，成為一組長度為 5 的鍵值組為止。

72 【老師上課動態展示】檔案在附書光碟中。(ch6-13a.sln)
由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

73 6-14 基數排序 (Radix Sort ) 【定義】
1. 先將n筆數字資料依個位數來加以「分配」，並分別放入由數字0,1,2,...9的暫存陣列Temp[10][n]中，再透過「合併」數字的順序放回原陣列。則此時的資料已依個位數大小由小到大排序。 2. 將n筆數字資料依十位數來加以「分配」 ，並分別放入由數字0,1,2,...9的暫存陣列Temp[10][n]中，再透過「合併」數字的順序放回原陣列。則此時的資料已依十位數和個位數大小由小到大排序。 3. 同理再作百位數、千位數、...即可得由小到大排序好的數字。

74 【作法】 假設R 為基底 (Base, 或稱進制)，則必須要準備 R個桶子(Bucket)，編號為 0 ~ n-1
2. 假設 D 為n筆資料中的最大鍵值之位數個數，則須執行 D 回合才能 完成排序(Sort) 工作 3. 從最低位數到最高位數，其每一回合必須要完成以下的程序： (1)分配：依位數值，將資料分配到對應的桶子(Bucket)中 (2)合併：指合併R個桶子(Bucket)中(從 0 ~ n-1)

75 【實例】將下列數字利用「基數排序法」由小至大來進行排序(Base=10) 。
原始資料：79, 8, 6, 93, 59, 84, 55, 9, 71, 33 【解答】 步驟一： Base = 10, ∴準備 10個桶子，編號為 0 ~ 9 步驟二：最大的數值是93，有二個位數， ∴D = 2，同時可知道需執行 2 個回合才會完成 Sort 工作 步驟三：從最低位數 (個位數) 開始執行各回合 1. 第一回合：把每個整數依其「個位數」為主排序 合併：71,93,33,84,55,6,8,79,59,9  2.第二回合：把每個整數依其「十位數」為主排序 (將第一回合的結果當作第二回合的輸入資料來源) 合併：6,8,9,33,55,59,71,79,84,93 個位數 1 2 3 4 5 6 7 8 9 分配資料 71 93 33 84 55 79 59 十位數 1 2 3 4 5 6 7 8 9 分配資料 33 55 59 71 79 84 93

76 【老師上課動態展示】檔案在附書光碟中。(ch6-14a.sln)
由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

77 6-15 搜尋(Search) 【定義】 就是在一群資料中找尋所要的特定資料。當資料量很龐大時， 如何快速搜尋到資料是本章所要探討的重點。
【分類】若依資料量大小來區分，搜尋可分兩類： 1.內部搜尋 2.外部搜尋

78 1.內部搜尋 【定義】欲找尋的資料量較小時，可以直接全部載入記憶體中來進行 搜尋的動作。 【適用時機】資料量較少者。 【圖解】 資料量較少
全部一次載入 主記憶體

79 2.外部搜尋 【定義】若要找尋的資料量較大時，無法一次將全部內容置於主記憶體 內，而需使用到外部的輔助記憶體來分批處理。
【適用時機】資料量較大者。 【圖解】 無法一次載入 資料量較大 主記憶體 輔助記憶體

80 資料結構課程中的「搜尋」方法 一般而言，在資料結構課程中，常見的有「循序搜尋」、「二分搜尋」、「二元樹搜尋」及「雜湊搜尋」四種搜尋方法，因此，在本章節中將依序的介紹。

81 6-16 循序搜尋法 (Sequential Search)
【定義】 從第一個資料項開始依序取出與「目的資料項(鍵值Key)」相互比較， 直到找出所要的元素或所有資料均已找完為止，這種搜尋法稱為「循 序搜尋」。 【優點】1.程式容易撰寫。 2.資料不須事先排序。 【缺點】搜尋效率較差(平均次數= )，因為不管資料順序為何，每次 都必須要從頭到尾拜訪一次。

82 【演算法】 01 02 03 04 05 06 07 08 Procedure sequential_search(int list[], int n, int key) Begin for (i = 0; i < n; i++) //從頭到尾拜訪一次 if (list[i] == key) // 比對陣列內的資料是否等於欲搜尋的條件 return i+1; // 若找到符合條件的資料，就傳回其索引 return(-1); // 若找不到符合條件的資料，就傳回 -1 End End Procedure

83 【舉例】請設計一個循序搜尋程式來找尋下列資料列，並顯示100資料項在資料列的所在位置。
輸入資料：90, 80, 40, 50, 65, 100, 10, 20,5,77 輸出結果：100在陣列中的第6筆 【解答】 題目：循序搜尋程式1 程式檔案名稱 ch6-16.sln 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 Public Class Form1 Private Sub Button1_Click(……) Handles Button1.Click Dim List() As Integer = {90, 80, 40, 50, 65, 100, 10, 20, 5, 77} Dim indata As Integer indata = Val(TextBox1.Text) Label4.Text = indata & "在陣列中的第" & Sequential_Search(List, 10, indata) & "筆." End Sub Function Sequential_Search(ByRef List() As Integer, ByVal n As Integer, ByVal key As Integer) Dim i As Integer For i = 0 To n - 1 If List(i) = key Then '比對陣列內的資料是否等於欲搜尋的條件 Return i '若找到符合條件的資料，就傳回其索引 End If Next i Return (-1) '若找不到符合條件的資料，就傳回-1 End Function End Class 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有 N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。

84 6-17 二分搜尋法(Binary Search)
【定義】 先將資料分割成兩部份，再利用「鍵值」與「中間值」來比較大小， 如果鍵值小於中間值，則可確定要找的資料在前半段的元素中，如 此分割數次直到找到為止。 【圖解】 【適用時機】事先已經排序完成。 【優點】搜尋效率較佳(平均次數=Log2N)。 【缺點】1.資料必須事先排序。 2.檔案必須是直接存取檔或隨機檔 圖解：1.首先將欲搜尋的資料，由小至大進行排序。 2.再將(第一項資料的索引 加上最後一項資料的索引值)/2之後，再取下限，即可求出中間值索引 3.因此，就可以將資料分割成兩部份，再利用「鍵值」與「中間值」來比較大小， 如果鍵值小於中間值， 則可確定要找的資料在前半段的元素中，如此分割數次直到找到為止。

85 【演算法】 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 Procedure binsearch(A[], key , low, high) Begin if(low<=high) //第一項資料的索引 值小於最後一項資料的索引值 { mid= ; //計算中間值的位置 switch compare(key, A[mid]) //「鍵值」與「中間值」比較大小 Case "=": return mid; //找到 Case “<”: return binsearch(A, key, low, mid-1) ; //遞迴呼叫找左半部 Case ">": return binsearch(A, key, mid+1, high) ; //遞迴呼叫找右半部 } Return -1; //搜尋失敗，傳回-1 End End Procedure 二分搜尋法 Low:代表第一項資料的索引 值 High:代表最後一項資料的索引值

86 【作法】 步驟 將所有資料由小至大排序。 步驟 設L(Low)表示第一項資料(最小)的索引，
H(High)表示最後一項資料(最大)的索引。 步驟 M(Middle)表示中間項的索引＝ 步驟 將「鍵值 」和「中間值」做比較。 當鍵值 ＞中間值 ，則L＝M＋1。 當鍵值 ＜中間值 ，則H＝M－1。 當鍵值 ＝中間值 ，則表示已經找到。 步驟重新計算M(中間值之索引)之後，再重複步驟和， 直到找到或所有資料均找過為止。 二分搜尋法的作法 鍵值：代表所要尋找的資料。 中間值：中間項的索引的陣列內容

87 【實例】 假設有九筆資料：8,1,99,76,88,45,15,33,24 現在我們想從資料中尋找「88」，請利用二分搜尋法來進行搜尋，並撰寫出完整的步驟。 【解答】 步驟 將所有資料由小至大排序之後，並依序存入一維陣列中。 1, 8, 15, 24, 33, 45, 76, 88, 99 步驟 設L(Low)表示第一項資料(最小) 的索引， H(High)表示最後一項資料(最大) 的索引。 已知：L=0, H=8 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99

88 步驟 計算M(Middle)表示中間值的索引＝
由於L=0, H=8，所以代入公式M= M= =4 步驟 將「鍵值」和「中間值」做比較。 假設鍵值Key=88 因為，Key=88>A[4]=33，所以 當鍵值＞中間值，所以，欲尋找的資料在右半邊， 因此，重新計算L＝M＋1=4+1=5 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 L(Low)表示第一項資料(最小)的索引， H(High)表示最後一項資料(最大)的索引。 M(Middle)表示中間項的索引 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 忽略不理 鍵值在右邊

89 步驟 重新計算M(中間值之索引)，重複步驟和， 直到找到或所有資料均找過為止。
因為，Key=88>A[6]=76，所以 當鍵值＞中間值， 所以，欲尋找的資料在右半邊， 因此，重新計算L＝M＋1=6+1=7 M= =7 因為，Key=88=A[7]，所以找尋成功。 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 忽略不理 鍵值在右邊 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 忽略不理 忽略不理 鍵值在右邊

90 【比較循序搜尋法與二分搜尋法 】 循序搜尋法 二分搜尋法 搜尋方式 按照順序尋找 從中間位置開始尋找 資料事先排序 不需要 要 最少搜尋次數
1次 最多搜尋次數 n次 Log2n 次 平均搜尋次數 (n+1)/2 次 (log2n+1)/2 次 搜尋速度 假設有1000筆資料，則平均找(1000+1)/2=500 次 假設有1000筆資料，則最多須找log21000=10 次 適用時機 資料量少 資料量大

91 【實作】 【解答】ch6-17.sln 由前一個例子，我們可以清楚得知，在氣泡排序法中，5筆資料必須要排序4回合，也就是當有
N筆資料時，則必須要排序n-1回合，因此，我們行號03就是用來控制排序n-1個回合 因此，行號03中的i變數是用來控制回合數，而行號05的j變數是用來控制掃瞄資料項的個數。