1、第九章第九章 群體類群體類和群體數據的組織和群體數據的組織1本章主要內容本章主要內容l函數模板函數模板l類模板類模板lString類類l群體類群體類l群體數據的組織群體數據的組織第九章第九章 群體類群體類和群體數據的組織和群體數據的組織29.0 函數模板函數模板 函數模板可以用來創建一個通用功能的函數，函數模板可以用來創建一個通用功能的函數，以支持多種不同形參，進一步簡化重載函數的函以支持多種不同形參，進一步簡化重載函數的函數體設計。數體設計。聲明方法：聲明方法：template 函數聲明函數聲明 函 數 模 板第九章第九章 群體類群體類和群體數據的組織和群體數據的組織3模板參數表模板參數表模

2、板參數表由用逗號分隔的模板參數構成，可以包括以下形式內模板參數表由用逗號分隔的模板參數構成，可以包括以下形式內容：容：1typename/class 標識符標識符 如如typename T,指明可以接收一個類型參數。這些類型參數代指明可以接收一個類型參數。這些類型參數代表的是類型，可以是內部類型或者自定義類型。表的是類型，可以是內部類型或者自定義類型。2類型說明符類型說明符 標志符標志符如如 int val，指明可以接收一個由類型說明符所規定類型的常，指明可以接收一個由類型說明符所規定類型的常量作為參數。量作為參數。3template class 標志符標志符如如templateclass C

3、ontainer指明可以接收一個指明可以接收一個類模板作為參數。類模板作為參數。第九章第九章 群體類群體類和群體數據的組織和群體數據的組織4求絕對值函數的模板求絕對值函數的模板#includeusing namespace std;templateT abs(T x) return x0?-x:x; void main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl;運行結果：運行結果：55.5第九章第九章 群體類群體類和群體數據的組織和群體數據的組織5求絕對值函數的模板分析求絕對值函數的模板分析編譯器從調用編譯器從調用abs

4、()時實參的類型，推導出函時實參的類型，推導出函數模板的類型參數。例如，對于調用表達數模板的類型參數。例如，對于調用表達式式abs(n)，由于實參，由于實參n為為int型，所以推導型，所以推導出模板中類型參數出模板中類型參數T為為int。當類型參數的含義確定后，編譯器將以函數當類型參數的含義確定后，編譯器將以函數模板為樣板，生成一個函數：模板為樣板，生成一個函數：int abs(int x) return x0?-x:x; 第九章第九章 群體類群體類和群體數據的組織和群體數據的組織6 類模板用于設計一個通用類，使這個類的數據成員的類類模板用于設計一個通用類，使這個類的數據成員的類型、成員函數的

5、參數能夠按照需要進行改變即參數化）型、成員函數的參數能夠按照需要進行改變即參數化）聲明類模板的一般形式為：聲明類模板的一般形式為： template class class_name其中，其中，Ttype是一個標識符，代表所聲明的類模板中參數是一個標識符，代表所聲明的類模板中參數化的類型名。留意：模板類的成員函數必須是函數模板?；念愋兔?。留意：模板類的成員函數必須是函數模板。 定義了類模板以后，就可以創建這個類的實例：定義了類模板以后，就可以創建這個類的實例：Class_name 對象對象1，對象，對象n；type用具體的數據類型代入，系統根據代入的數據類型生用具體的數據類型代入，系統根據代

6、入的數據類型生成所需的類，并創建該類的對象。成所需的類，并創建該類的對象。9.1 類模板類模板第九章第九章 群體類群體類和群體數據的組織和群體數據的組織7/EX9_1.cpp : 演示類模板的定義和使用演示類模板的定義和使用#include #include struct student/聲明一個結構體類型聲明一個結構體類型 int id ; int score ; ;template/聲明一個類模板聲明一個類模板class buffer /實現對任意類型數據的存取實現對任意類型數據的存取 private: T a ; int empty ; public: buffer( void ) ;/

7、聲明聲明buffer類的構造函數類的構造函數 T get( void ) ; void put( T x) ;第九章第九章 群體類群體類和群體數據的組織和群體數據的組織8template/定義定義buffer類的構造函數模板類的構造函數模板buffer:buffer( void ):empty(0) template/定義成員函數定義成員函數get模板模板T buffer:get(void) if (empty=0) coutthe buffer is empty!endl; exit(1); return a;template/定義成員函數定義成員函數put模板模板void buffer:p

