【正文】 問(wèn)的排序過(guò)程。 群體數(shù)據(jù)的組織 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 65 內(nèi)部排序方法 ? 插入排序 ? 選擇排序 ? 交換排序 群體數(shù)據(jù)的組織 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 66 插入排序的基本思想 ? 每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。 初始狀態(tài)： [5] 4 10 20 12 3 插入操作： 1 [4] [4 5] 10 20 12 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++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 67 直接插入排序 ? 在插入排序過(guò)程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡(jiǎn)單的直接插入排序算法。 ? 例 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ù)模板（ ） 68 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 69 選擇排序的基本思想 每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。 [5 4 10 20 12 3] 初始狀態(tài)： 3 [4 10 20 12 5] 3 4 [10 20 12 5] 第 i 次選擇后，將選出的那個(gè)記錄與第 i 個(gè)記錄做 交換 。 3 4 5 [20 12 10] ... ... C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 70 直接選擇排序 ? 在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡(jiǎn)單的是通過(guò)順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 ? 例 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ù)模板（ ） 71 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 72 交換排序的基本思想 兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。 群體數(shù)據(jù)的組織 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 73 最簡(jiǎn)單的交換排序方法 —— 起泡排序 對(duì)具有 n個(gè)元素的序列按升序進(jìn)行起泡排序的步驟： – 首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則將兩元素交換。然后比較第二、第三個(gè)元素，依次類推，直到第 n1和第 n個(gè)元素進(jìn)行了比較和交換。此過(guò)程稱為第一趟起泡排序。經(jīng)過(guò)第一趟，最大的元素便被交換到第 n個(gè)位置。 – 對(duì)前 n1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第 n1個(gè)位置。 – 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。對(duì) n個(gè)元素的序列，起泡排序最多需要進(jìn)行 n1趟。 群體數(shù)據(jù)的組織 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 74 起泡排序舉例 對(duì)整數(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) 第一趟結(jié)果 第二趟結(jié)果 第三趟結(jié)果 第四趟結(jié)果 小的逐漸上升 每趟沉下一個(gè)最大的 群體數(shù)據(jù)的組織 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 75 例 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++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 76 順序查找 ? 其基本思想 – 從序列的首元素開(kāi)始 ， 逐個(gè)元素與待查找的關(guān)鍵字進(jìn)行比較 ， 直到找到相等的 。若整個(gè)序列中沒(méi)有與待查找關(guān)鍵字相等的元素 ， 就是查找不成功 。 ? 順序查找函數(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ù)模板 77 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 78 折半查找的基本思想 對(duì)于已按關(guān)鍵字排序的序列，經(jīng)過(guò)一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。 群體數(shù)據(jù)的組織 C++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 79 折半查找舉例 用折半查找法，在下列序列中查找值為 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++語(yǔ)言程序設(shè)計(jì) 清華大學(xué) 鄭莉 80 例 105 折半查找函數(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ù)的組織