1、1、函數模板和類模板、函數模板和類模板2、線性群體、線性群體3、群體數據的組織、群體數據的組織4、綜合實例、綜合實例3 函數模板函數模板 類模板類模板4理想的函數重載是針對不同的參數做不同的事理想的函數重載是針對不同的參數做不同的事. int abs(int x) return x0?-x:x;double abs(double x) return x0?-x:x;5 函數模板可以用來創建一個通用功能的函函數模板可以用來創建一個通用功能的函數，以支持多種不同形參，進一步簡化重數，以支持多種不同形參，進一步簡化重載函數的函數體設計。載函數的函數體設計。 6 函數模板的定義形式：函數模板的定義形式

2、：template返回類型返回類型 函數名函數名(函數模板形參表函數模板形參表) 函數模板定義體函數模板定義體 template T abs(T x) return x0?-x:x;7/9_0.cpp#includeusing namespace std;templateT abs(T x) return x0?-x:x; int main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl;return 0; 8 編譯器從調用編譯器從調用abs()時實參的類型，推時實參的類型，推導出函數模板的類型參數。導出函數模板的類型參數。

3、例如，對于調用表達式例如，對于調用表達式abs(n)，由于，由于實參實參n為為int型，所以推導出模板中類型型，所以推導出模板中類型參數參數T為為int。 當類型參數的含義確定后，編譯器將以當類型參數的含義確定后，編譯器將以函數模板為樣板，生成一個函數：函數模板為樣板，生成一個函數：int abs(int x) return x0?-x:x; 9/9_1.cpp#includeusing namespace std;templatevoid outputArray(const T* array,int count)for(int i=0;icount;i+)coutarrayi ;couten

4、dl; 10int main() const int A_COUNT=8,B_COUNT=8,C_COUNT=20;int aA_COUNT=1,2,3,4,5,6,7,8;double bB_COUNT=1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8;char cC_COUNT=Welcome to see you!;couta array contains:endl;outputArray(a,A_COUNT);coutb array contains:endl;outputArray(b,B_COUNT);coutc array contains:endl;outputA

5、rray(c,C_COUNT);return 0; 11使用類模板使用戶可以為類聲明一使用類模板使用戶可以為類聲明一種模式，使得類中的某些數據成員、種模式，使得類中的某些數據成員、某些成員函數的參數、某些成員函數某些成員函數的參數、某些成員函數的返回值，能取任意類型。（包括基的返回值，能取任意類型。（包括基本類型的和用戶自定義類型）。本類型的和用戶自定義類型）。12類模板：類模板：template class 類名類名類類成員成員聲明聲明如果需要在類模板以外定義其成員函數，則要如果需要在類模板以外定義其成員函數，則要采用以下的形式：采用以下的形式：template 返回類型返回類型名名 類名類

6、名:函數函數名名(參數表參數表)13/9_2.cpp#include #include using namespace std;/ 結構體結構體Studentstruct Student int id; /學號學號 float gpa; /平均分平均分;/類模板：實現對任意類型數據進行存取類模板：實現對任意類型數據進行存取 template class Storepublic: Store(); / 默認形式（無形參）的構造函數默認形式（無形參）的構造函數 T& getElem(); /提取數據函數提取數據函數 void putElem(T x); /存入數據函數存入數據函數private:

7、T item; / 用于存放任意類型的數據用于存放任意類型的數據 bool haveValue; / 用于標記用于標記item是否已被存入內是否已被存入內容容 ;template Store:Store():haveValue(false) 14template / 提取數據函數的實現提取數據函數的實現T& Store:getElem() / 如果試圖提取未初始化的數據，則終止程序如果試圖提取未初始化的數據，則終止程序 if (!haveValue) cout No item present! endl; exit(1); return item; / 返回返回item中存放的數據中存放的數據

8、 template / 存入數據函數的實現存入數據函數的實現 void Store:putElem(T x) haveValue=true; / 將將haveValue 置為置為 TRUE，表示，表示item中已存入數值中已存入數值 item=x; / 將將x值存入值存入item15int main() Store s1, s2; s1.putElem(3); s2.putElem(-7); couts1.getElem() s2.getElem()endl; Student g=1000, 23; Store s3; s3.putElem(g); cout The student id is