8、ut(T x) empty+; a = x;第九章第九章 群體類群體類和群體數據的組織和群體數據的組織9void main(void) student s = 1022, 78 ; buffer i1, i2 ;/聲明整型對象聲明整型對象i1, i2 buffer stu1 ;/聲明結構體對象聲明結構體對象stu1 buffer d ;/聲明雙精度對象聲明雙精度對象d i1.put(13) ;/對象對象i1調用調用put執行了執行了empty+ i2.put(-101) ;/對象對象i2調用調用put執行了執行了empty+ couti1.get( ) i2.get( ) endl ; stu

9、1.put( s ) ;/對象對象stu1調用調用put執行了執行了empty+ coutthe students id is stu1.get( ).idendl ; coutthe students score is stu1.get( ).scoreendl ; coutd.get( )、+等等) 對字符串進行賦值、銜接、復制、查找、交換對字符串進行賦值、銜接、復制、查找、交換等。等。 基本形式為基本形式為 . string類類第九章第九章 群體類群體類和群體數據的組織和群體數據的組織12/EX9_2.cpp : 演示演示string類的應用類的應用#include #include u

10、sing namespace std ;void main( ) string s1(Hello), s2, s3, s4 ;/定義定義string對象對象 s2 = s1 ; /用用=號進行賦值號進行賦值(重載運算符重載運算符=) s3.assign(s1); /調用成員函數調用成員函數assign( )進行賦值進行賦值 couts1=s1.data( ), s2=s2.data( ) , s3=s3.data( )endl ; couts1的長度的長度=s1.length( )endl; /輸出字符串長輸出字符串長度度 char a =China!, b6 ; s1 = a ;/strin

11、g對象對象s1接收字符數組接收字符數組a的賦值的賦值 couts1=s1.data( )endl ; for( int i=0; i5; i+ ) bi = s2i ;/b5= 0; cout字符數組字符數組b= bendl ; /字符串的連接字符串的連接 s4=s2+ +s1; /用用+進行字符串的連接進行字符串的連接(重載運算符重載運算符+)s3=s2.append( s1 ) ; /s2與與s1連接并賦給連接并賦給s3，注意連接后的，注意連接后的s2結果結果第九章第九章 群體類群體類和群體數據的組織和群體數據的組織13couts2=s2.data( ), s3=s3.data( ), s

12、4= s4.data( )endl ; int f=pare( 6, 5, s4, 7, 5 ) ;/將將s3的第的第6個開始的個開始的5個字符與個字符與/s4的第的第7個開始的個開始的5個字符進行比較個字符進行比較 if ( f=0 ) couts3與與s4比較的部分相等比較的部分相等n; else couts3與與s4比較的部分不相等比較的部分不相等n; /取子字符串操作取子字符串操作 string sz=s2.substr( 5, 5 ) ; /取取s2的第的第5個開始的個開始的5個字符個字符 cout子字符串子字符串sz=sz.data( )endl ; s1.swap(s4) ;/交

13、換交換s1與與s4 couts1=s1.data(), s4=s4.data()endl ; cout字符串字符串China在在s1中的位置為：中的位置為： s1.find(China)endl; int len=s1.length( ) ; char *pt=new charlen+1 ; /定義字符型指針并動態分配空間定義字符型指針并動態分配空間 s1.copy(pt,len,0) ; /將將s1復制到復制到pt所指的數組，從所指的數組，從s10處開始復制處開始復制len個個字符字符 ptlen= 0 ; coutptendl ; s2 = pt ; /string類對象類對象s2接收字符

14、型指針的賦值接收字符型指針的賦值 couts2.data( )endl ;第九章第九章 群體類群體類和群體數據的組織和群體數據的組織14程序運行結果為程序運行結果為:s1=Hello, s2=Hello, s3=Hellos1的長度的長度=5s1=China!字符數組字符數組b= Hellos2=HelloChina!, s3=HelloChina!, s4=Hello China!s3與與s4比較的部分相等比較的部分相等 子字符串子字符串sz=Chinas1=Hello China!, s4=China!字符串字符串China在在s1中的位置為中的位置為: 6Hello China!Hell

15、o China!第九章第九章 群體類群體類和群體數據的組織和群體數據的組織9.2 群體數據群體數據群體的概念群體的概念群體是指由多個數據元素組成的集合體。群體可群體是指由多個數據元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。以分為兩個大類：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區分為線性群體中的元素按位置排列有序，可以區分為第一個元素、第二個元素等。第一個元素、第二個元素等。非線性群體不用位置順序來標識元素。非線性群體不用位置順序來標識元素。第一個元素第二個元素第三個元素最后一個元素第九章第九章 群體類群體類和群體數據的組織和群體數據的組織169.2.1 線

