选择排序算法及其程序实现教学设计

1、选择排序算法及其程序实现四位大哥比身高27363218d(1)27272718d(2)36361827d(3)32183636d(4)18323232d(1)1818d(2)2727d(3)3232d(4)3636（1）第一遍冒泡d(1)181818d(2)272727d(3)363232d(4)323636（2）第二遍冒泡（3）第三遍冒泡共进行（ ）次比较，（ ）次交换我来拼一拼选择排序的基本思想 选择排序（升序）的方法是 第1步： 找出n数组元素（d(1)d(n)中最小的数据，使它与第1个数据d(1) 交换位置。 第2步：在余下的元素d(2)d(n)中继续找最小的数据，使它与第2个数据d(

2、2) 交换位置。 第i步：在剩下的元素（d(i)d(n) 中找出最小数，使它与第i个数据d(i)交换位置。 *代表未排序子序列中 的最小元素273632184个数选择排序(升序)d(1)2718d(2)3636d(3)3232d(4)1827d(1)1818d(2)2727d(3)3232d(4)3636（1）第1遍排序d(1)1818d(2)3627d(3)3232d(4)2736（2）第2遍排序（3）第3遍排序共进行（ ）次交换算法演示分析第 1 遍 选择18363227k=1For j=2 to 4 if d(k)d(j) then k=jNext j 交换d(1)和d(k) 27363

3、218d (1) d (2) d (3) d (4) j=2k=127363218j=3k=1 27363218j=4k=j 15363227j=2Min=1j=3j=4If k1 then第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 then 交换d(2)和d(k) 第3遍选择18273236d (1) d (2) d (3) d (4) j=4k=3

4、k=3For j=4 to 4 if d(k)d(j) then k=jNext jIf k3 then 交换d(3)和d(k) k=1For j=2 to 4 if d(k)d(j) then k=jNext jIf k1 then 交换d(1)和d(k)27363218k=2For j=3 to 4 if d(k)d(j) then k=jNext jIf k2 then 交换d(2)和d(k) k=3For j=4 to 4 if d(k)d(j) then k=jNext jIf k3 then 交换d(3)和d(k) i=1i=2i=3找一找带颜色数字与i的关系？n=4总结1用i记录

5、选择排序遍数总结1*第1遍选择 ，j从2开始到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)*第2遍选择 ，j从3开始到4*第3遍选择 ，j从4开始到4k=3For j=4 to 4 if d(k)d(j) then k=jNext jIf k3 then 交换d(3)和d(k)For i=1 to 3k=ifor j=i+1 to 4 if d(k)d(j)then k=jnext jif k

6、 i then 交换d(i)和d(k)end ifNext i如果是 n个数呢？n个数选择排序的基本算法For i = 1 To n-1 Next i 找出d(i)至d(n)中的最小值 将最小值与第i个数据d(i)交换位置 For j = i+1 to nNext j 外循环 内循环程序实现For i = 1 To n - 1 k = i For j = i + 1 To n If d(k) d(j) Then k = j endif Next j If k i Then t = d(i) d(i) = d(k) d(k) = t End IfNext i试一试：利用已学的选择排序算法，对初始数据【49,38,65,97,76,13,27,59】升序排序。原始数据第1遍第2遍第3遍第4遍第5遍第6遍第7遍4938659776132759共进行（ ）次比较，（ ）次交换选择排序的比较次数：n*(n-1)/2冒泡排序的比较次数：n*(n-1)/2冒泡排序的交换次数:交换次数：与待排序元素的初始状态有关，当待排序已经有序时，交换0次。最坏情况下