对数据进行排序.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章算法的程序实现,3.4,对数据进行排序,冒泡排序法,冒泡排序法是简单的排序方法之一，它和气泡从水中往上冒的情况有些类似,，,将排序的元素看作是“气泡”，比较轻的元素要往上浮。,（1）对于数组,a,中的1至,n,个数据，先将第,n,个和第,n-1,个数据进行比较，如果,a(n)a(j)then,将,a(j-1),与,a(j),对调,Endif,Next j,（2）然后，对2至,n,个数据进行同样操作，则具有次小值的数据被安置在第2位上。,（3）重复以上过程，每次的移动都向最终排序的目标前进，直至没有数据需要交换为止。,这种排序的方法被形象地比喻成“冒泡”，在排序过程中，小的数就如气泡一般逐层上冒，而大的数逐个下沉。,For i=1 to 4,For j=5 to i+1 step -1,If a(j-1)a(j)then,T=a(j-1),A(j-1)=a(j),A(j)=t,Endif,Next j,Next i,当然，我们还可以采用：,（1）对于数组,a,中的1至,n,个数据，先将第,1,个和第2个数据进行比较，如果,a(1)a(2)，,则两个数交换位置。,然后比较第,2,个和第,3,个数据；依次类推，直到第,n-1,个数据和第,n,个数据进行比较交换，这称为一趟冒泡。这一趟最明显的效果是：将最,大,的数据传到了第,n,位。,由此还可推断出，对于,n,个数，一趟应该进行,n-1,次比较操作。算法,如下,所示：,For j=1 to 4,If a(j)a(j+1)then,将,a(j),与,a(j+1),对调,Endif,Next j,（2）然后，对1至,n-1,个数据进行同样操作，则具有次大值的数据被安置在第,n-1,位上。,（3）重复以上过程，每次的移动都向最终排序的目标前进，直至没有数据需要交换为止。,这种排序的方法被形象地比喻成“冒泡”，在排序过程中，小的数就如气泡一般逐层上冒，而大的数逐个下沉。,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,Endif,Next j,Next i,简单交换排序,（1）对于数组,a,中的1至,n,个数据，先,a(1),和,a(2),进行比较，如果,a(1)a(2)，,则两个数交换位置。,然后比较,a(1),和,a(3)；,依次类推，直到,a(1),和,a(n),进行比较交换，这称为一趟,排序,。,这一趟最明显的效果是：将最,小,的数据传到了第,1,位。,由此还可推断出，对于,n,个数，一趟应该进行,n-1,次比较操作。算法,如下,所示：,For j=2 to n,If a(1)a(j)then,将,a(1),与,a(j),对调,Endif,Next j,（2）然后，对2至,n,个数据进行同样操作，则具有次小值的数据被安置在第2位上。,（3）重复以上过程，每次的移动都向最终排序的目标前进，直至没有数据需要交换为止。,For i=1 to n-1,For j=i+1 to n,If a(i)a(j)then,将,a(I),与,a(j),交换,Endif,Next j,Next i,选择法排序,算法思想,：（1）,从,n,个数的序列中选出最小的数（递增），与第1个数交换位置。,除第1个数外，其余,n-1,个数再按（1）的方法选出次小的数，与第2个数交换位置；,重复（1）,n-1,遍，最后构成递增序列。,For i=1 To n-1,进行,n-1,遍比较,k=i,对第,i,遍比较时，初始假定第,i,个元素最小,For j=i+1 To n,在数组,in,个元素中选出的最小元素与第,i,个元素交换,If a(j)a(k)Then k=j,Next j,t=a(i),a(i)=a(k),a(k)=t,Next i,练习：随机产生10个整数，并用冒泡法排序（从小到大）。,