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

简单排序算法,-,冒泡排序,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,1,三个整数排序,开始,输入三个整数,a,b,c,ab?,N,ac,？,Y,Y,Y,交换,a,和,b,的值,交换,a,和,c,的值,交换,b,和,c,的值,N,bc?,N,输出,a,b,c,的值,结束,算法：三个整数排序,BEGIN,input,a,b,c;,/*,输入三个整数,*/,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,2,五个整数排序,算法：五个整数排序,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,中,*/,算法：三个整数排序,BEGIN,input,a,b,c;,/*,输入三个整数,*/,if,ab,then,交换,a,和,b,的值,;,if,ac,then,交换,a,和,c,的值,;,if,bc,then,交换,b,和,c,的值,;,print,a,b,c;,END,推广至,5,个,整数排序,if,bc,then,交换,b,和,c,的值,;,if,bd,then,交换,b,和,d,的值,;,if,be,then,交换,b,和,e,的值,;,/*,找出第二大的数并放在,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,3,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,排序时数据集中存放在一段空间中,?,?,?,在前面的排序算法中，存放数据的位置,(,以,a,、,b,、,c,、,d,、,e,表示,),之间没有联系,下面，约定排序时数据集中存放在一段存储空间中,例如：下面的,7,个整数连续地存放在位置,1,位置,7,中,1,2,3,4,5,6,7,43,18,9,13,55,7,43,4,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,简单排序方法,?,?,简单排序方法有多种，这里我们介绍冒泡,(,起泡,),排序法。,冒泡排序法,(bubble sort),的基本思想是,:,通过对相邻元素的比较和,交换，使全部记录排列有序。,冒泡排序的过程：对每两个相邻的元素进行比较，若为逆序，则将,两者交换，这样的操作反复进行，直至全部记录都比较、交换完毕,为止。如此经过一趟冒泡排序之后，就将关键字最大,(,或最小,),的元,素安排在最后一个,(,或第一个,),元素的位置上。然后，对后,n-1,个元,素重复进行同样的操作，则将具有次大,(,或次小,),元素安排在倒数,(,或,正数,),第二个元素的位置上。重复以上过程，直至没有元素需要交换,时为止。至此，整个序列的记录按关键字由小到大的顺序排列完毕。,?,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,5,冒泡排序方法,?,?,以,7,个元素为例说明冒泡排序,位置,1,位置,7,的元素初始排列如下所示,1,2,3,4,5,6,7,43,18,9,13,55,7,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,6,冒泡排序方法,?,?,第一步：令,位置,1,和位置,2,的元素比较，若位置,1,的元素大，则交换,第二步：令,位置,2,和位置,3,的元素比较，若位置,2,的元素大，则交换,1,2,3,4,5,6,7,43,18,9,13,55,7,43,交换,1,2,3,4,5,6,7,18,43,9,13,55,7,43,交换,1,2,3,4,5,6,7,18,9,43,13,55,7,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,7,冒泡排序方法,?,?,?,第三步：令,位置,3,和位置,4,的元素比较，若位置,3,的元素大，则交换,第四步：令,位置,4,和位置,5,的元素比较，若位置,4,的元素大，则交换,第五步：令,位置,5,和位置,6,的元素比较，若位置,5,的元素大，则交换,1,2,3,4,5,6,7,18,9,43,13,55,7,43,1,2,3,4,5,6,7,18,9,13,43,55,7,43,1,2,交换,18,9,13,43,7,55,43,交换,3,4,5,6,7,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,8,冒泡排序方法,?,第六步：令,位置,6,和位置,7,的元素比较，若位置,6,的元素大，则交换,1,2,3,4,5,6,7,?,?,18,9,13,43,7,55,43,最大元素被交换到最后一个位置,(,位置,7),下一趟则需将次大元素交换到倒数第二个位置,1,2,3,交换,18,9,13,43,7,43,55,4,5,6,7,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,9,冒泡排序方法,1,2,3,4,5,6,7,18,9,13,43,7,43,55,1,2,3,4,5,6,7,9,18,13,43,7,43,55,1,2,3,4,5,6,7,9,13,18,43,7,43,55,1,2,3,4,5,6,7,9,13,18,7,43,43,55,?,?,次大元素被交换到倒数第二个位置,(,位置,6),下一趟则需将第三大元素交换到倒数第三个位置，依此类推,10,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,?,?,以,7,个元素为例说明冒泡排序，存放每个元素的位置以序号进行标,记,经过六趟冒泡排序后，位置,1,位置,7,中的元素排列如下所示,1,2,3,4,5,6,7,43,18,9,13,55,7,43,1,2,排序,7,9,13,18,43,43,55,3,4,5,6,7,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,11,冒泡排序算法,?,7,个元素进行冒泡排序时，,需要六趟，用,i,表示趟数,开始,i 1,i=6?,N,Y,结束,进行第,i,趟冒泡排序,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,12,冒泡排序算法,?,?,?,7,个元素进行冒泡排序时，,需要六趟，用,i,表示趟数,j,表示元素的位置,a,j,与,a,j+1,是相邻的元素,开始,i 1,i=6?,N,Y,j 1,j=7-i?,Y,比较,a,j,和,a,j+1,结束,N,j j+1,如果,a,j,a,j+1,则交换,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,13,冒泡排序算法,?,int a7;,开始,for(i=0;i=5;i+),for(j=0;j=5-i;j+),i 1,i=6?,N,if(aj aj+1),temp=aj;,aj=aj+1;,aj+1=temp;,Y,j 1,j=7-i?,Y,比较,a,j,和,a,j+1,结束,N,j j+1,如果,a,j,a,j+1,则交换,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,14,简单选择排序,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,15,选择排序方法,?,?,以,7,个元素为例说明选择排序,位置,1,位置,7,的元素初始排列如下所示,1,2,3,4,5,6,7,43,18,9,13,55,7,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,16,选择排序方法,?,第一趟：从,7,个元素中选出最小者，将其换入,位置,1,，过程为：令,min_elem,表示最小元素（初值为位置,1,的元素），,k,为最小元素的,位置序号（初值为,1,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,43,18,9,13,55,7,43,位置,6,的元素最小,交换,1,2,3,4,5,6,7,7,43,9,13,55,43,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,17,选择排序方法,?,第二趟：从,6,个元素中选出最小者，将其换入,位置,2,，过程为：令,min_elem,表示最小元素（初值为位置,2,的元素），,k,为最小元素的,位置序号（初值为,2,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,7,18,9,13,55,43,43,位置,3,的元素最小,交换,1,2,3,4,5,6,7,7,9,18,13,55,43,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,18,选择排序方法,?,第三趟：从,5,个元素中选出最小者，将其换入,位置,3,，过程为：令,min_elem,表示最小元素（初值为位置,3,的元素），,k,为最小元素的,位置序号（初值为,3,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,7,9,18,13,55,43,43,位置,4,的元素最小,交换,1,2,3,4,5,6,7,7,9,13,18,55,43,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,19,选择排序方法,?,第四趟：从,4,个元素中选出最小者，将其换入,位置,4,，过程为：令,min_elem,表示最小元素（初值为位置,4,的元素），,k,为最小元素的,位置序号（初值为,4,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,7,9,13,18,55,43,43,位置,4,的元素最小,交换,1,2,3,4,5,6,7,7,9,13,18,55,43,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,20,选择排序方法,?,第五趟：从,3,个元素中选出最小者，将其换入,位置,5,，过程为：令,min_elem,表示最小元素（初值为位置,5,的元素），,k,为最小元素的,位置序号（初值为,5,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,7,9,13,18,55,43,43,位置,6,的元素最小,交换,1,2,3,4,5,6,7,7,9,13,18,43,55,43,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,21,选择排序方法,?,第六趟：从,2,个元素中选出最小者，将其换入,位置,6,，过程为：令,min_elem,表示最小元素（初值为位置,6,的元素），,k,为最小元素的,位置序号（初值为,6,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,7,9,13,18,43,55,43,位置,7,的元素最小,交换,1,2,3,4,5,6,7,7,9,13,18,43,43,55,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,22,选择排序方法,?,以,7,个元素为例，经过,6,趟选择，将元素排列有序,1,2,3,4,5,6,7,43,18,9,13,55,7,43,排序,1,2,3,4,5,6,7,7,9,13,18,43,43,55,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,23,选择排序算法,?,7,个元素进行选择排序时，,需要六趟，用,i,表示趟数,开始,i 1,i=6?,N,Y,结束,进行第,i,趟选择排序,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,24,选择排序算法,?,7,个元素进行选择排序时，,需要六趟，用,i,表示趟数,k,表示最小元素的位置,i i+1,开始,i 1,i=6?,N,?,Y,k i,j i+1,j=7?,Y,比较,a,k,和,a,j,结束,N,j j+1,如果,a,j,a,k,则令,k=j,交换,a,k,和,a,j,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,25,选择排序算法,?,int a7;,开始,for(i=0;i=5;i+),k=i;,i 1,i=6?,N,for(j=i+1;j=6;j+),if(ak aj),k=j;,temp=aj;,aj=ak;,ak=temp;,j j+1,Y,k i,j i+1,j=7?,Y,如果,a,j,a,k,则令,k=j,交换,a,k,和,a,j,比较,a,k,和,a,j,结束,i i+1,N,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,26,