【正文】 3 2 [10] [4 5 10] 20 12 3 3 [20] [4 5 10 20] 12 3 4 [12] [4 5 10 12 20] 3 5 [3] [3 4 5 10 12 20] C++語言程序設計 63 直接插入排序 ? 在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。 ? 例 911 直接插入排序函數(shù)模板（ ） 群體數(shù)據(jù)的組織 template class T void InsertionSort(T A[], int n) { int i, j。 T temp。 for (i = 1。 i n。 i++) { j = i。 temp = A[i]。 while (j 0 amp。amp。 temp A[j1]) { A[j] = A[j1]。 j。 } A[j] = temp。 } } 直接插入排序函數(shù)模板（ ） 64 C++語言程序設計 65 選擇排序的基本思想 每次從待排序序列中選擇一個關鍵字最小的元素，（當需要按關鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。 [5 4 10 20 12 3] 初始狀態(tài)： 3 [4 10 20 12 5] 3 4 [10 20 12 5] 第 i 次選擇后，將選出的那個記錄與第 i 個記錄做 交換 。 3 4 5 [20 12 10] ... ... C++語言程序設計 66 直接選擇排序 ? 在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 ? 例 912 直接選擇排序函數(shù)模板（ 9） 群體數(shù)據(jù)的組織 template class T void Swap (T amp。x, T amp。y) { T temp。 temp = x。 x = y。 y = temp。 } template class T void SelectionSort(T A[], int n) { int smallIndex。 int i, j。 for (i = 0。 i n1。 i++) { smallIndex = i。 for (j = i+1。 j n。 j++) if (A[j] A[smallIndex]) smallIndex = j。 Swap(A[i], A[smallIndex])。 } } 直接選擇排序函數(shù)模板（ ） 67 C++語言程序設計 68 交換排序的基本思想 兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。 群體數(shù)據(jù)的組織 C++語言程序設計 69 最簡單的交換排序方法 —— 起泡排序 對具有 n個元素的序列按升序進行起泡排序的步驟： – 首先將第一個元素與第二個元素進行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第 n1和第 n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第 n個位置。 – 對前 n1個元素進行第二趟起泡排序，將其中最大元素交換到第 n1個位置。 – 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對 n個元素的序列，起泡排序最多需要進行 n1趟。 群體數(shù)據(jù)的組織 C++語言程序設計 70 起泡排序舉例 對整數(shù)序列 8 5 2 4 3 按升序排序 8 5 2 4 3 5 2 4 3 8 2 4 3 5 8 2 3 4 5 8 2 3 4 5 8 初始狀態(tài) 第一趟結果 第二趟結果 第三趟結果 第四趟結果 小的逐漸上升 每趟沉下一個最大的 群體數(shù)據(jù)的組織 C++語言程序設計 71 例 913 起泡排序函數(shù)模板 template class T void Swap (T amp。x,T amp。y) { T temp。 temp = x。 x = y。 y = temp。 } template class T void BubbleSort(T A[],int n) {int i,j。 int lastExchangeIndex。 i = n1。 while (i 0) { lastExchangeIndex = 0。 for (j = 0。 j i。 j++) if (A[j+1] A[j]) { Swap(A[j],A[j+1])。 lastExchangeIndex=j。 } i=lastExchangeIndex。 } } 群體數(shù)據(jù)的組織 C++語言程序設計 72 順序查找 ? 其基本思想 – 從序列的首元素開始 ， 逐個元素與待查找的關鍵字進行比較 ， 直到找到相等的 。若整個序列中沒有與待查找關鍵字相等的元素 ， 就是查找不成功 。 ? 順序查找函數(shù)模板 – 例 914 群體數(shù)據(jù)的組織 template class T int SeqSearch(T list[],int n,T key) { for(int i=0。i n。i++) if (list[i] == key) return i。 return 1。 } 順序查找函數(shù)模板 73 C++語言程序設計 74 折半查找的基本思想 對于已按關鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。 群體數(shù)據(jù)的組織 C++語言程序設計 75 折半查找舉例 用折半查找法，在下列序列中查找值為 21的元素： L=1 5 13 19 21 37 56 64 75 80 88 92 H=11 M =INT((L+H)/2)=6 5 13 19 21 37 L=1 H=M1=5 M=INT((L+H)/2)=3 M 21 37 H L=M+1=4 L M=INT((L+H)/2)=4 M C++語言程序設計 76 例 915 折半查找函數(shù)模板 template class T int BinSearch(T list[], int n, T key) { int mid, low, high。 T midvalue。 low=0。 high=n1。 while (low = high) { mid = (low+high)/2。 midvalue = list[mid]。 if (key == midvalue) return mid。 else if (key midvalue) high = mid1。 else low = mid+1。 } return 1。 } 群體數(shù)據(jù)的組織 C++語言程序設計 77 小結與復習建議 ? 主要內容 – 模板、群體類和群體數(shù)據(jù)的組織 ? 達到的目標 – 理解模板的作用，學會簡單的應用。 – 以群體類以及查找、排序算法為綜合例題，對前面章節(jié)的內容進行全面復習； – 掌握一些常用的數(shù)據(jù)結構和算法，能夠解決一些略復雜的問題，也為下一章學習 C++標準模板庫打下基礎。 ? 實驗任務 – 實驗八