16、性群體的概念線性群體的概念 線性群體中的元素次序與其位置關系是對應的。線性群體中的元素次序與其位置關系是對應的。在線性群體中，又可按照訪問元素的不同方法分為直在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。接訪問、順序訪問和索引訪問。9.2.2 直接訪問群體直接訪問群體數組數組 靜態數組是具有固定元素個數的群體，其中的元靜態數組是具有固定元素個數的群體，其中的元素可以通過下標直接訪問。缺陷：大小在編譯時就已素可以通過下標直接訪問。缺陷：大小在編譯時就已經確定，在運行時無法修改。經確定，在運行時無法修改。 動態數組由一系列位置連續的，任意數量相同類動態數組由一系列位置連

17、續的，任意數量相同類型的元素組成。優點：其元素個數可在程序運行時改型的元素組成。優點：其元素個數可在程序運行時改變。動態數組類模板舉例參見變。動態數組類模板舉例參見P293301第九章第九章 群體類群體類和群體數據的組織和群體數據的組織17#ifndef ARRAY_CLASS#define ARRAY_CLASSusing namespace std;#include #include #ifndef NULLconst int NULL = 0;#endif / NULLenum ErrorType invalidArraySize, memoryAllocationError, inde

18、xOutOfRange ;char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;動態數組類模板程序17第九章第九章 群體類群體類和群體數據的組織和群體數據的組織18template class Array private: T* alist; int size; void Error(ErrorType error) const; public: Array(int sz = 50); Array(const Array& A); Array(void); Array& ope

19、rator= (const Array& rhs); T& operator(int i); operator T* (void) const; int ListSize(void) const; void Resize(int sz); ;#endif18第九章第九章 群體類群體類和群體數據的組織和群體數據的組織1919數組類模板的構造函數數組類模板的構造函數/ 構造函數構造函數template Array:Array(int sz) if (sz = 0) /sz為數組大小元素個數），若小于為數組大小元素個數），若小于0，則輸出錯誤信息，則輸出錯誤信息 Error(inva

20、lidArraySize); size = sz; / 將元素個數賦值給變量將元素個數賦值給變量size alist = new Tsize; /動態分配動態分配size個個T類型的元素空間類型的元素空間 if (alist = NULL) /如果分配內存不成功，輸出錯誤信息如果分配內存不成功，輸出錯誤信息 Error(memoryAllocationError);直接訪問的線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2020數組類的拷貝構造函數數組類的拷貝構造函數template Array:Array(const Array& X) int n = X.siz

21、e; size = n; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); T* srcptr = X.alist; / X.alist是對象是對象X的數組首地址的數組首地址 T* destptr = alist; / alist是本對象中的數組首地址是本對象中的數組首地址 while (n-) / 逐個復制數組元素逐個復制數組元素 *destptr+ = *srcptr+;直接訪問的線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2121淺拷貝淺拷貝 alist sizeAA的數組元素占用的內存拷

22、貝前 alist sizeAA的數組元素占用的內存拷貝后 alist sizeBvoid main(void) Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2222深拷貝深拷貝 alist sizeAA的數組元素占用的內存拷貝前 alist sizeAA的數組元素占用的內存拷貝后 alist sizeBB的數組元素占用的內存第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2

23、323數組類的重載數組類的重載=運算符函數運算符函數template Array& Array:operator= (const Array& rhs) int n = rhs.size; if (size != n) delete alist; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); size = n; T* destptr = alist; T* srcptr = rhs.alist; while (n-) *destptr+ = *srcptr+; return *this;直接訪問的

24、線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織24錯誤報告函數錯誤報告函數template void Array: Error(ErrorType error) const cout errorMsgerror endl; throw error;第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2525數組類的重載下標操作符函數數組類的重載下標操作符函數template T& Array:operator (int n) / 檢查下標是否越界檢查下標是否越界 if (n size-1) Error(indexOutOfRange,n); / 返回下標為返回

