冒泡排序和选择排序ppt课件.ppt

《冒泡排序和选择排序ppt课件.ppt》由会员分享，可在线阅读，更多相关《冒泡排序和选择排序ppt课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 2YN输出输出a,b,c的值的值输入三个整数输入三个整数a,b,cab?交换交换a和和b的值的值ac？交换交换a和和c的值的值bc?交换交换b和和c的值的值YYNN开始开始结束结束算法：三个整数排序算法：三个整数排序BEGIN input a,b,c; /*输入三个

2、整数输入三个整数*/ if ab then 交换交换a和和b的值的值; if ac then 交换交换a和和c的值的值; if bc then 交换交换b和和c的值的值; print a,b,c; END西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 3算法：三个整数排序算法：三个整数排序BEGIN input a,b,c; /*输入三个整数输入三个整数*/ if ab then 交换交换a和和b的值的值; if ac then 交换交换a和和c的值的值; if bc then

3、 交换交换b和和c的值的值; print a,b,c; END算法：五个整数排序算法：五个整数排序BEGIN input a,b,c,d,e; /*输入五个整数输入五个整数*/ if ab then 交换交换a和和b的值的值; if ac then 交换交换a和和c的值的值; if ad then 交换交换a和和d的值的值; if ae then 交换交换a和和e的值的值; /*找出最大数并放在找出最大数并放在a中中*/ if bc then 交换交换b和和c的值的值; if bd then 交换交换b和和d的值的值; if be then 交换交换b和和e的值的值; /*找出第二大的数并放在

4、找出第二大的数并放在b中中*/ if cd then 交换交换c和和d的值的值; if ce then 交换交换c和和e的值的值; /*找出第三大的数并放在找出第三大的数并放在c中中*/ if de then 交换交换d和和e的值的值; /*找出第四大的数并放在找出第四大的数并放在d中中*/ print a,b,c,d,e; END推广至推广至5个个整数排序整数排序西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 4n在前面的排序算法中，存放数据的位置在前面的排序算法中，存放数据

5、的位置( (以以a a、b b、c c、d d、e e表示表示) )之间没有联系之间没有联系n下面，约定排序时数据集中存放在一段存储空间中下面，约定排序时数据集中存放在一段存储空间中n例如：下面的例如：下面的7 7个整数连续地存放在个整数连续地存放在位置位置11位置位置7 7中中1234567431891355743西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 5n简单排序方法有多种，这里我们介绍简单排序方法有多种，这里我们介绍冒泡冒泡( (起泡起泡) )排序法。排序法。n冒

6、泡排序法冒泡排序法(bubble sort)(bubble sort)的基本思想是的基本思想是: :通过对相邻元素的比较和通过对相邻元素的比较和交换，使全部记录排列有序。交换，使全部记录排列有序。n冒泡排序的过程：冒泡排序的过程：对每两个相邻的元素进行比较，若为逆序，则将对每两个相邻的元素进行比较，若为逆序，则将两者交换，这样的操作反复进行，直至全部记录都比较、交换完毕两者交换，这样的操作反复进行，直至全部记录都比较、交换完毕为止。如此经过一趟冒泡排序之后，就将关键字最大为止。如此经过一趟冒泡排序之后，就将关键字最大( (或最小或最小) )的元的元素安排在最后一个素安排在最后一个( (或第一个

7、或第一个) ) 元素的位置上。然后，对后元素的位置上。然后，对后n-1n-1个元个元素重复进行同样的操作，则将具有次大素重复进行同样的操作，则将具有次大( (或次小或次小) )元素安排在倒数元素安排在倒数( (或或正数正数) )第二个元素的位置上。重复以上过程，直至没有元素需要交换第二个元素的位置上。重复以上过程，直至没有元素需要交换时为止。至此，整个序列的记录按关键字由小到大的顺序排列完毕。时为止。至此，整个序列的记录按关键字由小到大的顺序排列完毕。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian Univers

