高中信息技术 2、选择排序课件 浙教版

1、一、复习 n 1、冒泡排序思路冒泡排序思路: :小元素从根部逐次向上浮动小元素从根部逐次向上浮动 n2 2、冒泡排序程序设计要点：（、冒泡排序程序设计要点：（1 1）基本形：）基本形： nFor i = 1 To n-1 n For j = n To i + 1 Step -1 n If d(j) d(j - 1) Then n t = p(i):p(i) = p(i - 1):p(i - 1) = t n End If n Next j nNext i 规律：从根部向上冒泡，先冒出最小，连续双规律：从根部向上冒泡，先冒出最小，连续双 循环，双循环变量值对角加一，循环体数值交换循环，双循环变量

2、值对角加一，循环体数值交换 2、冒泡排序程序设计要点 n（2）冒泡排序程序的冒泡排序程序的小小小变形小变形： nFor j =2 to n n For i = n To j Step -1 n If p(i) d(j) then k=j Next j If k不等于不等于1时，交换时，交换d(1)和和d(k) 交换交换d(1)与与d(4) 第2遍选择 18 36 32 27 d (1) d (2) d (3) d (4) j=3 k=2 18 36 32 27 j=3 k=j 18 36 32 27j=4 k=j j=4 18 36 32 27 k=j 18 27 32 36 k=2 For

3、j=3 to 4 if d(k)d(j) then k=j Next j If k2 then 交换交换d(2)和和d(k) 第3遍选择 18 27 32 36 d (1) d (2) d (3) d (4) j=4 k=3 k=3 For j=4 to 4 if d(k)d(j) then k=j Next j If k3 then 交换交换d(3)和和d(k) 四、算法分析 n第第1 1遍选择遍选择 ，j j从从2 2开始到开始到4 4 k=1 For j=2 to 4 if d(k)d(j) then k=j Next j If k1，交换，交换d(1)和和d(k) k=2 For j=

4、3 to 4 if d(k)d(j) then k=j Next j If k2 then 交换交换d(2)和和d(k) n第第2 2遍选择遍选择 ，j j从从3 3开始到开始到4 4 n第第3 3遍选择遍选择 ，j j从从4 4开始到开始到4 4 k=3 For j=4 to 4 if d(k)d(j) then k=j Next j If k3 then 交换交换d(3)和和d(k) 用i来表示次数 的变化 For i=1 to 3 K=i 因为循环变量的值在因为循环变量的值在 循环体内不能随意改变循环体内不能随意改变 For j=i +1 to 4 五、程序实现 For i = 1 To

5、 n- 1 选择第选择第i个作为最小的数个作为最小的数 k = i For j = i + 1 To n 如果找到更小的，用如果找到更小的，用k记住它的编号记住它的编号 If d(k) d(j) Then k = j 注意：注意：d(k)与与d(j)比较比较 Next j 特点：平行加一，下标跟随，数值交换，特点：平行加一，下标跟随，数值交换，小数上冒小数上冒。 选择排序基本形选择排序基本形 If k i Then 如果最小的数所在的位置不是如果最小的数所在的位置不是i，则交换，则交换 t = d(i) d(i) = d(k) d(k) =t 注意：注意： d(k)与与d(i)交换交换 End

6、 If Next i 六、六、选择排序和冒泡排序的比较选择排序和冒泡排序的比较 交换次数交换次数循环比较次数循环比较次数 冒泡冒泡=(n-1)*n/2(n-1)+3+2+1 选择选择=n-1(n-1)+3+2+1 以以n个数据为例个数据为例:(运行比较程序运行比较程序) 冒泡：冒泡：从根部向上冒泡，逐个交换，先冒出最小，从根部向上冒泡，逐个交换，先冒出最小， 升序排序。升序排序。 选择：选择：从顶部向下找较小数的下标，找到最小的数从顶部向下找较小数的下标，找到最小的数 再交换至前，升序排序。再交换至前，升序排序。 选择排序是冒泡排序的改进。选择排序是冒泡排序的改进。 七、选择排序的变形 For i= n To 2 Step -1 Max = i 选择第选择第i个作为最大的数个作为最大的数 For j = 1 To i-1 如果找到更大的，用如果找到更大的，用max记住它的编号记住它的编号 If d(Max) d(j) Then Max = j d(min)与与d(j)比较比较 Next j If Max i Then 如果最大的数所在的位置不是如果最大的数所在的位置不是i，则交换，则交换 k = d(i) d(i) = d(Max) d(Max) = k d(max)与