第11章 查找与排序

1、第十一章第十一章 查找和排序查找和排序 本章内容本章内容 查找查找 顺序查找顺序查找 二分查找二分查找 二叉排序树查找二叉排序树查找 哈希查找哈希查找 平均查找长度的计算平均查找长度的计算 n 排序排序 l 直接插入排序直接插入排序 l 直接选择排序直接选择排序 l 冒泡排序冒泡排序 查找的基本概念查找的基本概念 查找：在数据元素集合(查找表)中查找关 键字与给定值相等的数据元素。 关键字：数据元素中的一个或多个数据 项值，它可以惟一标识一个数据元素。 平均查找长度(ASL)： i n i i CPASL 1 式中，n为查找表的长度；pi为查找第i个元素的概率，在等 概率情况下pi等于1/n；

2、 Ci为找到第i个元素时的比较次数 顺序查找顺序查找 要求： 查找表必须采用线性表。 基本思想：用给定值依次与线性表中每 个元素的关键字进行比较。如果某个元 素的关键字与给定值相同，则查找成功； 如果找遍全表也没有发现满足条件的元 素，则查找失败。 算法实现： 顺序表类和单链表类中的 search函数。 实现一：顺序表类中实现顺序查找的成员函数实现一：顺序表类中实现顺序查找的成员函数 /查找元素查找元素x并返回其下标，若元素不存在，则返回并返回其下标，若元素不存在，则返回-1 /被查找的数存放在一个数组中，从数组的第一个元素被查找的数存放在一个数组中，从数组的第一个元素 开始，依次往下比较，直