8、ity, China 61234567431891355743n以以7 7个元素为例说明冒泡排序个元素为例说明冒泡排序n位置位置11位置位置7 7的元素初始排列如下所示的元素初始排列如下所示西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 71234567431891355743n第一步：令第一步：令位置位置1 1和位置和位置2 2的元素比较，若位置的元素比较，若位置1 1的元素大，则交换的元素大，则交换交换交换1234567184391355743n第二步：令第二步：令位置位置

9、2 2和位置和位置3 3的元素比较，若位置的元素比较，若位置2 2的元素大，则交换的元素大，则交换交换交换1234567189431355743西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 81234567189431355743n第三步：令第三步：令位置位置3 3和位置和位置4 4的元素比较，若位置的元素比较，若位置3 3的元素大，则交换的元素大，则交换交换交换1234567189134355743n第四步：令第四步：令位置位置4 4和位置和位置5 5的元素比较，若位置的元

10、素比较，若位置4 4的元素大，则交换的元素大，则交换n第五步：令第五步：令位置位置5 5和位置和位置6 6的元素比较，若位置的元素比较，若位置5 5的元素大，则交换的元素大，则交换交换交换1234567189134375543西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 91234567189134375543n第六步：令第六步：令位置位置6 6和位置和位置7 7的元素比较，若位置的元素比较，若位置6 6的元素大，则交换的元素大，则交换交换交换1234567189134374

11、355西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 101234567189134374355123456791813437435512345679131843743551234567913187434355西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 11n以以7 7个元素为例说明冒泡排序，存放每个元素的位置以序号进行标个元素为例说明冒泡排序，存放每个元素

12、的位置以序号进行标记记n经过六趟冒泡排序后，位置经过六趟冒泡排序后，位置11位置位置7 7中的元素排列如下所示中的元素排列如下所示12345677913184343551234567431891355743排序排序西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 12n7 7个元素进行冒泡排序时，个元素进行冒泡排序时，需要六趟，用需要六趟，用i i表示趟数表示趟数i 1i=6?结束结束Yi i+1N进行第进行第i趟冒泡排序趟冒泡排序开始开始西安电子科技大学计算机学院 - Scho

13、ol of Computer Science & Engineering, Xidian University, China 13n7 7个元素进行冒泡排序时，个元素进行冒泡排序时，需要六趟，用需要六趟，用i i表示趟数表示趟数i 1iaj+1则交换则交换j j+1NYnj j表示元素的位置表示元素的位置na aj j与与a aj+1j+1是相邻的元素是相邻的元素j=7-i?j=7-i?开始开始西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 14nint a7;int a7;i

14、 1iaj+1则交换则交换j j+1NYj=7-i?j=7-i?开始开始for(i = 0; i=5; i+)for(i = 0; i=5; i+) for(j = 0; j=5-i; j+) for(j = 0; j aj+1) if (aj aj+1) temp = aj; temp = aj; aj = aj+1; aj = aj+1; aj+1 = temp; aj+1 = temp; 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 15西安电子科技大学计算机学院 -

15、School of Computer Science & Engineering, Xidian University, China 161234567431891355743n以以7 7个元素为例说明选择排序个元素为例说明选择排序n位置位置11位置位置7 7的元素初始排列如下所示的元素初始排列如下所示西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 171234567431891355743n第一趟：从第一趟：从7 7个元素中选出最小者，将其换入个元素中选出最小者，将其换入位置

16、位置1 1，过程为：令，过程为：令min_elemmin_elem表示最小元素（初值为位置表示最小元素（初值为位置1 1的元素），的元素），k k为最小元素的为最小元素的位置序号（初值为位置序号（初值为1 1），逐一比较，找出最小元素及其位置），逐一比较，找出最小元素及其位置位置位置6的元素最小的元素最小交换交换1234567743913554343西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 181234567718913554343n第二趟：从第二趟：从6 6个元素中选出