25、下標為n的數組元素的數組元素 return alistn;直接訪問的線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2626為什么有的函數返回引用為什么有的函數返回引用如果一個函數的返回值是一個對象的值，它如果一個函數的返回值是一個對象的值，它就被認為是一個常量，不能成為左值。就被認為是一個常量，不能成為左值。如果返回值為引用。由于引用是對象的別名，如果返回值為引用。由于引用是對象的別名，所以通過引用當然可以改變對象的值。所以通過引用當然可以改變對象的值。直接訪問的線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2727重載指針轉換操作符重載指針轉換操作符t

26、emplate Array:operator T* (void) const / 返回當前對象中私有數組的首地址返回當前對象中私有數組的首地址 return alist;直接訪問的線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織28指針轉換運算符的作用指針轉換運算符的作用#include using namespace std;void main() int a10; void read(int *p, int n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;void main() Array a(10);

27、 void read(int *p, n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;直接訪問的線性群體右邊右邊read(a, 10);中中a是是Array類型對象，編譯類型對象，編譯器會為其尋找一個可以將其器會為其尋找一個可以將其轉換為轉換為int指針的函數或規則指針的函數或規則，試圖執行，試圖執行(int *)a,，以匹配，以匹配void read(int *p, int n)函數函數，若找不到，則編譯出錯，若找不到，則編譯出錯，由于類中重載了指針轉換符由于類中重載了指針轉換符，因此，因此 (int *)a 將得到將得到

28、a中數中數組指針，匹配成功。組指針，匹配成功。第九章第九章 群體類群體類和群體數據的組織和群體數據的組織2929Array類的應用類的應用例例9-4求范圍求范圍2N中的質數，中的質數，N在程序運行時由鍵盤輸入。在程序運行時由鍵盤輸入。直接訪問的線性群體第九章第九章 群體類群體類和群體數據的組織和群體數據的組織30void main(void) Array A(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: ; cin n; Aprimecount+ = 2; / 2是一個質數是一個

29、質數 for(i = 3; i n; i+) if (primecount = A.ListSize() A.Resize(primecount + 10); if (i % 2 = 0) continue; j = 3; while (j i/2) Aprimecount+ = i; for (i = 0; i primecount; i+) cout setw(5) Ai; if (i+1) % 10 = 0) cout endl; 30第九章第九章 群體類群體類和群體數據的組織和群體數據的組織319.2.3 順序訪問群體順序訪問群體鏈表鏈表 鏈表是一種動態數據結構，可以用來表示順序訪鏈表

30、是一種動態數據結構，可以用來表示順序訪問的線性群體。問的線性群體。 鏈表是由系列結點組成的，結點可以在運行時動鏈表是由系列結點組成的，結點可以在運行時動態生成。態生成。 每一個結點包括數據域和指向鏈表中下一個結點每一個結點包括數據域和指向鏈表中下一個結點的指針即下一個結點的地址）。如果鏈表每個結點的指針即下一個結點的地址）。如果鏈表每個結點中只有一個指向后繼結點的指針，則該鏈表稱為單鏈中只有一個指向后繼結點的指針，則該鏈表稱為單鏈表。表。 鏈表模板和應用舉例參見鏈表模板和應用舉例參見P302307第九章第九章 群體類群體類和群體數據的組織和群體數據的組織329.2.4 特殊的線性群體特殊的線性

31、群體棧棧棧是只能從一端訪問的線性群體，可以訪問的這一棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。端稱棧頂，另一端稱棧底。ana2a1入棧出棧棧頂棧底第九章第九章 群體類群體類和群體數據的組織和群體數據的組織331. 棧的應用舉例棧的應用舉例函數調用函數調用main調fun(參數)終了fun(參數)前往參數當前現場返回地址入棧當前現場返回地址出棧參數出棧當前現場 返回地址第九章第九章 群體類群體類和群體數據的組織和群體數據的組織342. 棧的基本狀態棧的基本狀態?？眨簵？眨簵Ｖ袥]有元素棧中沒有元素棧滿：棧滿：棧中元素個數達到上限棧中元素個數達到上限一般狀態：棧中有元素，但

32、未達到棧滿狀態一般狀態：棧中有元素，但未達到棧滿狀態第九章第九章 群體類群體類和群體數據的組織和群體數據的組織棧頂ana1a0入棧出棧數組下標maxn10一般狀態棧頂入棧出棧數組下標初始狀態棧空）maxn10棧頂amaxana1a0入棧出棧數組下標maxn10棧滿狀態35第九章第九章 群體類群體類和群體數據的組織和群體數據的組織3. 棧的基本操作棧的基本操作初始化初始化入棧入棧出棧出棧清空棧清空棧訪問棧頂元素訪問棧頂元素檢測棧的狀態滿、空）檢測棧的狀態滿、空）棧類模板和應用舉例參見棧類模板和應用舉例參見P307313第九章第九章 群體類群體類和群體數據的組織和群體數據的組織379.2.5 特殊

33、的線性群體特殊的線性群體隊列隊列隊列是只能向一端添加元素，從另一端刪除元素隊列是只能向一端添加元素，從另一端刪除元素的線性群體的線性群體a1 a2an-1 an隊頭隊尾入隊出隊a0第九章第九章 群體類群體類和群體數據的組織和群體數據的組織381. 隊列的基本狀態隊列的基本狀態隊空：隊空：隊列中沒有元素隊列中沒有元素隊滿：隊滿：隊列中元素個數達到上限隊列中元素個數達到上限一般狀態：隊列中有元素，但未達到隊滿狀態一般狀態：隊列中有元素，但未達到隊滿狀態第九章第九章 群體類群體類和群體數據的組織和群體數據的組織a0 a1an-1 an隊頭隊尾入隊出隊數組下標 0 1 n-1 n max(一般狀態)元

34、素移動方向隊頭隊尾入隊出隊數組下標 0 1 n-1 n max(隊空狀態) a0 a1 an-1 an amax隊頭隊尾入隊出隊數組下標 0 1 n-1 n max(隊滿狀態)元素移動方向第九章第九章 群體類群體類和群體數據的組織和群體數據的組織402. 循環隊列循環隊列 在想象中將數組彎曲成環形，元素出隊時，后在想象中將數組彎曲成環形，元素出隊時，后繼元素不移動，每當隊尾達到數組最后一個元素時繼元素不移動，每當隊尾達到數組最后一個元素時，便再回到數組開頭。，便再回到數組開頭。隊列類模板參見隊列類模板參見P313316第九章第九章 群體類群體類和群體數據的組織和群體數據的組織1234m-1m-

35、2m-30amam+1am+2a3隊頭隊尾a4am-2am-3am-1隊滿狀態 元素個數=m1234m-1m-2m-30隊尾隊頭隊空狀態 元素個數=0隊尾1234m-1m-2m-30a0a1a2a3隊頭一般狀態第九章第九章 群體類群體類和群體數據的組織和群體數據的組織429.3 群體數據的組織群體數據的組織l插入排序插入排序l選擇排序選擇排序l交換排序交換排序l順序查找順序查找l折半查找折半查找第九章第九章 群體類群體類和群體數據的組織和群體數據的組織43排序排序sorting） 排序是計算機程序設計中的一種重要操作，它的排序是計算機程序設計中的一種重要操作，它的功能是將一個數據元素的任意序列

36、，重新排列成一個按功能是將一個數據元素的任意序列，重新排列成一個按關鍵字有序的序列。關鍵字有序的序列。數據元素：數據元素： 數據的基本單位。在計算機中通常作為一個整體數據的基本單位。在計算機中通常作為一個整體進行考慮。一個數據元素可由若干數據項組成。進行考慮。一個數據元素可由若干數據項組成。關鍵字：關鍵字： 數據元素中某個數據項的值，用它可以標識識數據元素中某個數據項的值，用它可以標識識別一個數據元素。別一個數據元素。 在排序過程中需要完成兩種基本操作：在排序過程中需要完成兩種基本操作：比較兩個數的大小比較兩個數的大小調整元素在序列中的位置調整元素在序列中的位置第九章第九章 群體類群體類和群體

37、數據的組織和群體數據的組織44內部排序與外部排序內部排序與外部排序內部排序：內部排序： 待排序的數據元素存放在計算機內存中進行的排待排序的數據元素存放在計算機內存中進行的排序過程。內部排序方法序過程。內部排序方法:插入排序插入排序選擇排序選擇排序交換排序交換排序外部排序：外部排序： 待排序的數據元素數量很大，以致內存存中一次待排序的數據元素數量很大，以致內存存中一次不能容納全部數據，在排序過程中尚需對外存進行訪不能容納全部數據，在排序過程中尚需對外存進行訪問的排序過程。問的排序過程。第九章第九章 群體類群體類和群體數據的組織和群體數據的組織459.3.1 插入排序插入排序 每一步將一個待排序元

38、素按其關鍵字值的大小插入到已排每一步將一個待排序元素按其關鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。序序列的適當位置上，直到待排序元素插入完為止。初始狀態：初始狀態： 5 4 10 20 12 3 5 4 10 20 12 3插入操作：插入操作：1 4 4 5 10 20 12 31 4 4 5 10 20 12 32 10 4 5 10 20 12 32 10 4 5 10 20 12 33 20 4 5 10 20 12 33 20 4 5 10 20 12 34 12 4 5 10 12 20 34 12 4 5 10 12 20 35 3 3 4 5 10 1

39、2 205 3 3 4 5 10 12 20第九章第九章 群體類群體類和群體數據的組織和群體數據的組織46直接插入排序直接插入排序/9_11.h : 直接插入排序函數模板直接插入排序函數模板template void InsertionSort(T A , int n) int i, j ; T temp; for (i = 1; i 0 & temp A j-1 ) /逐個比較逐個比較 A j = A j-1 ; /將元素逐個后移，以便找到插入位置將元素逐個后移，以便找到插入位置 j - - ; A j = temp ;/ 插入位置找到，立即插入插入位置找到，立即插入 第九章第九章

40、群體類群體類和群體數據的組織和群體數據的組織479.3.2 選擇排序選擇排序每次從待排序序列中選擇一個關鍵字最小的元素，（當需每次從待排序序列中選擇一個關鍵字最小的元素，（當需要按關鍵字升序排列時），順序排在已排序序列的最后，直至要按關鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。全部排完。5 4 10 20 12 35 4 10 20 12 3待排序序列：待排序序列：3 4 10 20 12 53 4 10 20 12 53 4 10 20 12 53 4 10 20 12 5第第 i i 次選擇后，將選出的那個元素與第次選擇后，將選出的那個元素與第 i i 個元素做交換。個元素

41、做交換。3 4 5 20 12 103 4 5 20 12 10. .第九章第九章 群體類群體類和群體數據的組織和群體數據的組織48直接選擇排序直接選擇排序/9_12.h : 直接選擇排序函數模板直接選擇排序函數模板template void Swap ( T &x, T &y )/ 輔助函數：交換輔助函數：交換x和和y的值的值 T temp ; temp = x ; x = y ; y = temp ;template void SelectionSort ( T A , int n ) int smallIndex int i, j ; for ( i = 0; i n-1

42、; i+ ) smallIndex = i ; /最小元素之下標初值設為最小元素之下標初值設為i for ( j = i+1; j n; j+ )/逐個比較逐個比較 if ( A j A smallIndex ) smallIndex = j ;/記錄當前找到的最小值的下標記錄當前找到的最小值的下標 Swap ( A i , A smallIndex ) ; / 將這一趟找到的最小元素與將這一趟找到的最小元素與A I 交換交換 第九章第九章 群體類群體類和群體數據的組織和群體數據的組織499.3.3 交換排序交換排序 兩兩比較待排序序列中的元素，并交換不滿足順序要求的各兩兩比較待排序序列中的元

43、素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。對元素，直到全部滿足順序要求為止。 最簡單的交換排序方法最簡單的交換排序方法起泡排序。起泡排序。 對具有對具有n個元素的序列按升序進行起泡排序的步驟：個元素的序列按升序進行起泡排序的步驟： 首先將第一個元素與第二個元素進行比較，若為逆序，則將首先將第一個元素與第二個元素進行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。個元素進行了比較和交換。此過程稱為第一趟起泡排序。經過第一趟，最大的元

44、素便被交換到第經過第一趟，最大的元素便被交換到第n個位置。個位置。 對前對前n-1個元素進行第二趟起泡排序，將其中最大元素交換個元素進行第二趟起泡排序，將其中最大元素交換到第到第n-1個位置。個位置。 如此繼續，直到某一趟排序未發生任何交換時，排序完畢。如此繼續，直到某一趟排序未發生任何交換時，排序完畢。對對n個元素的序列，起泡排序最多需要進行個元素的序列，起泡排序最多需要進行n-1趟。趟。第九章第九章 群體類群體類和群體數據的組織和群體數據的組織50起泡排序舉例：對整數序列起泡排序舉例：對整數序列 8 5 2 4 3 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初初始始狀狀態態第第一一趟趟結結果果第第二二趟趟結結果果第第三三趟趟結結果果第第四四趟趟結結果果小小的的逐逐漸漸上上升升每趟沉下一個最大的第九章第九章 群體類群體類和群體數據的組織和群體數據的組織51/9_13.h : 起泡排序函數模板起泡排序函數模板template v