選擇排序算法及其程序?qū)崿F(xiàn)教學(xué)設(shè)計(jì)

1、選擇排序算法及其程序?qū)崿F(xiàn)四位大哥比身高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）第三遍冒泡共進(jìn)行（ ）次比較，（ ）次交換我來(lái)拼一拼選擇排序的基本思想 選擇排序（升序）的方法是 第1步： 找出n數(shù)組元素（d(1)d(n)中最小的數(shù)據(jù)，使它與第1個(gè)數(shù)據(jù)d(1) 交換位置。 第2步：在余下的元素d(2)d(n)中繼續(xù)找最小的數(shù)據(jù)，使它與第2個(gè)數(shù)據(jù)d(

2、2) 交換位置。 第i步：在剩下的元素（d(i)d(n) 中找出最小數(shù)，使它與第i個(gè)數(shù)據(jù)d(i)交換位置。 *代表未排序子序列中 的最小元素273632184個(gè)數(shù)選擇排序(升序)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遍排序共進(jìn)行（ ）次交換算法演示分析第 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找一找?guī)ь伾珨?shù)字與i的關(guān)系？n=4總結(jié)1用i記錄

5、選擇排序遍數(shù)總結(jié)1*第1遍選擇 ，j從2開(kāi)始到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開(kāi)始到4*第3遍選擇 ，j從4開(kāi)始到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個(gè)數(shù)呢？n個(gè)數(shù)選擇排序的基本算法For i = 1 To n-1 Next i 找出d(i)至d(n)中的最小值 將最小值與第i個(gè)數(shù)據(jù)d(i)交換位置 For j = i+1 to nNext j 外循環(huán) 內(nèi)循環(huán)程序?qū)崿F(xiàn)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試一試：利用已學(xué)的選擇排序算法，對(duì)初始數(shù)據(jù)【49,38,65,97,76,13,27,59】升序排序。原始數(shù)據(jù)第1遍第2遍第3遍第4遍第5遍第6遍第7遍4938659776132759共進(jìn)行（ ）次比較，（ ）次交換選擇排序的比較次數(shù)：n*(n-1)/2冒泡排序的比較次數(shù)：n*(n-1)/2冒泡排序的交換次數(shù):交換次數(shù)：與待排序元素的初始狀態(tài)有關(guān)，當(dāng)待排序已經(jīng)有序時(shí)，交換0次。最壞情況下