9、 s3.getElem().id endl;Store d; cout Retrieving object d. ;cout d.getElem() endl; /輸出對象輸出對象D的數據成員的數據成員/ 由于由于D未經初始化未經初始化,在執行函數在執行函數D.getElement()時出錯時出錯return 0;1617 線性群體線性群體線性群體的概念線性群體的概念直接訪問群體直接訪問群體-數組類數組類順序訪問群體順序訪問群體-鏈表類鏈表類棧類棧類隊列類隊列類18群體群體是指由多個數據元素組成的集合體是指由多個數據元素組成的集合體。群體可以分為兩個大類：。群體可以分為兩個大類：線性群體線性群

10、體和和非線非線性群體。性群體。線性群體線性群體中的元素按中的元素按位置排列有序位置排列有序，可，可以區分為第一個元素、第二個元素等。以區分為第一個元素、第二個元素等。非線性群體不用位置順序非線性群體不用位置順序來標識元素。來標識元素。19線性群體中的元素次序與其位置關系是對線性群體中的元素次序與其位置關系是對應的。在線性群體中，又可按照訪問元素的不應的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。同方法分為直接訪問、順序訪問和索引訪問。在本章我們只介紹直接訪問和順序訪問。在本章我們只介紹直接訪問和順序訪問。第一個元素第二個元素第三個元素最后一個元素20 靜態數組是

11、具有固定元素個數的群體，其中靜態數組是具有固定元素個數的群體，其中的元素可以通過下標直接訪問。的元素可以通過下標直接訪問。缺點：大小在編譯時就已經確定，在運行缺點：大小在編譯時就已經確定，在運行時無法修改。時無法修改。 動態數組由一系列位置連續的，任意數量相動態數組由一系列位置連續的，任意數量相同類型的元素組成。同類型的元素組成。優點：其元素個數可在程序運行時改變。優點：其元素個數可在程序運行時改變。 動態數組類模板：例動態數組類模板：例9-3（9_3.h）/Array.h#ifndef ARRAY_H#define ARRAY_H#include /數組類模板的定義數組類模板的定義templ

12、ate class Arrayprivate:T* list;int size;public:Array(int sz=50); /構造函數構造函數Array(const Array &a);/復制構造函數復制構造函數Array();21Array& operator=(const Array &rhs);T& operator(int i);const T& operator(int i) const;operator T*();operator const T*()const;int getSize()const;void resize(int size);2223/構造函數構造函數tem

13、plateArray:Array(int sz)assert(sz=0);size=sz;list=new Tsize;/析構函數析構函數templateArray:Array()deletelist;24/復制構造函數復制構造函數templateArray:Array(const Array &a)size=a.size;list=new Tsize;for(int i=0;isize;i+)listi=a.listi;25 alist sizeAA的數組元素的數組元素占用的內存占用的內存拷貝前拷貝前 alist sizeAA的數組元素占用的內存拷貝后拷貝后 alist sizeBint m

14、ain() Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;26 alist sizeAA的數組元素的數組元素占用的內存占用的內存拷貝前拷貝前 alist sizeAA的數組元素的數組元素占用的內存占用的內存拷貝后拷貝后 alist sizeBB的數組元素的數組元素占用的內存占用的內存27templateArray& Array:operator =(const Array& rhs)if(&rhs!=this)if(size!=rhs.size)de

15、lete list;size=rhs.size;list=new Tsize;for(int i=0;isize;i+)listi=rhs.listi;return *this;28templateT& Array:operator (int n)assert(n=0&nsize);return listn;templateconst T& Array:operator (int n)constassert(n=0&nsize);return listn;29 如果一個函數的返回值是一個對象的值，它如果一個函數的返回值是一個對象的值，它就被認為是一個常量，不能成為左值。就被認為是一個常量，不能

16、成為左值。 如果返回值為引用。由于引用是對象的別名如果返回值為引用。由于引用是對象的別名，所以通過引用當然可以改變對象的值。，所以通過引用當然可以改變對象的值。30template Array:operator T*()return list;template Array:operator const T*()constreturn list;31#include using namespace std;int main() int a10; void read(int *p, int n); read(a, 10);void read(int *p, int n) for (int i=0;

