5.3排序算法的程序实现

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,排序算法的分析及实现,冒泡排序和选择排序,交换数据的实现,(A=3:B=5),5,C=A,5,A=B,C=A,交换数据的实现,(A=3:B=5),5,B=C,A=B,C=A,交换数据的实现,(A=3:B=5),数组,为了存储一组数据,我们需要用到数组变量,例如,dim d(1 to 1000) as integer,定义了一个整数类型的数组变量,d,下标从,1,到,1000,d(1),d(2),d(3),d(4),d(1000),27,36,32,18,16,排序的意义,排序是为了将一组杂乱的数据变成一组有序的数据。（递增或递减）,如何实现将较小数逐次从下向上推移呢？,从最后一个元素起，依次,比较相邻的两个元素,中的数据,将,较小,的数据调换到上面。,冒泡排序算法,冒泡排序法是,简单,的排序方法之一，它和气泡从水中往,上冒的情况有些类似。,方法,：,是在一列数据中把较小的数逐次向上推移的一种排序技术。,原始序列,d(1),27,d(2),36,d(3),32,d(4),18,最终序列,d(1),18,d(2),27,d(3),32,d(4),36,用数组来存储一系列同类型的数据,然后调整数组中的元素,dim d(1 to 4) as integer ,定义一个数组变量,d,例：将以下四个数组元素用冒泡法进行排序,(,从小到大,),d(1)=27 d(2)=36 d(3)=32 d(4)=18,冒泡排序,d(1),27,d(2),36,d(3),32,d(4),18,空椅子,d(1),27,d(2),36,d(3),32,d(4),空椅子,18,空椅子,18,空椅子,d(1),27,d(2),36,d(3),d(4),32,d(1),27,d(2),36,d(3),18,d(4),32,两个数进行数据交换,就象两杯水进行交换,需要再拿一个空杯,d(1),27,d(2),36,d(3),18,d(4),32,（,1,）第一遍冒泡（最小数冒到最上面）,d(1),27,d(2),36,d(3),18,d(4),32,空椅子,d(1),27,d(2),18,d(3),36,d(4),32,空椅子,空椅子,空椅子,d(1),27,d(2),18,d(3),36,d(4),32,d(1),18,d(2),27,d(3),36,d(4),32,（,1,）第一遍冒泡（最小数冒到最上面）,d(1),27,27,27,18,d(2),36,36,18,27,d(3),32,18,36,36,d(4),18,32,32,32,（,1,）第一遍冒泡,d(1),18,18,18,d(2),27,27,27,d(3),36,32,32,d(4),32,36,36,（,2,）第二遍冒泡,d(1),18,18,d(2),27,27,d(3),32,32,d(4),36,36,（,3,）第三遍冒泡,d(1),27,d(2),36,d(3),32,d(4),18,（,1,）第一遍冒泡,27,36,18,32,27,18,36,32,18,27,36,32,4,3,3,2,2,1,if d(4)d(3) then,交换,d(4),和,d(3),的值,j,j-1,if d(3)d(2) then,交换,d(3),和,d(2),的值,if d(2)d(1) then,交换,d(2),和,d(1),的值,For j=4 to 2 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,j,j-1,j,j-1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,通项式,d(1),18,d(2),27,d(3),36,d(4),32,（,2,）第二遍冒泡,18,27,32,36,18,27,32,36,4,3,3,2,For j=4 to 3 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,j,j-1,18,27,32,36,（,3,）第三遍冒泡,18,27,32,36,4,3,For j=4 to 4 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,d(1),27,27,27,18,d(2),36,36,18,27,d(3),32,18,36,36,d(4),18,32,32,32,（,1,）第一遍冒泡,d(1),18,18,18,d(2),27,27,27,d(3),36,32,32,d(4),32,36,36,（,2,）第二遍冒泡,d(1),18,18,d(2),27,27,d(3),32,32,d(4),36,36,（,3,）第三遍冒泡,For j=4 to 2 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,For j=4 to 3 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,For j=4 to 4 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,For j=4 to 2 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,For j=4 to 3 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,For j=4 to 4 step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,第一遍,第二遍,第三遍,J,从,4,到,2,J,从,4,到,3,J,从,4,到,4,i=1,i=2,i=3,i=1,2,3,For j=4 to,i+1,step -1,if d(j)d(j-1) then,交换,d(j),和,d(j-1),的值,Next j,For i = 1 To 3(num-1),Next i,For j = 4(num) To i + 1 Step -1,Next j,If d(j) d(j - 1) Then,End If,k = d(j): d(j) = d(j - 1): d(j - 1) = k,Num:,数组元素的个数,问：,5,个数比较怎么改？,交换,d(j),和,d(j-1),的值,算法分析,以,i,表示次数,练习：,随机产生,10,个整数，并用冒泡法排序（从小到大）。,（从后往前,小的数向前,上升）,Dim a(1 To 10) As Integer,Dim i,j, t As Integer,Print ,排序前：,Randomize,For,i = 1 To 10,a(i) = Int(Rnd * 100),Print a(i);,Next,i,For,j = 1 To 9,For,i = 10 To j+1 Step -1,If a(i) a(i - 1) Then,t = a(i),a(i) = a(i - 1),a(i - 1) = t,End If,Next,i,Next,j,Print,Print ,排序后：,For i = 1 To 10,Print a(i);,Next i,第一遍,:j=1,a(10),与,a(9),比较后,(,如果,a(10),小于,a(9),进行互换处理,。）,a(9),与,a(8),比较后处理,a(2),与,a(1),比较后处理,第二遍,:j=2,a(10),与,a(9),比较后处理,a(3),与,a(2),比较后处理,第三遍,:j=3,.,第九遍,:j=9,a(10),与,a(9),比较后处理,j=10,循环结束。,10,个数排序的核心代码,For,j = 1 To 9,For,i = 10 To j+1 Step -1,If a(i) d(j) then min=j,Next j,If min,不等于,1,时，交换,d(1),和,d(min),第,2,遍选择,18,36,32,27,d (,1,),d (2),d (3),d (4),j=3,Min=,2,18,36,32,27,j=3,Min=,j,18,36,32,27,j=4,Min=,j,j=4,18,36,32,27,Min=,j,18,27,32,36,Min=2,For j=3 to 4,if d(min)d(j) then min=j,Next j,If min2 then,交换,d(2),和,d(min),第,3,遍选择,18,27,32,36,d (,1,),d (2),d (3),d (4),j=4,Min=,3,Min=3,For j=4 to 4,if d(min)d(j) then min=j,Next j,If min3 then,交换,d(3),和,d(min),分析,第,1,遍选择 ，,j,从,2,开始到,4,Min=,1,For j=,2,to 4,if d(min)d(j) then min=j,Next j,If min,1,，交换,d(,1,),和,d(min),Min=,2,For j=,3,to 4,if d(min)d(j) then min=j,Next j,If min,2,then,交换,d(,2,),和,d(min),第,2,遍选择 ，,j,从,3,开始到,4,第,3,遍选择 ，,j,从,4,开始到,4,Min=,3,For j=,4,to 4,if d(min)d(j) then min=j,Next j,If min,3,then,交换,d(,3,),和,d(min),用,i,来表示次数的变化,程序实现,For,i,= 1 To 3,（,num - 1,）,选择第,i,个最小的数,Min =,i,For,j =,i,+ 1 To 4,（,num,）,如果找到更小的，用,min,记住它的编号,If d(Min) d(j) Then Min = j,Next,j,If Min ,i,Then ,如果最小的数所在的位置不是,i,，则交换,temp = d(i),d(i) = d(Min),d(Min) = temp,End If,Next,i,数组元素的个数,练习：随机产生,10,个整数，并用选择排序算法排序（,从小到大,）。,Dim a(1 To 10) As Integer,Dim i,j, k,t As Integer,Print ,排序前：,Randomize,For,i = 1 To 10,a(i) = Int(Rnd * 100),Print a(i);,Next,i,For,j = 1To 9,k=j,For,i = j+1 To 10,If a(i)a(k) then k=i,Next,i,IF jk then,t=a(j):a(j)=a(k):a(k)=t,End if,Next,j,Print,Print ,排序后：,For,i = 1 To 10,Print a(i);,Next,i,第一遍,:j=1,k=j,即,k=1,数组,a,里面,a(1),到,a(10)10,个元素比较大小，找到最小的元素,a(i),让,k=i(,小循环作用,),退出小循环后，交换,a(1),与,a(k),的值。,第二遍,:j=2,k=j,即,k=2,数组,a,里面,a(2),到,a(10)9,个元素比较大小，找到最小的元素,a(i),让,k=i(,小循环作用,),退出小循环后，交换,a(2),与,a(k),的值。,第三遍,:j=3,.,第九遍,:j=9,k=j,即,k=9,数组,a,里面,a(9),到,a(10)2,个元素比较大小，找到最小的元素,a(i),让,k=i(,小循环作用,),退出小循环后，交换,a(9),与,a(k),的值。,j=10,循环结束。,练习：随机产生,10,个整数，并用选择排序算法排序（,从小到大,）。,Dim a(1 To 10) As Integer,Dim i,j, k,t As Integer,Print ,排序前：,Randomize,For,i = 1 To 10,a(i) = Int(Rnd * 100),Print a(i);,Next,i,For,j = 1To 9,k=j,For,i = j+1 To 10,If a(i)a(k) then k=i,Next,i,IF jk then,t=a(j):a(j)=a(k):a(k)=t,End if,Next,j,Print,Print ,排序后：,For,i = 1 To 10,Print a(i);,Next,i,Dim a(1 To 10) As Integer,Dim i,j, t As Integer,Print ,排序前：,Randomize,For,i = 1 To 10,a(i) = Int(Rnd * 100),Print a(i);,Next,i,For,j = 1 To 9,For,i = 10 To j+1 Step -1,If a(i) a(i - 1) Then,t = a(i),a(i) = a(i - 1),a(i - 1) = t,End If,Next,i,Next,j,Print,Print ,排序后：,For i = 1 To 10,Print a(i);,Next i,选择排序算法,冒泡排序算法,要,区分,一个排序是冒泡排序还是选择排序，就,看交换是在双重循环中的哪一个循环中发生。,如果,元素交换,是在,里面,的,小循环中发生,，就是,冒泡排序,，是在,外面,的,大循环中发生,，就是,选,择排序,。,总结：,1,、下表中原始数据是一组学生的军训打靶成绩，若采用冒泡排序算法对其进行排序，则第,3,遍的排序结果是：,原始数据,第一遍,第二遍,第三遍,第四遍,98,85,85,85,95,98,88,88,85,95,98,93,93,88,95,95,88,93,93,98,85,88,93,98,95,1,有一组,数，依次为,3,、,2,、,8,、,5,、,9,，,原始数据,3,2,8,5,9,第一趟,9,2,8,5,3,第二趟,第三趟,9,8,5,2,3,第四趟,9,8,5,3,2,若采用选择排序算法对其进行从大到小排序，则第二趟的排序结果是,（,A,）,9 2 8 5 3,（,B,）,9 5 8 2 3,（,C,）,9 8 2 5 3,（,D,）,9 2 8 3 5,