专题21 排序算法（课件）-高考信息技术一轮复习考点扫描（浙江专用）(共44张PPT)

专题二十一 排序算法 1 PART 01 冒泡排序 2 基本思想 在一列数据中把较小(大)的数据逐次向上推移的一种排序技术。该算法的基本思想是把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小(大)的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一趟加工。当第一趟加工完成时，最小(大)的数据已经上升到第一个元素的位置。然后对余下的n－1个元素重复上述处理过程，直至最后余下两个数据的比较和交换。 由于每一趟加工都是将本趟最小(大)的数元素像气泡一样浮至本趟的顶端位置，所以称作冒泡排序。 排序过程 n个数的冒泡排序算法 For i=1 To n-1 'i记录正在执行的排序的遍数，由1变到n-1 For j=n To i+1 step -1 'j记录一遍处理过程中，当前数 组元素下标，由n变到i+1 If d(j) < d(j-1) Then '如果d(j)比d(j-1)小 k=d(j)：d(j)=d(j-1)：d(j-1)=k 'd(j)与d(j-1)互换 Endif Next j Next i 升序 n个数的冒泡排序算法（降序） For i= 1 to n-1 For j= n to i+1 step -1 if d(j) >d(j-1) then t=d(j) : d(j)=d(j-1) : d(j-1)=t End if Next j Next i For i= 1 to n-1 For j= 2 to n+1-i if d(j) <d(j-1) then t=d(j) : d(j)=d(j-1) : d(j-1)=t End if Next j Next i 变形1 For i= 1 to n-1 For j= 1 to n-i if d(j) >d(j+1) then t=d(j) : d(j)=d(j+1) : d(j+1)=t End if Next j Next i 变形2 For i= n to 2 step -1 For j= 1 to i-1 if d(j) >d(j+1) then t=d(j) : d(j)=d(j+1) : d(j+1)=t End if Next j Next i 变形3 For i= 1 to n-1 For j= i+1 to n if d(i) >d(j) then t=d(i) : d(i)=d(j) : d(j)=t End if Next j Next i 变形4 For i= n to 2 step -1 For j= 1 to i-1 if d(j) >d(i) then t=d(j) : d(j)=d(i) : d(i)=t End if Next j Next i 变形5 For i = 1 To n - 1 Flag=True '内层循环之前没有相邻数据的交换 For j = n To i + 1 Step -1 If a(j) < a(j - 1) Then t = a(j)：a(j) = a(j - 1)：a(j - 1) = t flag=False '有了相邻数据的交换，改变标记变量 End If Next j If flag=True then Exit for Next i 优化1 当某一轮冒泡排序没有任何数据交换，则说明数组已然有序，后面的轮次可以省略 Do while left<right  For j=