17、 ipi;int main() Array a(10); void read(int *p, n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;32 例例9-4求范圍求范圍2N中的質數，中的質數，N在程序在程序運行時由鍵盤輸入。運行時由鍵盤輸入。/9_4.cpp#include #include #include Array.husing namespace std;int main()Array a(10);int count=0;int n;cout=2 as upper limit for prime numbers:;

18、cinn;acount+=2;33for(int i=2;i=n;i+)bool isPrime=true;for(int j=0;jcount;j+)/檢查檢查i是否能被比它小的質數整除是否能被比它小的質數整除if(i%aj=0)isPrime=false;break;if(isPrime)/如果質數表滿了，將其空間加倍如果質數表滿了，將其空間加倍if(count=a.getSize()a.resize(count*2);acount+=i;for(i=0;icount;i+)coutsetw(8)ai;coutendl;return 0;3435 鏈表是一種動態數據結構，可以用來鏈表是一種

19、動態數據結構，可以用來表示順序訪問的線性群體。表示順序訪問的線性群體。 鏈表是由系列鏈表是由系列結點結點組成的，結點可以組成的，結點可以在運行時動態生成。在運行時動態生成。 每一個結點包括每一個結點包括數據域數據域和指向鏈表中和指向鏈表中下一個結點的下一個結點的指針指針（即下一個結點的（即下一個結點的地址）。如果鏈表每個結點中只有一地址）。如果鏈表每個結點中只有一個指向后繼結點的指針，則該鏈表稱個指向后繼結點的指針，則該鏈表稱為單鏈表。為單鏈表。36 data1 data2 data3 datan NULLheadrear37/結點類模板的定義結點類模板的定義templateclass Nod

20、eprivate:Node* next;public:T data;Node(const T &data,Node *next=0);void insertAfter(Node *p);Node* deleteAfter();Node* nextNode();const Node* nextNode() const;38/構造函數構造函數templateNode:Node(const T&data,Node*next):data(data),next(next) /返回后繼結點的指針返回后繼結點的指針templateNode* Node:nextNode()return next;/返回后繼結

21、點的指針返回后繼結點的指針templateconst Node* Node:nextNode()constreturn next;39/在當前結點之后插入一個結點在當前結點之后插入一個結點ptemplatevoid Node:insertAfter(Node*p)p-next=next;next=p; data1 data2 p data40 /刪除當前結點的后繼結點，并返回其地址刪除當前結點的后繼結點，并返回其地址templateNode* Node:deleteAfter()Node* tempPtr=next;if(next=0)return 0;next=tempPtr-next;re

22、turn tempPtr; data1 data2 data3tempPtr41#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedListprivate:Node*front,*rear;/表頭和表尾指針表頭和表尾指針Node*prevPtr,*currPtr;/記錄表當前遍歷位記錄表當前遍歷位置的指針，由插入和刪除操作更新置的指針，由插入和刪除操作更新int size; /表中元素的個數表中元素的個數int position;/當前元素在表中的位置序號。由函當前元素在表中的位置序號。由函數數

23、reset使用使用42/生成新結點，數據域為生成新結點，數據域為item，指針域為，指針域為ptrNext;Node* newNode(const T &item,Node* ptrNext=NULL); /釋放結點釋放結點void freeNode(Node*p);/將鏈表將鏈表L復制到當前輩復制到當前輩(假設當前表位空假設當前表位空)/被復制構造函數和被復制構造函數和“operator=”調用調用void copy(const LinkedList&L);public:LinkedList();LinkedList(const LinkedList&L);LinkedList(); int

24、 getSize() const;/返回鏈表中元素的個數返回鏈表中元素的個數 bool isEmpty() const;/鏈表是否為空鏈表是否為空43void reset(int pos=0);/初始化游標的位置初始化游標的位置void next(); /使游標移動到下一個結點使游標移動到下一個結點bool endOfList()const;/游標是否到了鏈尾游標是否到了鏈尾int currentPosition(void) const;/返回游標的當前位返回游標的當前位void insertFront(const T&item);/在表頭插入結點在表頭插入結點void insertRear(

25、const T& item);/在表尾插入結點在表尾插入結點void insertAt(const T& item);/在當前結點之前插入結點在當前結點之前插入結點void insertAfter(constT& item);/在當前結點之后插入結點在當前結點之后插入結點void deleteFront();/刪除頭結點刪除頭結點void deleteCurrent(); /刪除當前結點刪除當前結點T& data();/返回對當前結點數據成員的引用返回對當前結點數據成員的引用const T&data()const;/返回對當前結點數據成員的常引用返回對當前結點數據成員的常引用/清空鏈表：釋放所

26、有結點的內存空間。被析構函數和清空鏈表：釋放所有結點的內存空間。被析構函數和operator=調用調用 void clear();44#include #include LinkedList.husing namespace std;int main()LinkedList list;/輸入輸入10個整數依次向表頭插入個整數依次向表頭插入for(int i=0;iitem;list.insertFront(item); /輸出鏈表輸出鏈表coutList ;list.reset();while(!list.endOfList()coutlist.data() ;list.next();cout

27、endl;45 /輸入要刪除的整數輸入要刪除的整數int key;coutkey;/查找并刪除結點查找并刪除結點list.reset();while(!list.endOfList()if(list.data()=key)list.deleteCurrent();list.next();46 /輸出鏈表輸出鏈表coutList: ;list.reset();/輸出各結點數據，直到鏈表尾輸出各結點數據，直到鏈表尾while(!list.endOfList()coutlist.data() ;list.next();coutendl;return 0;4748棧是只能從一端訪問的線性群體，可以訪問

28、的棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。這一端稱棧頂，另一端稱棧底。ana2a1入棧出棧棧頂棧底49ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)50 棧空棧空棧中沒有元素棧中沒有元素 棧滿棧滿棧中元素個數達到上限棧中元素個數達到上限 一般狀態一般狀態棧中有元素，但未達到棧滿狀態棧中有元素，但未達到棧滿狀態棧頂ana1a0入棧出棧數組下標maxn10一般狀態棧頂入棧出棧數組下標初始狀態（棧空）maxn10棧頂amaxana1a0入棧出

29、棧數組下標maxn10棧滿狀態5152 初始化初始化 入棧入棧 出棧出棧 清空棧清空棧 訪問棧頂元素訪問棧頂元素 檢測棧的狀態（滿、空）檢測棧的狀態（滿、空）53/Stack.h#ifndef STACK_H#define STACK_H#include /棧類模板的定義棧類模板的定義,SIZE為棧的大小為棧的大小template class Stackprivate:T listSIZE;int top;54public: Stack(); void push(const T &item); T pop(); void clear(); const T &peek() const; bool

30、 isEmpty() const; bool isFull() const;/類的實現略類的實現略55 例例9_9 一個簡單的整數計算器一個簡單的整數計算器實現一個簡單的整數計算器，能夠進行加、實現一個簡單的整數計算器，能夠進行加、減、乘、除和乘方運算。使用時算式采用后綴輸減、乘、除和乘方運算。使用時算式采用后綴輸入法，每個操作數、操作符之間都以空白符分隔入法，每個操作數、操作符之間都以空白符分隔。例如，若要計算。例如，若要計算“3+5”則輸入則輸入“3 5 +”。乘。乘方運算符用方運算符用“”表示。每次運算在前次結果基礎表示。每次運算在前次結果基礎上進行，若要將前次運算結果清除，可鍵入上進行

31、，若要將前次運算結果清除，可鍵入“c”。當鍵入。當鍵入“q”時程序結束。時程序結束。/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#include Stack.hclass Calculatorprivate:Stack s;void enter(double num);bool getTwoOperands(double &opnd1,double &opnd2);void compute(char op);public:void run();void clear();#endif56/Calculator.cpp#include

32、Calculator.h#include #include #include using namespace std;void Calculator:enter(double num) s.push(num); 57/連續將兩個操作數彈出棧，放在連續將兩個操作數彈出棧，放在opnd1和和opnd2中中/如果棧中沒有兩個操作數，則返回如果棧中沒有兩個操作數，則返回false并輸出相關信息并輸出相關信息bool Calculator:getTwoOperands(double& opnd1, double& opnd2) if (s.isEmpty() cerr Missing operand!

33、endl; return false; opnd1 = s.pop(); if (s.isEmpty() cerr Missing operand! endl; return false; opnd2 = s.pop(); return true;58void Calculator:compute(char op) double operand1, operand2;bool result = getTwoOperands(operand1, operand2); if (result) switch(op) case +: s.push(operand2+operand1); break;

34、case -: s.push(operand2-operand1); break; case *: s.push(operand2*operand1); break; case /: if (operand1=0)cerr Divide by 0! endl;s.clear(); else s.push(operand2/operand1); break; case : s.push(pow(operand2,operand1); break;default:cerrUnrecognized operator!endl;break;cout=s.peek()result;return resu

35、lt;void Calculator:clear(void) s.clear(); 60void Calculator:run(void) string str; while(cinstr, str!=q) switch(str0) case c: s.clear(); break; case -: if(str.size()1) enter(stringToDouble(str); else compute(str0); break; case +: case *: case /: case : compute(str0); break; default: enter(stringToDou

36、ble(str); break; 61/9_9.cpp#include Calculator.hint main() Calculator c; c.run(); return 0;6263隊列是只能向一端添加元素，從另一端隊列是只能向一端添加元素，從另一端刪除元素的線性群體刪除元素的線性群體a1 a2an-1 an隊頭隊尾入隊出隊a064 隊空隊空隊列中沒有元素隊列中沒有元素 隊滿隊滿隊列中元素個數達到上限隊列中元素個數達到上限 一般狀態一般狀態隊列中有元素，但未達到隊滿狀態隊列中有元素，但未達到隊滿狀態a0 a1an-1 an隊頭隊頭隊尾隊尾入隊入隊出隊出隊數組下標數組下標 0 1 n-1

37、 n max(一般狀態一般狀態)隊頭隊頭隊尾隊尾入隊入隊出隊出隊數組下標數組下標 0 1 n-1 n max(隊空狀態隊空狀態) a0 a1 an-1 an amax隊頭隊頭隊尾隊尾入隊入隊出隊出隊數組下標數組下標 0 1 n-1 n max(隊滿狀態隊滿狀態)元素移動方向元素移動方向6566在想象中將數組彎曲成環形，元素出隊時在想象中將數組彎曲成環形，元素出隊時，后繼元素不移動，每當隊尾達到數組最后一，后繼元素不移動，每當隊尾達到數組最后一個元素時，便再回到數組開頭。個元素時，便再回到數組開頭。1234m-1m-2m-30amam+1am+2a3隊頭隊頭隊尾隊尾a4am-2am-3am-1隊

38、滿狀態隊滿狀態 元素個數元素個數=m1234m-1m-2m-30隊尾隊尾隊頭隊頭隊空狀態隊空狀態 元素個數元素個數=0隊尾隊尾1234m-1m-2m-30a0a1a2a3隊頭隊頭一般狀態一般狀態6768/Queue.h#ifndef QUEUE_H#define QUEUE_H#include /隊列類模板的定義隊列類模板的定義,SIZE為隊列的長度為隊列的長度template class Queueprivate:int front,rear,count;/隊頭指針、隊尾指針、元素個數隊頭指針、隊尾指針、元素個數T listSIZE;/隊列元素數組隊列元素數組public:Queue();/

39、構造函數，初始化隊頭指針、隊尾指針、元素個數構造函數，初始化隊頭指針、隊尾指針、元素個數void insert(const T &item);/新元素入隊新元素入隊T remove(); /元素出隊元素出隊69void clear();/清空隊列清空隊列const T&getFront() const;/訪問隊首元素訪問隊首元素/測試隊列狀態測試隊列狀態int getLength() const;/求隊列長度求隊列長度bool isEmpty() const;/判斷隊列空否判斷隊列空否bool isFull() const;/判斷隊列滿否判斷隊列滿否;/隊列類模板的實現隊列類模板的實現/構造函

40、數，初始化隊頭指針、隊尾指針、元素個數構造函數，初始化隊頭指針、隊尾指針、元素個數template Queue:Queue():front(0),rear(0),count(0) 70/訪問隊首元素訪問隊首元素template const T& Queue:getFront() constreturn listfront;/返回隊列元素的個數返回隊列元素的個數template int Queue:getLength() constreturn count;/測試隊列是否為空測試隊列是否為空template bool Queue:isEmpty() constreturn count=0;71t

41、emplate bool Queue:isFull() constreturn count=SIZE;template void Queue:clear()count=0;front=0;rear=0;#endif72 插入排序插入排序 選擇排序選擇排序 交換排序交換排序 順序查找順序查找 折半查找折半查找73 排序排序是計算機程序設計中的一種重要操作，是計算機程序設計中的一種重要操作，它的功能是將一個數據元素的任意序列，重它的功能是將一個數據元素的任意序列，重新排列成一個按新排列成一個按關鍵字關鍵字有序的序列。有序的序列。數據元素數據元素：數據的基本單位。在計算機中：數據的基本單位。在計算機

42、中通常作為一個整體進行考慮。一個數據元通常作為一個整體進行考慮。一個數據元素可由若干數據項組成。素可由若干數據項組成。關鍵字關鍵字：數據元素中某個數據項的值，用：數據元素中某個數據項的值，用它可以標識（識別）一個數據元素。它可以標識（識別）一個數據元素。 在排序過程中需要完成兩種基本操作：在排序過程中需要完成兩種基本操作：比較兩個數的大小比較兩個數的大小調整元素在序列中的位置調整元素在序列中的位置74 內部排序內部排序：待排序的數據元素存放在計算機內：待排序的數據元素存放在計算機內存中進行的排序過程。存中進行的排序過程。 外部排序外部排序：待排序的數據元素數量很大，以致：待排序的數據元素數量很

43、大，以致內存存中一次不能容納全部數據，在排序過程內存存中一次不能容納全部數據，在排序過程中尚需對外存進行訪問的排序過程。中尚需對外存進行訪問的排序過程。75 插入排序插入排序 選擇排序選擇排序 交換排序交換排序76 每一步將一個待排序元素按其關鍵字值的大小插每一步將一個待排序元素按其關鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素入到已排序序列的適當位置上，直到待排序元素插入完為止。插入完為止。初始狀態：初始狀態： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入操作：1 1 4 4 4 5 10 20 12 34 5 10 20 12 32 2 10 10 4

44、 5 10 20 12 3 4 5 10 20 12 33 3 2020 4 5 10 20 12 3 4 5 10 20 12 34 4 12 12 4 5 10 12 20 3 4 5 10 12 20 35 5 3 3 3 4 5 10 12 20 3 4 5 10 12 2077 在插入排序過程中，由于尋找插入位置的方法不在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。介紹最簡單的直接插入排序算法。 例例9-11 直接插入排序函數模板（直接插入排序函數模板（9_11.h）temp

45、latevoid insertionSort(T a,int n)int i,j;T temp;/將下標為將下標為1n-1的元素逐個插入到已排序序列中適當的位置的元素逐個插入到已排序序列中適當的位置for(i=1;i0&temp=aj-1時，時，j便是應插入的位置便是應插入的位置/若達到若達到j=0，則，則0是應插入的位置是應插入的位置aj=aj-1;j-;/插入位置已找到，立即插入插入位置已找到，立即插入aj=temp;7879每次從待排序序列中選擇一個關鍵字最小的每次從待排序序列中選擇一個關鍵字最小的元素，（當需要按關鍵字升序排列時），順序排元素，（當需要按關鍵字升序排列時），順序排在已排

46、序序列的最后，直至全部排完。在已排序序列的最后，直至全部排完。5 4 10 20 12 3初始狀態：初始狀態：3 4 10 20 12 53 4 10 20 12 5第第 i i 次選擇后，將選出的那個記錄與第次選擇后，將選出的那個記錄與第 i i 個記錄做交換。個記錄做交換。3 4 5 20 12 10. .80 在選擇類排序方法中，從待排序序列中選在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選出待排序序列中的最小元素，稱為

47、直接選擇排序。擇排序。 例例9-12 直接選擇排序函數模板（直接選擇排序函數模板（9-12.h）/輔助函數：交換輔助函數：交換x和和y的值的值templatevoid mySwap(T &x,T &y)T temp=x;x=y;y=temp;/用選擇法對數組用選擇法對數組a的的n個元素進行排序個元素進行排序template void selectionSort(T a,int n)for(int i=0;in-1;i+)int leastIndex=i;/在元素在元素ai+1.an-1中逐個比較，顯出最小值中逐個比較，顯出最小值for(int j=i+1;jn;j+)if(ajaleastIndex)leastIndex=j;mySwap(ai,aleastIndex);8182兩兩比較待排序序列中的元素，兩兩比較待排序序列中的元