冒泡排序和选择排序课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,简单排序算法,-,冒泡排序,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,1,简单排序算法-冒泡排序西安电子科技大学计算机学院-Schoo,三个整数排序,开始,输入三个整数,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,三个整数排序开始输入三个整数a,b,cab?Nac？YY,五个整数排序,算法：五个整数排序,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,五个整数排序算法：五个整数排序BEGINinputa,b,c,排序时数据集中存放在一段空间中,?,?,?,在前面的排序算法中，存放数据的位置,(,以,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,冒泡排序方法?以7个元素为例说明冒泡排序位置1位置7的元,冒泡排序方法,?,?,第一步：令,位置,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,冒泡排序方法?第一步：令位置1和位置2的元素比较，若位置1,冒泡排序方法,?,?,?,第三步：令,位置,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,冒泡排序方法?第三步：令位置3和位置4的元素比较，若位置,冒泡排序方法,?,第六步：令,位置,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,冒泡排序方法?第六步：令位置6和位置7的元素比较，若位置6的,冒泡排序方法,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,冒泡排序方法123456718913437435512345,冒泡排序方法,?,?,以,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个元素为例说明冒泡排序，存放每个元素的位,冒泡排序算法,?,7,个元素进行冒泡排序时，,需要六趟，用,i,表示趟数,开始,i 1,i=6?,N,Y,结束,进行第,i,趟冒泡排序,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,12,冒泡排序算法?7个元素进行冒泡排序时，需要六趟，用i表示趟数,冒泡排序算法,?,?,?,7,个元素进行冒泡排序时，,需要六趟，用,i,表示趟数,j,表示元素的位置,a,j,与,a,j+1,是相邻的元素,开始,i 1,i=6?,N,Y,j 1,j,a,j+1,则交换,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,13,冒泡排序算法?7个元素进行冒泡排序时，需要六趟，用i表示,冒泡排序算法,?,int a7;,开始,for(i=0;i=5;i+),for(j=0;j=5-i;j+),i 1,i aj+1),temp=aj;,aj=aj+1;,aj+1=temp;,Y,j 1,j,a,j+1,则交换,i i+1,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,14,冒泡排序算法?int a7;开始for(i=0;i,简单选择排序,西安电子科技大学计算机学院,-,School of Computer Science&Engineering,Xidian University,China,15,简单选择排序西安电子科技大学计算机学院-School of,选择排序方法,?,?,以,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位置7的元,选择排序方法,?,第一趟：从,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,选择排序方法?第一趟：从7个元素中选出最小者，将其换入位置1,选择排序方法,?,第二趟：从,6,个元素中选出最小者，将其换入,位置,2,，过程为：令,min_elem,表示最小元素（初值为位置,2,的元素），,k,为最小元素的,位置序号（初值为,2,），逐一比较，找出最小元素及其位置,1,2,3,4,5,6,7,7,18,9