VB教程——排序算法复习

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,*,*,排序问题,1,、冒泡法,(,起泡法,),2,、顺序交换法,3,、选择法,4,、插入法,1,、冒泡法,首先我们来看,把最大的那个数放在最后位置上,的方法：,假设有,5,个数，分别为,10,，,2,，,6,，,7,，,4,，存放在,a(1)-a(5),中。,首先，从,a(1),到,a(5),，,相邻的两数,两两进行比较，在每次比较过程中，若前一个数比后一个数大，则交换两元素的内容。,第一轮的比较过程：,for j=1 to 4,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,1,、冒泡法,现在重复上述算法：把,a(1),到,a(4),中的最大数放在,a(4),中，,a(1),到,a(3),中的最大数放在,a(3),中，,a(1),与,a(2),中的最大数放在,a(2),中。这样一共经过,4,次选大就把,a(1),到,a(5),中的数进行由小到大排序。,在排序过程中小数象气泡一样上浮，而大数逐个下沉，所以叫起泡法。,第,1,轮：,for j=1 to,4,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,第,2,轮：,for j=1 to,3,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,第,3,轮：,for j=1 to,2,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,第,4,轮：,for j=1 to,1,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,第,i,轮：,for j=1 to,5-i,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,For i=1 to 4,Next i,1.,冒泡法,冒泡法程序清单：,Dim a(1 To 5)As Integer,For i=1 To 5,a(i,)=,Val(InputBox,(,输入一个数,),Next i,For i=1 to 4,For j=1 To 5-i,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t,End if,Next j,Next i,For i=1 To 5,Print,a(i,);,Next i,冒泡排序,思考：如果这,5,个数是,2,，,4,，,6,，,7,，,10,，简述程序执行流程。,1.,冒泡法,改进算法,:,Dim a(1 To 5)As Integer,For i=1 To 5,a(i,)=,Val(InputBox,(,输入一个数,),Next i,For i=1 to 4,flag=0,For j=1 To 5-i,if,a(j,)a(j+1)Then,t=,a(j,):,a(j,)=a(j+1):a(j+1)=t:,flag=1,End if,Next j,If flag=0 Then Exit For,Next i,For i=1 To 5,Print,a(i,);,Next i,1.,冒泡法,对已知存放在数组中的,n,个数，用冒泡法按,递增顺序,排序。,(1),从第一个元素开始，将,相邻的数比较,，若为,逆序，就交换,，比较完一轮，最大的数已沉底，成为数组中的最后一个元素,a(n,),(2),对,a(1),和,a(n-1),的,n-1,个数进行同,(1),的操作，次大的数放入,a(n-1),中，完成第二轮排序。,(3),进行,n-1,轮排序，所有的数排序完毕。,1.,冒泡法,n,个数冒泡法递增排序程序清单：,Dim a%(),i%,j%,n%,n=,InputBox,(,请输入一个正整数,),ReDim,a(1 To n),For i=1 To n,a(i,)=,Int(Rnd,*100):Print,a(i,);,Next i,For i=1 To,n-1,For j=1 To,n-i,If,a(j,),a(j,+1),Then,t=,a(j,):,a(j,)=,a(j,+1):,a(j,+1)=t,End If,Next j,Next i,Print,For i=1 To n,Print,a(i,);,Next i,2,、顺序交换法,我们再来看一种,将最小的数放在第一个位置,的算法,先设定用,a(1),存放最小值，然后用,a(1),分别与其后的每一个数,a(j)(j,=2.5),进行比较，在比较过程中如果,a(1),不是小的数，就将,a(1),与,a(j,),互换。,第一轮的比较过程,For j=2 To 5,if(a(1),a(j,)Then,t=a(1):a(1)=,a(j,):,a(j,)=t,End if,Next j,2,、顺序交换法,现在重复上述算法：把,a(2),到,a(5),中的最小数放在,a(2),中，,a(3),到,a(5),中的最小数放在,a(3),中，,a(4),与,a(5),中的最小数放在,a(4),中。这样一共经过,4,次选小就把,a(1),到,a(5),中的数进行由小到大排序。,第,1,轮：,for j=,2,to 5,if,a(1),a(j,)Then,t=a(1):a(1)=,a(j,):,a(j,)=t,End if,Next j,第,2,轮：,for j=,3,to 5,if,a(2),a(j,)Then,t=a(2):a(2)=,a(j,):,a(j,)=t,End if,Next j,第,3,轮：,for j=,4,to 5,if,a(3),a(j,)Then,t=a(3):a(3)=,a(j,):,a(j,)=t,End if,Next j,第,4,轮：,for j=,5,to 5,if,a(4),a(j,)Then,t=a(4):a(4)=,a(j,):,a(j,)=t,End if,Next j,第,i,轮：,for j=,i+1,to 5,if,a(i,),a(j,),Then,t=,a(i,):,a(i,)=,a(j,):,a(j,)=t,End if,Next j,For i=1 to 4,Next i,2,、顺序交换法,Dim a(1 To 5)As Integer,For i=1 To 5,a(i,)=,Val(InputBox,(,输入一个数,),Next i,For i=1 To 4,For j=i+1 To 5,If,a(i,),a(j,)Then,t=,a(i,):,a(i,)=,a(j,):,a(j,)=t,End if,Next j,Next i,For i=1 To 5,Print,a(i,);,Next i,顺序排序,2,、顺序交换法,对已知存放在数组中的,n,个数，用顺序交换法按,递增顺序,排序。,(1),从第一个元素开始，将它和其后的每个元素进行比较，若为逆序，就交换，比较完一轮，,a(1),成为数组中的最小的元素。,(2),对,a(2),和,a(n,),的,n-1,个数进行同,(1),的操作，次小的数放入,a(2),中，完成第二轮排序。,(3),进行,n-1,轮排序，所有的数排序完毕。,2,、顺序交换法,n,个数顺序法递增排序程序清单：,Dim a%(),i%,j%,n%,n=,InputBox,(,请输入一个正整数,),ReDim,a(1 To n),For i=1 To n,a(i,)=,Int(Rnd,*100):Print,a(i,);,Next i,For i=1 To n-1,For j=i+1 To n,If,a(,i,),a(,j,)Then,t=,a(i,):,a(i,)=,a(j,):,a(j,)=t,End If,Next j,Next i,Print,For i=1 To n,Print,a(i,);,Next i,3,、选择法,算法：不急于交换，先找出,a(1),到,a(5),中最小数所在的位置,K,，,一遍扫描完之后，再把,a(1),与,a(K,),互换。,重复此算法，只是每次重复进行比较的数列范围向后移一个位置。即第二遍从,a(2),到,a(5),中去找最小数的位置，最后把,a(2),与,a(K,),对调，第三遍从,a(3),到,a(5),中去找最小数的位置，最后把,a(3),与,a(K,),对调，,此过程重复,4,次后，即将,a,数组中的,5,个数按由小到大的顺序排好。这种排序方法叫选择法。,第,1,轮：,k=,1,for j=,2,to 5,if,a(j,),a(k,),Then k=j,Next j,if k1 then t=a(1):a(1)=,a(k):a(k,)=t,第,2,轮：,k=,2,for j=,3,to 5,if,a(j,),a(k,)Then k=j,Next j,if k2 then t=a(2):a(2)=,a(k):a(k,)=t,第,3,轮：,k=,3,for j=,4,to 5,if,a(j,),a(k,)Then k=j,Next j,if k3 then t=a(3):a(3)=,a(k):a(k,)=t,第,4,轮：,k=,4,for j=,5,to 5,if,a(j,),a(k,)Then k=j,Next j,if k4 then t=a(4):a(4)=,a(k):a(k,)=t,第,i,轮：,k=,i,for j=,i+1,to 5,if,a(j,),a(k,),Then k=j,Next j,if k,i,then t=,a(i):a(i,)=,a(k):a(k,)=t,For i=1 to 4,Next i,3,、选择法,选择排序法程序清单：,Dim a(1 To 5)As Integer,For i=1 To 5,a(i,)=,Val(InputBox,(,输入一个数,),Next i,For i=1 to 4,k=i,For j=i+1 To 5,if,a(j,),a(k,)Then k=j,Next j,if ki Then t=,a(i,):,a(i,)=,a(k,):,a(k,)=t,Next i,For i=1 To 5,Print,a(i,);,Next i,排序过程,3,、选择法,对已知存放在数组中的,n,个数，用选择法按,递增顺序,排序。,(1),从,n,个数的序列中选出最小的数，与第,1,个数交换位置；,(2),除第,1,个数外，其余,n-1,个数再按,(1),的方法选出次小的数，与第,2,个数交换位置；,(3),重复,(1)n-1,遍，最后构成递增序列。,3,、选择法,n,个数选择法递增排序程序清单：,Dim a%(),i%,j%,n%,n=,InputBox,(,请输入一个正整数,),ReDim,a(1 To n),For i=1 To n,a(i,)=,Int(Rnd,*100):Print,a(i,);,Next i,For i=1 To n,1,k=i,For j=i+1 To n,If,a(,j,)Key Then Exit For,next i,For k=9 To i Step-1,a(k,+1)=,a(k,),Next k,a(i,)=Key,For i=1 To 10,Print,a(i,);,Next i,4,插入法,插入法,2,：用上面的插入方法将一批数排序（从小到大），设数列中开始只有一个元素。,Dim x(1 To 10)As Integer,For i=1 To 10,x(i,)=,Val(InputBox,(