群体类和群体数据的组织ppt课件

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