3、到找到要找的元素为止。开始，依次往下比较，直到找到要找的元素为止。 int Seqlist:Search ( char x ) int i = 0; for( i = 0; i next; while( p != NULL ) if( p - data = x ) break; p = p - next; return p; 顺序查找的平均查找长度 评价：在用顺序查找方法完成查找时， 每进行一次成功查找需要的平均比较次 数约为表长度的一半，因此，它的效率 较低。适用于在查找表较小的情况下进 行查找。 )( 2 11 11 nO n i n CPASL n i i n i i 二分查找（折半查找

4、）二分查找（折半查找） 要求： 必须以顺序方式存储线性表 线性表中所有数据元素必须按照关键字有序排列 基本思想：将给定值与处于顺序表“中间位置” 上的元素的关键字进行比较，若相等则查找成 功；若给定值大于关键字则在表的后半部分继 续进行二分查找，否则在表的前半部分继续进 行二分查找。如此进行下去直至找到满足条件 的元素，或当前查找区为空，此时查找失败。 1.设表长为n，low、high和mid分别指向待查元素 所在区间的上界、下界和中点，k为给定值。 2.初始时， 令 low = 0，high = n - 1，mid= (low+high)/2 让 k 与 mid 指向的记录比较 若 k =

5、rmid ，查找成功 若 k rmid ，则low = mid + 1 3.重复上述操作，直至low high时，查找失败。 二分查找算法实现二分查找算法实现 0Atlanta 1Boston 2Chicago 3Denver 4Detroit 5Houston 6Los Angeles 7Miami 8New York 9Philadelphi a 10 San Francisco 11 Seattle Seattle 11 San Francisco10 Philadelphia9 New York8 Miami7 Los Angeles6 Houston5 Detroit4 Denver

6、3 Chicago2 Boston1 Atlanta0 Seattle 11 San Francisco10 Philadelphia9 New York8 Miami7 Los Angeles6 Houston5 Detroit4 Denver3 Chicago2 Boston1 Atlanta0 lowhigh mid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 找找21例如例如 key = 21 的查找过程的查找过程 low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2 lowhi

7、ghmid 5 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 lowhighmid 0 1 2 3 4 5 6 7 8 9 10 例例key = 70 的查找过程的查找过程 lowhigh mid 找找70 5 13 19 21 37 56 64 75 80 88 92 lowhighmid 5 13 19 21 37 56 64 75 80 88 92 low high mid 5 13 19 21 37 56 64 75 80 88 92 low high mid 0

8、 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92 low high 5 13 19 21 37 56 64 75 80 88 92 当下界当下界low大于上界大于上界high时，则说明表中时，则说明表中 没有关键字等于没有关键字等于key的元素，查找不成功。的元素，查找不成功。 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3

9、 4 5 6 7 8 9 10 例：例：二分查找函数模板及其测试程序二分查找函数模板及其测试程序 #include using namespace std; template int BinSearch( T A , int low , int high , T key ) int mid; while(low = high) mid=(low + high) / 2; if( key = Amid ) return mid; /查找成功，返回元素的下标查找成功，返回元素的下标 if( key Amid ) high=mid-1; /到表的前半部分查找到表的前半部分查找 else low =

10、mid + 1; /到表的后半部分查找到表的后半部分查找 return -1;/查找失败，返回失败标志查找失败，返回失败标志-1 int main() int a = 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , k = 7 , i; i = BinSearch(a , 0 , 7 , k); if( i = -1 ) 例：例：用递归方法实现二分查找函数模板用递归方法实现二分查找函数模板 #include using namespace std; template int BinSearch( T A , int low , int high , T key ) int mi

11、d; if(low high) return -1; /查找失败，返回失败标志查找失败，返回失败标志-1 else mid=(low + high) / 2; if( key = Amid ) return mid; /查找成功，返回元素的下标查找成功，返回元素的下标 if( key Amid ) BinSearch( A , low , mid - 1 , key ); /到表的前半部分查找到表的前半部分查找 else BinSearch( A , mid + 1 , high , key ); /到表的后半部分查找到表的后半部分查找 int main() int a = 1 , 2 , 3

12、 , 4 , 5 , 6 , 7 , 8 , k = 7 , i; i = BinSearch(a , 0 , 7 , k); 二分查找二分查找 在二分查找中，比较的次数取决于所要查找 的元素在数组中的位置。对于n个元素的数 组，在最坏的情况下所要查找的元素必须查 到查找区间只剩下一个元素时才能找到或者 能确定该元素根本不在数组中。 二分查找优缺点二分查找优缺点 优点： 查找效率高 平均查找长度 缺点： 查找前要将表中元素按关键字有序排列 只适用于线性表的顺序存储。适用于那种一经 建立就很少改动而又经常需要查找的线性表。 )(log1) 1(log 1 2 1 22 1 11 nOn n n

13、j n CPASL j k j i n i i 搜索算法的效率搜索算法的效率 顺序搜索的平均时间性能 （1 + 2 + 3 + + n ) / n = ( n + 1 ) / 2 二分查找的最坏情况的时间性能 n / 2 / 2 / 2 / 2 = 1 n=2k 使用二分查找算法最多只需要k=log2n次比较即可 K次次 )(nO )(log 2 nO 平均查找长度： 平均查找长度： N和和log2N的值的值 Nlog2N 103 1007 100010 1,000,00020 1,000,000,00030 二叉排序树查找二叉排序树查找 n将数据集合中的数据元素存储为一颗二将数据集合中的数据

14、元素存储为一颗二 叉排序树，叉排序树， 然后按给定方法进行查找。然后按给定方法进行查找。 二叉排序树的定义：二叉排序树的定义： 二叉排序树或者是一棵空二叉树，或者二叉排序树或者是一棵空二叉树，或者 是具有以下性质的二叉树：是具有以下性质的二叉树： 若它的左子树非空，则左子树上所有结点的若它的左子树非空，则左子树上所有结点的 值均小于根结点的值；值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的若它的右子树非空，则右子树上所有结点的 值均不小于根结点的值；值均不小于根结点的值； 左、右子树本身又各是一棵二叉排序树。左、右子树本身又各是一棵二叉排序树。 二叉排序树二叉排序树 二叉排序树：

15、二叉排序树：一种特殊的二叉树，其特点是：左子树上一种特殊的二叉树，其特点是：左子树上 所有结点的值均小于其双亲结点的值，右子树上所有结点的所有结点的值均小于其双亲结点的值，右子树上所有结点的 值均大于或等于其双亲结点的值。值均大于或等于其双亲结点的值。 56 89 47 23 1526 50 3080 2090 1085 40 3525 2388 66 不是二叉排序树。不是二叉排序树。 插入操作：插入操作： 若二叉排序树为空，则新结点为二叉排序树的根结点；否若二叉排序树为空，则新结点为二叉排序树的根结点；否 则将新结点的关键字值和根结点的关键字值进行比较，若则将新结点的关键字值和根结点的关键字

16、值进行比较，若 小于根结点的值，则将新结点插入到左子树中去，否则，小于根结点的值，则将新结点插入到左子树中去，否则， 插入到右子树中去。此插入过程是递归进行的。插入到右子树中去。此插入过程是递归进行的。 设有整数序列设有整数序列47,23,56,15,26,89,将其中的值依次插入将其中的值依次插入 二叉排序树二叉排序树 56 89 47 23 1526 152326475689 中序遍历结果：中序遍历结果： 对二叉排序树进行中序遍历可以得到一个数据元素由小到大对二叉排序树进行中序遍历可以得到一个数据元素由小到大 的有序序列。构造二叉排序树的过程即为对无序序列进行排的有序序列。构造二叉排序树的

17、过程即为对无序序列进行排 序的过程。序的过程。 删除操作：删除操作： 一个结点被删除后，必须保证余下的结点仍然构成一棵二一个结点被删除后，必须保证余下的结点仍然构成一棵二 叉排序树。下面分三种情况讨论：叉排序树。下面分三种情况讨论： u 情况二：被删除的结点至少有一棵空子树，则用那棵非空子情况二：被删除的结点至少有一棵空子树，则用那棵非空子 树的根成为其双亲结点的相应子女树的根成为其双亲结点的相应子女 50 30 25 10 15 35 3337 53 62 60 55 53 62 55 50 30 10 15 35 3337 u 情况一：若被删除的是叶结点，则将对应双亲结点指针域置空情况一：

18、若被删除的是叶结点，则将对应双亲结点指针域置空 u 情况三：被删除的结点有两棵非空的子树情况三：被删除的结点有两棵非空的子树 方法一：找到被删除结点在中序遍历序列中的直接后继结方法一：找到被删除结点在中序遍历序列中的直接后继结 点（它一定在被删除结点的右子树中），用此后继结点的点（它一定在被删除结点的右子树中），用此后继结点的 值取代被删除结点的值，然后删除此后继结点，由于被删值取代被删除结点的值，然后删除此后继结点，由于被删 除的后继结点的左子树一定是空子树，所以删除后继结点除的后继结点的左子树一定是空子树，所以删除后继结点 的过程同情况二。的过程同情况二。 方法二：用被删除结点在中序遍历序

19、列中的直接前驱结方法二：用被删除结点在中序遍历序列中的直接前驱结 点（该结点的右子树也一定为空）代替被删除的结点，点（该结点的右子树也一定为空）代替被删除的结点， 然后删除这个前驱结点。然后删除这个前驱结点。 50 30 10 15 35 3337 53 62 55 53 30 10 15 35 3337 62 55 37 30 10 15 35 33 53 62 55 后继结点后继结点 前驱结点前驱结点 将结点将结点50删除删除 中序遍历结点序列：中序遍历结点序列：10 15 30 33 35 10 15 30 33 35 3737 5050 5353 55 62 55 62 用中序遍历该二

20、叉树得到的直接后继用中序遍历该二叉树得到的直接后继 结点代替该结点，删除直接后继结点结点代替该结点，删除直接后继结点 用中序遍历该二叉树得到的直接前驱用中序遍历该二叉树得到的直接前驱 结点代替该结点，删除直接前驱结点结点代替该结点，删除直接前驱结点 查找操作：查找操作： u 查找查找思路：思路： 当二叉排序树不为空时，将给定值与根结点的值进行比当二叉排序树不为空时，将给定值与根结点的值进行比 较，若相等则查找成功。如果给定值小于根结点的值，较，若相等则查找成功。如果给定值小于根结点的值， 则在根结点的左子树中继续查找，否则在根结点的右子则在根结点的左子树中继续查找，否则在根结点的右子 树中继续

21、查找。当待查找的二叉排序树为空时，查找失树中继续查找。当待查找的二叉排序树为空时，查找失 败。败。 u 平均查找长度：平均查找长度： )(log2nOASL 在二叉排序树中查找成功时走过的是一条从根结点到 所寻找结点的一条路径，因此，二叉排序树查找的平 均查找长度取决于二叉排序树的深度。 在二叉排序树中查找关键字值等于在二叉排序树中查找关键字值等于50,35,90,95 50 3080 2090 85 40 35 8832 505050 30 40 35 5050 80 90 )(log2nOASL 平均查找长度：平均查找长度： 二叉排序树的蜕变：二叉排序树的蜕变： 例如，由整数序列例如，由整

22、数序列15,23,26,47,56,89 生成的二叉排序树生成的二叉排序树 47 56 89 15 23 26 平均查找长度与顺序查找相同平均查找长度与顺序查找相同 当把一组有序值依次插入到一棵二叉排序树时， 生成的二叉排序树将蜕变成一棵单支树。 哈希查找哈希查找 U K T 0 1 2 . . . m- 1 哈希方法：使用函数将哈希方法：使用函数将U映射到表映射到表T0m- 1 的下标上的下标上 哈希函数哈希函数: h(关键值关键值) 元素存储地元素存储地 址址 所有可能出现的关键字集合U 实际存储关键字集合K 哈希表哈希表 如果哈希函数是一一映射的，那么增、 删、改、查的复杂度都是O(1)

23、的。 如果关键字的可能值太多，而数组长度 是有限的，那么哈希函数就只能是多对 一的，就会产生碰撞。 哈希存储哈希存储(哈希表哈希表) 哈希存储(哈希表)： 以数据元素的关键字以数据元素的关键字k为自变量，通过一定的函数关系计算为自变量，通过一定的函数关系计算 出对应的函数值出对应的函数值h(k)，把这个值解释为数据元素的存储地址，把这个值解释为数据元素的存储地址 并把数据元素存储到相应的存储单元内（这个过程称为哈并把数据元素存储到相应的存储单元内（这个过程称为哈 希）。希）。h(k)称为哈希地址。称为哈希地址。 例：设有一组关键字值例：设有一组关键字值85, 72, 49, 58, 15, 7

24、0, 90, 38， 哈希函数哈希函数 h(k) = k mod 12。则对应的哈希地址为：。则对应的哈希地址为： 1, 0, 1, 10, 3, 10, 6, 2 冲突： 若有两个不同的关键字若有两个不同的关键字ki和和kj，即，即ki kj（i j）。）。 但但h(ki) = h(kj)，这种情况称为冲突。，这种情况称为冲突。 ki与与kj 称为同义词。称为同义词。 采用哈希技术要解决的两个主要问题：采用哈希技术要解决的两个主要问题： u 构造一个好的哈希函数，使出现冲突的机会构造一个好的哈希函数，使出现冲突的机会 尽可能少些；尽可能少些； u设计一个有效的解决冲突的办法设计一个有效的解决

25、冲突的办法 哈希表哈希表 碰撞的解决方法： 开放地址法：如果一个元素该在的位置已经有 其他元素，就另安排一个空闲位置。 链地址法：映射到同一位置的元素被串成链表。 解决冲突的方法：开放地址法和链地址法解决冲突的方法：开放地址法和链地址法 u 开放地址法：处理用数组存储哈希表时出现的冲突开放地址法：处理用数组存储哈希表时出现的冲突 发生冲突时按某种规则形成一个地址探查序列发生冲突时按某种规则形成一个地址探查序列 按序列顺序逐个检查各地址单元，直至找到一个未被占按序列顺序逐个检查各地址单元，直至找到一个未被占 用的单元为止用的单元为止 将发生冲突的数据元素存入该地址单元中。将发生冲突的数据元素存入

26、该地址单元中。 线性探查序列线性探查序列 平方探查序列平方探查序列 设哈希表的长度是设哈希表的长度是m，发生冲突的地址是，发生冲突的地址是d d+1, d+2, , m-1, 0, 1, , d-1 (d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, l两种常用的地址探查方法：两种常用的地址探查方法： 设哈希表的长度设哈希表的长度11，哈希函数是，哈希函数是h(k) = k % 11，将整数序列，将整数序列 54,77,94,89,14,45,76存入哈希表。按存入哈希表。按线性探查法线性探查法处理冲突处理冲突 例例1 01234678910 54 7794 89

27、54 % 11 = 10 77 % 11 = 0 94 % 11 = 6 89 % 11 = 1 14 % 11 = 3 45 % 11 = 1 (冲突冲突) 76 % 11 = 10 (冲突冲突) 14 4576 线性探查法建立哈希表线性探查法建立哈希表 5 线性探查地址序列线性探查地址序列 d+1, d+2, , m-1, 0, 1, , d-1 等概率时查找成功的平均查找长度：等概率时查找成功的平均查找长度： ASL=（1+1+1+1+1+2+6）/ 7=13/7 设哈希表的长度设哈希表的长度11，哈希函数是，哈希函数是h(k) = k % 11，将整数序列，将整数序列 54,77,94

28、,89,14,45,76存入哈希表。按平方探查法处理冲突存入哈希表。按平方探查法处理冲突 例例2 012345678910 5477 94 89 54 % 11 = 10 77 % 11 = 0 94 % 11 = 6 89 % 11 = 1 14 % 11 = 3 45 % 11 = 1 (冲突冲突) 76 % 11 = 10 (冲突冲突) 14 4576 平方探查法建立哈希表平方探查法建立哈希表 (d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, 平方探查地址序列：平方探查地址序列： 将所有哈希地址相同的记录都链接在同一单将所有哈希地址相同的记录都链接在同一单

29、链表中。链表中。 哈希表中的每个存储单元中不再存放数据元哈希表中的每个存储单元中不再存放数据元 素而是存放相应单链表的头指针素而是存放相应单链表的头指针. 例例:给定关键字给定关键字19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函数为哈希函数为 H(key) = key % 7 链地址法链地址法 例例:给定关键字给定关键字 19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函数为哈希函数为 H(key) = key % 7 链地址法链地址法 14 11 198268 55 36 1 23 0 1 2 5 4 3 6 哈希查找 哈希表的查找过程和建

30、表的过程相似，按哈希存储哈希表的查找过程和建表的过程相似，按哈希存储 的方法进行查找。的方法进行查找。 假设给定的关键字为假设给定的关键字为k: 根据建表时构造的哈希函数根据建表时构造的哈希函数h，计算出哈希地址，计算出哈希地址 h(k)，如果哈希表中该地址单元为空，则查找，如果哈希表中该地址单元为空，则查找 失败。失败。 否则，将该地址中记录的关键字与给定值比较，否则，将该地址中记录的关键字与给定值比较， 如果相等，则查找成功；如果不等，则按建表如果相等，则查找成功；如果不等，则按建表 时设定的处理冲突方法查找下一个地址。如此时设定的处理冲突方法查找下一个地址。如此 反复下去，直到某个地址单

31、元为空（查找失败）反复下去，直到某个地址单元为空（查找失败） 或者关键字比较相等（查找成功）为止。或者关键字比较相等（查找成功）为止。 排序的基本概念排序的基本概念 排序排序：将文件中的记录按排序码非递减：将文件中的记录按排序码非递减(或非递增或非递增) 的顺序重新排列。的顺序重新排列。 排序码排序码：数据元素中的一个或多个数据项。排序码：数据元素中的一个或多个数据项。排序码 可以是关键字，也可以是其他若干数据项的组合。可以是关键字，也可以是其他若干数据项的组合。 排序算法的稳定性排序算法的稳定性：如果在待排序的元素序列中，：如果在待排序的元素序列中， 存在着多个排序码相同的元素，按照某种排序

32、算法存在着多个排序码相同的元素，按照某种排序算法 排序后，这些元素的相对位置仍保持不变，则称该排序后，这些元素的相对位置仍保持不变，则称该 排序算法是稳定的，否则就是不稳定的。排序算法是稳定的，否则就是不稳定的。 待排序数据：待排序数据：18 12 10 12 30 16 排序后数据：排序后数据：10 12 12 16 18 30 稳定稳定 排序后数据：排序后数据：10 12 12 16 18 30 不稳定不稳定 插入排序插入排序 基本思想：把元素ei(0in) 依次插入到 由S中前i个元素组成的已经排好序的序列 e0, e1, ,ei-1的适当位置上，插入后S的 前i+1个元素仍为有序。 直

33、接插入排序直接插入排序 以顺序查找的办法找到要插入的元素在已排好 序的元素序列中应处的位置。 所有元素分成两个集合：已排序记录集和待排 序记录集。初始时，已排序记录集只有一个元 素，即e0，待排序记录集是所有剩余元素。然 后每次从待排序记录集中选取一个元素，使用 顺序查找的方法，找到其在已排序记录集中的 位置，将其插入到该位置，直到待排序记录集 为空。 直接插入排序直接插入排序 把把n n个元素的序列划分为两个子序列：一个为有序；另一个为无序个元素的序列划分为两个子序列：一个为有序；另一个为无序 将无序子序列中的元素依次取出插入到有序子序列中，直到无序子将无序子序列中的元素依次取出插入到有序子

34、序列中，直到无序子 序列为空，整个排序结束。序列为空，整个排序结束。 若待排序数据元素的排序码序列是（若待排序数据元素的排序码序列是（1818，1212，1010，1212，3030，1616） 16 30 12 10 12 16 30 12 10 30 18 12 12 10 16 30 12 16 30 16 18 12 18 12 10 18 12 12 10 18 18 30 16 12 12 10 第第1趟趟 第第2趟趟 第第3 3趟趟 第第4 4趟趟 第第5趟趟 初始状态初始状态 未排序未排序 已排序已排序 直接插入排序直接插入排序 例：例：待排序记录为待排序记录为50,20,75

35、,34,40 3440752050 直接插入排序直接插入排序 直接插入排序的函数模板示例：直接插入排序的函数模板示例： template void InsertionSort(T A, int n)/对对A0An-1排序排序 int i , j; T temp; for( i = 1 ; i 0 j- ) Aj = Aj-1; Aj = temp; 算法分析算法分析 时间复杂度与元素的初始状态有关时间复杂度与元素的初始状态有关 初态为正序时（最好情形）复杂度为初态为正序时（最好情形）复杂度为O(n) 初态为逆序时（最坏情形）复杂度是O(n2) 直接插入排序的平均时间复杂度是O(n2) 直接插入

36、排序是稳定的排序算法 适用于一个长度较短、接近有序的序列 3440752050 5040207534 二分插入排序二分插入排序 在插入ei时，e0, e1, , ei-1是一个有序序 列，所以可以用二分查找法寻找ei的插入 位置，从而减少比较次数。 二分插入排序是稳定的排序算法，其平均 时间复杂度仍是O(n2) 二分插入排序的函数模板示例：二分插入排序的函数模板示例： template void InsertionSort( T A , int n ) /对对0An-1排序排序 int i , j , low , high , mid; T temp; for(i = 1 ; i n ; i+

37、 ) temp = ai; low = 0; high = i - 1; while(low = high) mid = (low + high) / 2; if( temp = low ; j-) Aj+1 = Aj; Alow = temp; 选择排序选择排序 基本思想：每次从待排序的元素序列中 选择一个最小的元素将其附加到已排好 序的元素序列的后面，直至全部元素排 好序为止。 在初始时，已排好序的元素序列为空， 待排序的元素序列中包括了需要排序的 所有元素。 直接选择排序直接选择排序 基本思想：用逐个比较的办法从待排序 的元素序列中选出最小的元素。依次对 i=0, 1, 2, ,n-2分

38、别执行如下的选择和交 换步骤：在元素序列ei, ei+1, , en-1中选 择出最小的元素ek；当ki时，交换ei与ek 的值。经上述n-1次的选择和交换后，排 序工作即已完成。 直接选择排序直接选择排序 用逐个比较的办法从待排序的元素序列中 选出最小的元素。 直接选择排序直接选择排序 第第1 1步：在步：在n n个数据元素中找出排序码最小的数据个数据元素中找出排序码最小的数据 元素，与第元素，与第1 1个元素交换个元素交换 第第2 2步：在步：在n-1n-1个数据元素中找出排序码最小的数个数据元素中找出排序码最小的数 据元素，与第据元素，与第2 2个元素交换个元素交换 第第i i步：在步：

39、在n-i+1n-i+1个数据元素中找出排序码最小的个数据元素中找出排序码最小的 数据元素，与第数据元素，与第i i元素交换元素交换 未排序未排序 已排序已排序 1630181012 16301812 3016121210 163018 1630 18 1210 121210 18121210 12 183016121210 第第1趟趟(i=0) 第第2趟趟(i=1) 第第3趟趟(i=2) 第第4 4趟趟(i=3) 第第5趟趟(i=4) 初始状态初始状态 直接选择排序直接选择排序 直接选择排序函数模板：直接选择排序函数模板： 直接选择排序算法是不稳定算法，其平均时间复杂直接选择排序算法是不稳定算

40、法，其平均时间复杂 度为度为O(n2)，时间复杂度与元素的初态无关，时间复杂度与元素的初态无关 template void SelectionSort(T A , int n)/对对A0An-1排序排序 int i , j , k , temp; for(i = 0 ; i n-1 ; i+) /n-1趟选择趟选择 k = i; /假定假定Ai最小最小 for( j = i + 1 ; j n ; j+ ) if( Aj Ak ) k = j; /记当前最小元素的下标记当前最小元素的下标 if(k != i) /Ai不是最小，与不是最小，与Ak交换交换 temp = Ai; Ai = Ak;

41、Ak = temp; 冒泡排序冒泡排序 基本思想： 从待排序记录集的一端（这里假定为低端）对相邻 的两个元素（e0和e1，e1和e2，en-2和en-1）依次比较 它们的排序码，若不符合排序的顺序要求，就将相应 的两个元素互换，此过程称为一趟冒泡排序，最多经 过n-1趟冒泡排序，排序工作即可完成。 每趟排序的结果是将待排序记录集中排序码最大的 元素交换到待排序记录集最后一个元素的位置。假设 在一趟冒泡排序时，从ej+1以后没有发生元素的互换， 则说明ej+1以后的元素是已经排好序的，下面只需要在 e0到ej范围内进行新一趟的冒泡排序，即待排序记录集 是从e0到ej，下一趟只需从e0到ej范围内

42、进行。 冒泡排序（交换排序）冒泡排序（交换排序） 冒冒 泡泡 排排 序序 76654913582797 第一趟第一趟 第三趟第三趟 第四趟第四趟 第二趟第二趟 97766549135827 97766558491327 97766558492713 97766558492713 97766558492713 97766558492713 第五趟第五趟 第六趟第六趟 初始状态初始状态 #include void main() int a10; for(int i= 0 ; i ai; int temp; for(i = 0 ; i 10; i+) for(int j = 0 ; j aj+1)

43、temp = aj; aj = aj+1; aj+1= temp; #include void main() int a10; for(int i = 0; i ai; bool change = true; int temp; for(i = 0 ; i 10 i+) change = false; /标志置为假，假设未交换 for(int j = 0 ; j aj+1) temp = aj; aj = aj+1; aj+1 = temp; change = true; /标志置为真,有 交换 算法分析算法分析 时间复杂度与元素的初始状态有关。 最好情况下的时间复杂度为O(n)。若待排序 元

44、素序列已经有序，则排序工作经一趟处理 就可结束。此时，对元素排序码的比较次数 为最小值n-1，且没有元素的互换。 最坏情况下的时间复杂度为O(n2)。若待排序 元素序列为逆序，则需要进行n-1趟冒泡。 每趟要进行n-i-1次排序码的比较和n-i-1次元 素的互换。 平均时间复杂度为O(n2)。 冒泡排序算法是稳定的。 97 27 58 13 49 65 76 待 排 序 记 录 LastExchangeIndex 27 97 58 13 49 65 76 27 58 97 13 49 65 76 27 58 13 97 49 65 76 27 58 13 49 97 65 76 27 58 13 49 65 97 76 27 58 13 49 65 76 97 待 排 序 记 录 第一趟排序结束第一趟排序结束 27 58 13 49 65 76 97 待 排 序 记 录 已排序记录 27 58 13 49 65 76 97 待 排 序 记 录 27 58 13 49 65 76 97 27 13 58 49 65 76 97 27 13 49 58 65 76 97 27 13 49 58 65 76 97 27 13 49 58 65 76 97 第二趟排序结束