浙江技術選考冒泡排序復習策略

姚春

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

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

那么，有幾個細節的地方，是需要我們幫助學生進行理解的。

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

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

2.冒泡排序中趟數、比較次數和交換次數的理解和區別

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

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

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

在學習當中，只要我們理解了趟數，比較次數和交換交數。根據三者關系，可以很方便推導出冒泡排序VB程序段，更有助于我們更靈活的掌握應用。

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

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

如果我們按照基本算法，循環條件a（j）>a（j+1），j初值從1開始，前數a（j）大于后數a（j+1）交換，小數交換到前面，升序，外循環3次，可以排好3個最小數，所以選到A。當然選錯了，因為對從前往后排序的理解不對。我們來看，從前往后，從a（1）開始，a（1）和a（2）比交換，如果a（1）大于a（2）交換，這次交換只是把a（1）和a（2）兩數中相對小的數交換到a（1），并不是把數組中所有最小的數交換到a（1）的位置，而a（2）是兩數中交換后相對較大的數，然后a（2）和a（3），a（3）和a（4），a（4）和a（5），a（5）和a（6）比較交換，兩都比較大的數交換到后一位置。所以，雖然是升序，但第一趟，確定的卻是最大數，放在數組中最后一個位置。所以上題中應選B這個答案。總結一下，冒泡排序，從后往前，升序首先確定的是最小值，放在數組第一個位置。從前往后，還是升序首先確定的是最大值，放在數組中最后一個位置，其從前往后的程序段如圖。

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