《冒泡排序算法》PPT課件

1、3.4 對(duì)數(shù)據(jù)進(jìn)行排序?qū)?shù)據(jù)進(jìn)行排序 冒泡排序冒泡排序“明日之星英語(yǔ)演講大賽” 評(píng)分出來(lái)了， 需要選出每組前三名進(jìn)入決賽。我們需要設(shè)計(jì)程序， 對(duì)選手選手成績(jī)進(jìn)行排序成績(jī)進(jìn)行排序。 那么我們應(yīng)該怎樣做呢？要解決這個(gè)問題，那么就讓我們一起來(lái)學(xué)習(xí)排序算法。 排序的意義n排序是為了將一組雜亂的數(shù)據(jù)變成一組有序有序的數(shù)據(jù)。（遞增或遞減）n 排序法的使用時(shí)非常頻繁的，在實(shí)踐中，人們?cè)O(shè)計(jì)出了許多好的算法，如交換排序、插入排序、以及選擇排序等等。各種算法有其自身的特點(diǎn)與適用范圍，今天我們來(lái)學(xué)習(xí)其中人們較常用的一種： 冒泡排序法。冒泡排序法。 冒泡法排序 “冒泡法排序”也叫“起泡法排序” ，是一種比較簡(jiǎn)單、易懂

2、的交換排序方法，它通過將相鄰元素進(jìn)行比較比較和交換交換，逐步將一個(gè)無(wú)序序列排列為一個(gè)有序序列。將元素按從小到大的順序排列稱為升序排列，反之稱為降序排列。理解：冒泡排序是在一列數(shù)據(jù)中把較小的數(shù)據(jù)逐次理解：冒泡排序是在一列數(shù)據(jù)中把較小的數(shù)據(jù)逐次向上推移的一種排序技術(shù)。向上推移的一種排序技術(shù)。（觀賞FLASH）冒泡排序冒泡排序根據(jù)棋牌規(guī)則，把下列5張牌從小排到大排列冒泡排序用數(shù)組來(lái)存儲(chǔ)一系列同類型的數(shù)據(jù)用數(shù)組來(lái)存儲(chǔ)一系列同類型的數(shù)據(jù),然后調(diào)然后調(diào)整數(shù)組中的元素整數(shù)組中的元素. 例如例如: dim A(4) as integer 定義一個(gè)數(shù)組變量定義一個(gè)數(shù)組變量A圖314 冒泡法排序示意圖A(0)A(

3、1)A(2)A(3)A(4)n 這啟發(fā)我們把一個(gè)數(shù)組的一端比做水底而把另一端想像成水面，不斷把較小的數(shù)據(jù)移向一端或把較大的數(shù)據(jù)移向另一端，最終就可以得到排好序的數(shù)組。在這種排序的過程中，大的數(shù)就如氣泡一樣逐層下沉，而小的數(shù)逐個(gè)上浮，因此被形象地比喻成“冒泡”，故稱為冒泡法。 算法分析第1次冒泡排序時(shí)(i=0) j 從 4 開始到1For j=4 to 1 step -1 if d(j)d(j-1) then 交換d(j) 和d(j-1)的值第2次冒泡排序時(shí)(i=1) j 從 4 開始到2For j=4 to 2 step -1 if d(j)d(j-1) then 交換d(j) 和d(j-1)

4、的值第3次冒泡排序時(shí)(i=2) j 從 4 開始到3For j=4 to 3 step -1 if d(j)d(j-1) then 交換d(j) 和d(j-1)的值當(dāng)i 從0到3 變化時(shí) 每次 j 從4 到i+1 時(shí) d(j)比比d(j-1)小小,則交換它們則交換它們第4次冒泡排序時(shí)(i=3) j 從 4 開始到4For j=4 to 4 step -1 if d(j)d(j-1) then 交換d(j) 和d(j-1)的值程序代碼：程序代碼：For i = 0 To 3 For j = 4 To i + 1 Step -1 If A(j) A(j - 1) Then ( ) End If Next j Next i k = A(j): A(j) = A(j - 1): A(j - 1) = kn當(dāng)i 從0到3 變化時(shí)n 每次 j 從4 到i+1 時(shí) n A(j)比比A(j-1)小小,則交換它們則交換它們兩個(gè)數(shù)進(jìn)行數(shù)據(jù)交換兩個(gè)數(shù)進(jìn)行數(shù)據(jù)交換,就象兩杯水進(jìn)行交換就象兩杯水進(jìn)行交換,需要再拿一個(gè)空杯需要再拿一個(gè)空杯總結(jié)(*)n數(shù)組A（n） For i = 0 To n-1 For j = n To i + 1 Step -1n