17、最小者，将其换入个元素中选出最小者，将其换入位置位置2 2，过程为：令，过程为：令min_elemmin_elem表示最小元素（初值为位置表示最小元素（初值为位置2 2的元素），的元素），k k为最小元素的为最小元素的位置序号（初值为位置序号（初值为2 2），逐一比较，找出最小元素及其位置），逐一比较，找出最小元素及其位置位置位置3的元素最小的元素最小交换交换1234567791813554343西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 19123456779181355

18、4343n第三趟：从第三趟：从5 5个元素中选出最小者，将其换入个元素中选出最小者，将其换入位置位置3 3，过程为：令，过程为：令min_elemmin_elem表示最小元素（初值为位置表示最小元素（初值为位置3 3的元素），的元素），k k为最小元素的为最小元素的位置序号（初值为位置序号（初值为3 3），逐一比较，找出最小元素及其位置），逐一比较，找出最小元素及其位置位置位置4的元素最小的元素最小交换交换1234567791318554343西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University,

19、 China 201234567791318554343n第四趟：从第四趟：从4 4个元素中选出最小者，将其换入个元素中选出最小者，将其换入位置位置4 4，过程为：令，过程为：令min_elemmin_elem表示最小元素（初值为位置表示最小元素（初值为位置4 4的元素），的元素），k k为最小元素的为最小元素的位置序号（初值为位置序号（初值为4 4），逐一比较，找出最小元素及其位置），逐一比较，找出最小元素及其位置位置位置4的元素最小的元素最小交换交换1234567791318554343西安电子科技大学计算机学院 - School of Computer Science & Enginee

20、ring, Xidian University, China 211234567791318554343n第五趟：从第五趟：从3 3个元素中选出最小者，将其换入个元素中选出最小者，将其换入位置位置5 5，过程为：令，过程为：令min_elemmin_elem表示最小元素（初值为位置表示最小元素（初值为位置5 5的元素），的元素），k k为最小元素的为最小元素的位置序号（初值为位置序号（初值为5 5），逐一比较，找出最小元素及其位置），逐一比较，找出最小元素及其位置位置位置6的元素最小的元素最小交换交换1234567791318435543西安电子科技大学计算机学院 - School of Co

21、mputer Science & Engineering, Xidian University, China 221234567791318435543n第六趟：从第六趟：从2 2个元素中选出最小者，将其换入个元素中选出最小者，将其换入位置位置6 6，过程为：令，过程为：令min_elemmin_elem表示最小元素（初值为位置表示最小元素（初值为位置6 6的元素），的元素），k k为最小元素的为最小元素的位置序号（初值为位置序号（初值为6 6），逐一比较，找出最小元素及其位置），逐一比较，找出最小元素及其位置位置位置7的元素最小的元素最小交换交换1234567791318434355西安电子

22、科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 231234567431891355743n以以7 7个元素为例，经过个元素为例，经过6 6趟选择，将元素排列有序趟选择，将元素排列有序排序排序1234567791318434355西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 24n7 7个元素进行选择排序时，个元素进行选择排序时，需要六趟，用需要六趟，用i i表示趟数

23、表示趟数i 1i=6?结束结束Yi i+1N进行第进行第i趟选择排序趟选择排序开始开始西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 25n7 7个元素进行选择排序时，个元素进行选择排序时，需要六趟，用需要六趟，用i i表示趟数表示趟数i 1i=6?结束结束Yi i+1Nnk k表示最小元素的位置表示最小元素的位置k i, j i+1 比较比较ak和和aj如果如果ajak则令则令k = jj j+1NY交换交换ak和和aj开始开始j=7?j=7?西安电子科技大学计算机学院 -

24、School of Computer Science & Engineering, Xidian University, China 26i 1i=6?结束结束Yi i+1Nk i, j i+1 比较比较ak和和aj如果如果ajak则令则令k = jj j+1NY交换交换ak和和aj开始开始j=7?j=7?nint a7;int a7;for(i = 0; i = 5; i+)for(i = 0; i = 5; i+) k = i; k = i; for(j = i+1; j = 6; j+) for(j = i+1; j aj) if (ak aj) k = j; k = j; temp = aj; temp = aj; aj = ak; aj = ak; ak = temp; ak = temp;