浙江技術(shù)選考冒泡排序復(fù)習(xí)策略

姚春

信息技術(shù)自進(jìn)入浙江高考以來，題目難度日益增加。算法做為選考考查的重要內(nèi)容，重要性更是不言而喻，特別16、17兩道壓軸大題更是題型變化多樣，是學(xué)生得分最主要的區(qū)分點(diǎn)。所以，對算法的復(fù)習(xí)就顯得特別重要，一些考點(diǎn)頻出的內(nèi)容，如排序、對分查找、字符處理、矩陣轉(zhuǎn)換等算法，要求學(xué)生掌握基本思想，能夠靈活運(yùn)用，以適應(yīng)考試題材、題型的變化。這就要求教師在高三復(fù)習(xí)時(shí)要掌握基礎(chǔ)，注重細(xì)節(jié)，讓學(xué)生理解精髓。本文以選考中常出現(xiàn)的冒泡排序?yàn)槔?，共享?fù)習(xí)策略。

冒泡排序的基本思想是n個(gè)待排序列，相鄰兩數(shù)兩兩比較，將較小（大）的數(shù)據(jù)向前或后進(jìn)行交換，重復(fù)這一過程，直到選取排出一個(gè)最?。ù螅┑臄?shù)完成一趟，然后在進(jìn)行第二趟，第三趟，直到最后完全排好序。升序程序段如圖：

那么，有幾個(gè)細(xì)節(jié)的地方，是需要我們幫助學(xué)生進(jìn)行理解的。

1.升序、降序的理解判斷

在程序段中，n個(gè)待排序列是按照升序還是降序排列，顯然是由if語句中a（j）和a（j-1）的比較來確定的。假設(shè)條件是a（j）<=a（j-1）如何判定呢？首先我們要確定兩數(shù)在數(shù)組中的位置，j在循環(huán)中初值是n，是數(shù)組中最后一個(gè)數(shù)的下標(biāo)，a（j-1）代表前一個(gè)數(shù)，如果后一個(gè)數(shù)小于等于前一個(gè)數(shù)，把較小數(shù)交換到前一個(gè)位置，根據(jù)循環(huán)，小數(shù)不斷的被交換到前面，第一趟以后，最小數(shù)就到數(shù)組中第一個(gè)位置了，所以判定是升序。同樣，我們把條件改成a（j）>=a（j-1），大數(shù)被不斷交換到前面，所以就變成降序序列了。

2.冒泡排序中趟數(shù)、比較次數(shù)和交換次數(shù)的理解和區(qū)別

我們先來看46，31，25，27，19這5個(gè)數(shù)的冒泡升序排序過程如下圖（加粗?jǐn)?shù)據(jù)為每趟原始數(shù)據(jù)）。在排序過程，我們從最后一個(gè)數(shù)開始，與前一個(gè)數(shù)依次進(jìn)行比較，如果小于前面的數(shù)，則交換，然后在依次往前，兩兩比較，直到所有的數(shù)都比較過一次，我們把這樣由后往前完整的經(jīng)歷一次稱之為一趟（遍）。我們看到第一趟完成后，最小數(shù)19已排好，所以，每二趟不再參與排序，第二趟完成再排好一個(gè)數(shù)25，依此類推，當(dāng)?shù)谒奶藭r(shí)，排好4個(gè)數(shù)，剩下最后一個(gè)就不用排了。所以5個(gè)數(shù)總共需要4趟，那么n個(gè)數(shù)，就只需要n-1趟。

關(guān)于比較次數(shù)，我們再看在第一趟中，從后往前相鄰兩數(shù)兩兩比較，19和27，19和25，19和31，19和46，5個(gè)數(shù)完全比較完需要4次。第二趟，排好一個(gè)數(shù)，只剩4個(gè)數(shù)需要比較3次。所以，第三趟2次，第四趟1次。5個(gè)數(shù)總的比較次數(shù)是4+3+2+1=10次，那么n個(gè)數(shù)，就需要比較（n-1）+（n-2）+（n-3）+……+1次，根據(jù)數(shù)列求公式，得到總比較次數(shù)公式n*（n-1）/2。

最后是交換次數(shù)，在冒泡排序中，相鄰兩數(shù)進(jìn)行比較，但比較以后不一定要進(jìn)行交換。比如，第二趟的第一次比較27和25，25小于27，小數(shù)在前，所以有比較但沒有交換。在冒泡排序中，交換次數(shù)要根據(jù)排序數(shù)據(jù)實(shí)際交換情況進(jìn)行計(jì)算，交換次數(shù)最少0次，最多和比較次數(shù)一樣多，每次比較都進(jìn)行交換。

在學(xué)習(xí)當(dāng)中，只要我們理解了趟數(shù)，比較次數(shù)和交換交數(shù)。根據(jù)三者關(guān)系，可以很方便推導(dǎo)出冒泡排序VB程序段，更有助于我們更靈活的掌握應(yīng)用。

3.從前往后，從后往前的不同

我們的冒泡排序的基本算法，都是從最后一數(shù)開始，相鄰兩數(shù)進(jìn)行比較，把最小（大）值不斷向前交換的過程。既然可以從后往前，當(dāng)然也可以從前往后進(jìn)行比較交換，雖然程序結(jié)果一樣的，但中間的運(yùn)算過程卻不同。我們來看如圖程序段。

如果我們按照基本算法，循環(huán)條件a（j）>a（j+1），j初值從1開始，前數(shù)a（j）大于后數(shù)a（j+1）交換，小數(shù)交換到前面，升序，外循環(huán)3次，可以排好3個(gè)最小數(shù)，所以選到A。當(dāng)然選錯(cuò)了，因?yàn)閷那巴笈判虻睦斫獠粚ΑＮ覀儊砜?，從前往后，從a（1）開始，a（1）和a（2）比交換，如果a（1）大于a（2）交換，這次交換只是把a(bǔ)（1）和a（2）兩數(shù)中相對小的數(shù)交換到a（1），并不是把數(shù)組中所有最小的數(shù)交換到a（1）的位置，而a（2）是兩數(shù)中交換后相對較大的數(shù)，然后a（2）和a（3），a（3）和a（4），a（4）和a（5），a（5）和a（6）比較交換，兩都比較大的數(shù)交換到后一位置。所以，雖然是升序，但第一趟，確定的卻是最大數(shù)，放在數(shù)組中最后一個(gè)位置。所以上題中應(yīng)選B這個(gè)答案?？偨Y(jié)一下，冒泡排序，從后往前，升序首先確定的是最小值，放在數(shù)組第一個(gè)位置。從前往后，還是升序首先確定的是最大值，放在數(shù)組中最后一個(gè)位置，其從前往后的程序段如圖。

綜上所述，只要我們掌握了冒泡排序的基本思想，掌握了冒泡排序的一些基本變化，例如升序，降序關(guān)鍵點(diǎn)，從前往后比較，從后往前比較的不同。再加上一些練習(xí)題進(jìn)行融會貫通，靈活應(yīng)用，相信大家對于信息技術(shù)選考中11、12、16、17題中出現(xiàn)的冒泡排序問題將不再害怕。