《高中信息技术 2、选择排序课件 浙教版》由会员分享，可在线阅读，更多相关《高中信息技术 2、选择排序课件 浙教版（12页珍藏版）》请在金锄头文库上搜索。
1、一、复习n 1、冒泡排序思路冒泡排序思路: :小元素从根部逐次向上浮动小元素从根部逐次向上浮动n2 2、冒泡排序程序设计要点：（、冒泡排序程序设计要点：（1 1）基本形：）基本形： nFor i = 1 To n-1n For j = n To i + 1 Step -1n If d(j) d(j - 1) Thenn t = p(i):p(i) = p(i - 1):p(i - 1) = t n End Ifn Next jnNext i 规律：从根部向上冒泡，先冒出最小，连续双规律：从根部向上冒泡，先冒出最小，连续双循环，双循环变量值对角加一，循环体循环，双循环变量值对角加一，循环体数值交
2、换数值交换2、冒泡排序程序设计要点n（2）冒泡排序程序的冒泡排序程序的小小小变形小变形：nFor j =2 to nn For i = n To j Step -1n If p(i) d(j) then k=jNext jIf k不等于不等于1时，交换时，交换d(1)和和d(k)交换交换d(1)与与d(4)第2遍选择18363227d (1) d (2) d (3) d (4) j=3k=2 18363227j=3k=j 18363227j=4k=j j=418363227k=j 18273236k=2For j=3 to 4 if d(k)d(j) then k=jNext jIf k2 t
3、hen 交换交换d(2)和和d(k) 第3遍选择18273236d (1) d (2) d (3) d (4) j=4k=3 k=3For j=4 to 4 if d(k)d(j) then k=jNext jIf k3 then 交换交换d(3)和和d(k) 四、算法分析n第第1 1遍选择遍选择 ，j j从从2 2开始到开始到4 4k=1For j=2 to 4 if d(k)d(j) then k=jNext jIf k1，交换交换d(1)和和d(k)k=2For j=3 to 4 if d(k)d(j) then k=jNext jIf k2 then 交换交换d(2)和和d(k)n第第
4、2 2遍选择遍选择 ，j j从从3 3开始到开始到4 4n第第3 3遍选择遍选择 ，j j从从4 4开始到开始到4 4k=3For j=4 to 4 if d(k)d(j) then k=jNext jIf k3 then 交换交换d(3)和和d(k)用i来表示次数的变化For i=1 to 3 K=i 因为循环变量的值因为循环变量的值在在 循环体内不能随意改变循环体内不能随意改变For j=i +1 to 4五、程序实现 For i = 1 To n- 1 选择第选择第i个作为最小的数个作为最小的数 k = i For j = i + 1 To n 如果找到更小的，用如果找到更小的，用k记住
5、它的编号记住它的编号 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 IfNext i六、六、选择排序和冒泡排序的比较选择排序和冒泡排序的比较交换次数交换次数循环比较次数循环比较次数冒泡冒泡=(n-1)*n/2(n-1)+
6、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)与与d(i)交换交换 End IfNext I 特点：对角减一，下标跟随，数值交换，特点：对角减一，下标跟随，数值交换，大数下沉。大数下沉。八、复习题解n高考倒计时P70例4、 P74例11、 P77第5题
