1、排序問(wèn)題排序問(wèn)題 1 1、冒泡法、冒泡法( (起泡法起泡法) ) 2 2、順序交換法、順序交換法 3 3、選擇法、選擇法 4 4、插入法、插入法1、冒泡法、冒泡法首先我們來(lái)看首先我們來(lái)看把最大的那個(gè)數(shù)放在最后位置上把最大的那個(gè)數(shù)放在最后位置上的方法：的方法：假設(shè)有假設(shè)有5 5個(gè)數(shù)，分別為個(gè)數(shù)，分別為1010，2 2，6 6，7 7，4 4，存放在，存放在a(1)-a(5)a(1)-a(5)中。中。 首先，從首先，從a(1)a(1)到到a(5)a(5)，相鄰的兩數(shù)相鄰的兩數(shù)兩兩進(jìn)行比較，在每次比兩兩進(jìn)行比較，在每次比較過(guò)程中，若前一個(gè)數(shù)比后一個(gè)數(shù)大，則交換兩元素的內(nèi)容。較過(guò)程中，若前一個(gè)數(shù)比后一

2、個(gè)數(shù)大，則交換兩元素的內(nèi)容。第一輪的比較過(guò)程：第一輪的比較過(guò)程：for j=1 to 4 for j=1 to 4 if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a(j)=a(j+1) : a(j+1)=t)=a(j+1) : a(j+1)=t End if End ifNext jNext j1、冒泡法、冒泡法n現(xiàn)在重復(fù)上述算法：把現(xiàn)在重復(fù)上述算法：把a(bǔ)(1)a(1)到到a(4)a(4)中的最大數(shù)放在中的最大數(shù)放在a(4)a(4)中，中，a(1)a(1)到到a(3) a(3) 中的最大數(shù)放在中的最大數(shù)放在a(3)a(3)

3、中，中，a(1)a(1)與與a(2) a(2) 中的最大數(shù)放在中的最大數(shù)放在a(2)a(2)中。這樣一共經(jīng)過(guò)中。這樣一共經(jīng)過(guò)4 4次次選大就把選大就把a(bǔ)(1)a(1)到到a(5)a(5)中的數(shù)進(jìn)行由小到大排序。中的數(shù)進(jìn)行由小到大排序。 在排序過(guò)程中小數(shù)象氣泡一樣上浮，而大數(shù)逐個(gè)在排序過(guò)程中小數(shù)象氣泡一樣上浮，而大數(shù)逐個(gè)下沉，所以叫起泡法。下沉，所以叫起泡法。第第1 1輪：輪：for j=1 to for j=1 to 4 4 if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a(j)=a(j+1) : a(j+1)=t)=a(

4、j+1) : a(j+1)=t End if End ifNext jNext j第第2 2輪：輪：for j=1 tofor j=1 to 3 3 if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a(j)=a(j+1) : a(j+1)=t)=a(j+1) : a(j+1)=t End if End ifNext jNext j第第3 3輪：輪：for j=1 to for j=1 to 2 2 if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a(j)=

5、a(j+1) : a(j+1)=t)=a(j+1) : a(j+1)=t End if End ifNext jNext j第第4 4輪：輪：for j=1 to for j=1 to 1 1 if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a(j)=a(j+1) : a(j+1)=t)=a(j+1) : a(j+1)=t End if End ifNext jNext j第第i i輪：輪：for j=1 to for j=1 to 5-i5-i if a(j if a(j)a(j+1) Then )a(j+1) Then

6、t=a(j t=a(j): a(j): a(j)=a(j+1): a(j+1)=t)=a(j+1): a(j+1)=t End if End ifNext jNext jFor i=1 to 4For i=1 to 4Next iNext i1.冒泡法冒泡法冒泡法程序清單：冒泡法程序清單：Dim a(1 To 5) As IntegerDim a(1 To 5) As IntegerFor i = 1 To 5For i = 1 To 5 a(i) = Val(InputBox a(i) = Val(InputBox(輸入一個(gè)數(shù)輸入一個(gè)數(shù))Next iNext iFor i=1 to 4For

7、 i=1 to 4 For j=1 To 5-i For j=1 To 5-i if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a(j)=a(j+1): a(j+1)=t)=a(j+1): a(j+1)=t End if End if Next j Next jNext i Next i For i = 1 To 5For i = 1 To 5 Print a(i Print a(i););Next iNext i冒泡排序冒泡排序思考：如果這思考：如果這5 5個(gè)數(shù)是個(gè)數(shù)是2 2，4 4，6 6，7 7，1010，簡(jiǎn)述程序執(zhí)行

8、流程。，簡(jiǎn)述程序執(zhí)行流程。1.冒泡法冒泡法改進(jìn)算法改進(jìn)算法: :Dim a(1 To 5) As IntegerDim a(1 To 5) As IntegerFor i = 1 To 5For i = 1 To 5 a(i) = Val(InputBox a(i) = Val(InputBox(輸入一個(gè)數(shù)輸入一個(gè)數(shù))Next iNext iFor i=1 to 4For i=1 to 4 flag=0flag=0 For j=1 To 5-i For j=1 To 5-i if a(j if a(j)a(j+1) Then )a(j+1) Then t=a(j): a(j t=a(j): a

9、(j)=a(j+1): a(j+1)=t: )=a(j+1): a(j+1)=t: flag=1flag=1 End ifEnd if Next j Next j If flag=0 Then Exit ForIf flag=0 Then Exit ForNext i Next i For i = 1 To 5For i = 1 To 5 Print a(i Print a(i););Next iNext i1.冒泡法冒泡法對(duì)已知存放在數(shù)組中的對(duì)已知存放在數(shù)組中的n n個(gè)數(shù)，用冒泡法按個(gè)數(shù)，用冒泡法按遞增順序遞增順序排序。排序。 (1) (1) 從第一個(gè)元素開(kāi)始，將從第一個(gè)元素開(kāi)始，將相鄰的數(shù)

10、比較相鄰的數(shù)比較，若為，若為逆序，就逆序，就交換交換，比較完一輪，最大的數(shù)已沉底，成為數(shù)組中的最后一個(gè)，比較完一輪，最大的數(shù)已沉底，成為數(shù)組中的最后一個(gè)元素元素a(na(n) ) (2) (2) 對(duì)對(duì)a(1)a(1)和和a(n-1)a(n-1)的的n-1n-1個(gè)數(shù)進(jìn)行同個(gè)數(shù)進(jìn)行同(1)(1)的操作，次大的操作，次大的數(shù)放入的數(shù)放入a(n-1)a(n-1)中，完成第二輪排序。中，完成第二輪排序。 (3) (3) 進(jìn)行進(jìn)行n-1n-1輪排序，所有的數(shù)排序完畢。輪排序，所有的數(shù)排序完畢。1.冒泡法冒泡法n n個(gè)數(shù)冒泡法遞增排序程序清單：個(gè)數(shù)冒泡法遞增排序程序清單： Dim a%(), i%, j%,

11、 n%Dim a%(), i%, j%, n% n = InputBox n = InputBox(請(qǐng)輸入一個(gè)正整數(shù)請(qǐng)輸入一個(gè)正整數(shù)) ReDim ReDim a(1 To n) a(1 To n) For i = 1 To n For i = 1 To n a(i) = Int(Rnd a(i) = Int(Rnd * * 100) : Print a(i 100) : Print a(i);); Next i Next i For i = 1 To For i = 1 To n - 1n - 1 For j = 1 To For j = 1 To n - in - i If If a(ja

12、(j) ) a(ja(j + 1) + 1) Then Then t = a(j): a(j) = a(j + 1): a(j t = a(j): a(j) = a(j + 1): a(j + 1) = t + 1) = t End If End If Next j Next j Next i Next i Print Print For i = 1 To n For i = 1 To n Print a(i Print a(i);); Next i Next i2、順序交換法、順序交換法我們?cè)賮?lái)看一種我們?cè)賮?lái)看一種將最小的數(shù)放在第一個(gè)位置將最小的數(shù)放在第一個(gè)位置的算法的算法先設(shè)定用先設(shè)定用a

13、(1)a(1)存放最小值，然后用存放最小值，然后用a(1)a(1)分別與其后分別與其后的每一個(gè)數(shù)的每一個(gè)數(shù)a(j)(ja(j)(j=2.5)=2.5)進(jìn)行比較，在比較過(guò)程中進(jìn)行比較，在比較過(guò)程中如果如果a(1)a(1)不是小的數(shù)，就將不是小的數(shù)，就將a(1)a(1)與與a(ja(j) )互換。互換。第一輪的比較過(guò)程第一輪的比較過(guò)程For j=2 To 5For j=2 To 5 if(a(1)a(j if(a(1)a(j) Then) Then t=a(1) : a(1)=a(j) : a(j t=a(1) : a(1)=a(j) : a(j)=t)=t End if End ifNext j

14、Next j2、順序交換法、順序交換法n現(xiàn)在重復(fù)上述算法：把現(xiàn)在重復(fù)上述算法：把a(bǔ)(2)a(2)到到a(5)a(5)中的最小數(shù)放在中的最小數(shù)放在a(2)a(2)中，中，a(3)a(3)到到a(5)a(5)中的最小數(shù)放在中的最小數(shù)放在a(3)a(3)中，中，a(4)a(4)與與a(5)a(5)中的最小數(shù)放在中的最小數(shù)放在a(4)a(4)中。這樣一共經(jīng)過(guò)中。這樣一共經(jīng)過(guò)4 4次選次選小就把小就把a(bǔ)(1)a(1)到到a(5)a(5)中的數(shù)進(jìn)行由小到大排序。中的數(shù)進(jìn)行由小到大排序。第第1 1輪：輪：for j=for j=2 2 to 5 to 5 if if a(1)a(1)a(ja(j) Then

15、 ) Then t=a(1): a(1)=a(j) : a(j t=a(1): a(1)=a(j) : a(j)=t)=t End if End ifNext jNext j第第2 2輪：輪：for j=for j=3 3 to 5 to 5 if if a(2)a(2)a(ja(j) Then ) Then t=a(2): a(2)=a(j) : a(j t=a(2): a(2)=a(j) : a(j)=t)=t End if End ifNext jNext j第第3 3輪：輪：for j=for j=4 4 to 5 to 5 if if a(3)a(3)a(ja(j) Then ) T

16、hen t=a(3): a(3)=a(j) : a(j t=a(3): a(3)=a(j) : a(j)=t)=t End if End ifNext jNext j第第4 4輪：輪：for j=for j=5 5 to 5 to 5 if if a(4)a(4)a(ja(j) Then ) Then t=a(4): a(4)=a(j) : a(j t=a(4): a(4)=a(j) : a(j)=t)=t End if End ifNext jNext j第第i i輪：輪：for j=for j=i+1i+1 to 5 to 5 if if a(ia(i) ) a(ja(j) ) Then

17、Then t=a(i t=a(i): a(i): a(i)=a(j)=a(j): a(j): a(j)=t)=t End if End ifNext jNext jFor i=1 to 4For i=1 to 4Next iNext i2、順序交換法、順序交換法 Dim a(1 To 5) As Integer Dim a(1 To 5) As Integer For i = 1 To 5 For i = 1 To 5 a(i) = Val(InputBox a(i) = Val(InputBox(輸入一個(gè)數(shù)輸入一個(gè)數(shù)) Next i Next i For i = 1 To 4 For i =

18、 1 To 4 For j = i+1 To 5 For j = i+1 To 5 If If a(ia(i) ) a(j a(j) Then ) Then t = a(i): a(i) = a(j): a(j t = a(i): a(i) = a(j): a(j) = t ) = t End if End if Next j Next j Next i Next i For i = 1 To 5 For i = 1 To 5 Print a(i Print a(i);); Next i Next i順序排序順序排序2、順序交換法、順序交換法對(duì)已知存放在數(shù)組中的對(duì)已知存放在數(shù)組中的n n個(gè)數(shù)，

19、用順序交換法按個(gè)數(shù)，用順序交換法按遞增順序遞增順序排排序。序。 (1) (1) 從第一個(gè)元素開(kāi)始，將它和其后的每個(gè)元素進(jìn)行比較，從第一個(gè)元素開(kāi)始，將它和其后的每個(gè)元素進(jìn)行比較，若為逆序，就交換，比較完一輪，若為逆序，就交換，比較完一輪，a(1)a(1)成為數(shù)組中的最小的元成為數(shù)組中的最小的元素。素。 (2) (2) 對(duì)對(duì)a(2)a(2)和和a(na(n) )的的n-1n-1個(gè)數(shù)進(jìn)行同個(gè)數(shù)進(jìn)行同(1)(1)的操作，次小的數(shù)的操作，次小的數(shù)放入放入a(2)a(2)中，完成第二輪排序。中，完成第二輪排序。 (3) (3) 進(jìn)行進(jìn)行n-1n-1輪排序，所有的數(shù)排序完畢。輪排序，所有的數(shù)排序完畢。2、順

20、序交換法、順序交換法n n個(gè)數(shù)順序法遞增排序程序清單：個(gè)數(shù)順序法遞增排序程序清單：Dim a%(), i%, j%, n%Dim a%(), i%, j%, n% n = InputBox n = InputBox(請(qǐng)輸入一個(gè)正整數(shù)請(qǐng)輸入一個(gè)正整數(shù)) ReDim ReDim a(1 To n) a(1 To n) For i = 1 To n For i = 1 To n a(i) = Int(Rnd a(i) = Int(Rnd * * 100): Print a(i 100): Print a(i);); Next i Next i For i = 1 To n - 1 For i = 1

21、 To n - 1 For j = i + 1 To n For j = i + 1 To n If a( If a(i i) a() a(j j) Then) Then t = a(i): a(i) = a(j): a(j t = a(i): a(i) = a(j): a(j) = t) = t End If End If Next j Next j Next i Next i Print Print For i = 1 To n For i = 1 To n Print a(i Print a(i);); Next i Next i3、選擇法、選擇法算法：不急于交換，先找出算法：不急于交換

22、，先找出a(1)a(1)到到a(5)a(5)中最小數(shù)所在中最小數(shù)所在的位置的位置K K，一遍掃描完之后，再把，一遍掃描完之后，再把a(bǔ)(1)a(1)與與a(Ka(K) )互換。互換。重復(fù)此算法，只是每次重復(fù)進(jìn)行比較的數(shù)列范圍向后重復(fù)此算法，只是每次重復(fù)進(jìn)行比較的數(shù)列范圍向后移一個(gè)位置。即第二遍從移一個(gè)位置。即第二遍從a(2)a(2)到到a(5)a(5)中去找最小數(shù)的中去找最小數(shù)的位置，最后把位置，最后把a(bǔ)(2)a(2)與與a(Ka(K) )對(duì)調(diào)，第三遍從對(duì)調(diào)，第三遍從a(3)a(3)到到a(5)a(5)中去找最小數(shù)的位置，最后把中去找最小數(shù)的位置，最后把a(bǔ)(3)a(3)與與a(Ka(K) )對(duì)調(diào)

23、，對(duì)調(diào)，此此過(guò)程重復(fù)過(guò)程重復(fù)4 4次后，即將次后，即將a a數(shù)組中的數(shù)組中的5 5個(gè)數(shù)按由小到大的個(gè)數(shù)按由小到大的順序排好。這種排序方法叫選擇法。順序排好。這種排序方法叫選擇法。第第1 1輪：輪：k=k=1 1for j=for j=2 2 to 5 to 5 if if a(ja(j) ) a(ka(k) ) Then k=j Then k=jNext jNext jif k1 then t=a(1):a(1)=a(k):a(kif k1 then t=a(1):a(1)=a(k):a(k)=t)=t第第2 2輪：輪：k=k=2 2for j=for j=3 3 to 5 to 5 if i

24、f a(ja(j) )a(ka(k) Then k=j) Then k=jNext jNext jif k2 then t=a(2):a(2)=a(k):a(kif k2 then t=a(2):a(2)=a(k):a(k)=t)=t第第3 3輪：輪：k=k=3 3for j=for j=4 4 to 5 to 5 if if a(ja(j) )a(ka(k) Then k=j) Then k=jNext jNext jif k3 then t=a(3):a(3)=a(k):a(kif k3 then t=a(3):a(3)=a(k):a(k)=t)=t第第4 4輪：輪：k=k=4 4for

25、j=for j=5 5 to 5 to 5 if if a(ja(j) )a(ka(k) Then k=j) Then k=jNext jNext jif k4 then t=a(4):a(4)=a(k):a(kif k4 then t=a(4):a(4)=a(k):a(k)=t)=t第第i i輪：輪：k=k=i ifor j=for j=i+1i+1 to 5 to 5 if if a(ja(j) ) a(ka(k) ) Then k=j Then k=jNext jNext jif kif ki i then t=a(i):a(i then t=a(i):a(i)=a(k):a(k)=a(

26、k):a(k)=t)=tFor i=1 to 4For i=1 to 4Next iNext i3、選擇法、選擇法選擇排序法程序清單：選擇排序法程序清單：Dim a(1 To 5) As IntegerDim a(1 To 5) As IntegerFor i = 1 To 5For i = 1 To 5 a(i) = Val(InputBox a(i) = Val(InputBox(輸入一個(gè)數(shù)輸入一個(gè)數(shù))Next iNext iFor i=1 to 4For i=1 to 4 k=i k=i For j=i+1 To 5 For j=i+1 To 5 if a(j)a(k if a(j)a(

27、k) Then k=j) Then k=j Next j Next j if ki Then t=a(i): a(i)=a(k): a(k if ki Then t=a(i): a(i)=a(k): a(k)=t)=tNext i Next i For i = 1 To 5For i = 1 To 5 Print a(i Print a(i););Next iNext i排序過(guò)程排序過(guò)程3、選擇法、選擇法對(duì)已知存放在數(shù)組中的對(duì)已知存放在數(shù)組中的n n個(gè)數(shù)，用選擇法按個(gè)數(shù)，用選擇法按遞增順序遞增順序排排序。序。 (1) (1) 從從n n個(gè)數(shù)的序列中選出最小的數(shù)，與第個(gè)數(shù)的序列中選出最小的數(shù)，與

28、第1 1個(gè)數(shù)交個(gè)數(shù)交換位置；換位置； (2) (2) 除第除第1 1個(gè)數(shù)外，其余個(gè)數(shù)外，其余n-1n-1個(gè)數(shù)再按個(gè)數(shù)再按(1)(1)的方法選的方法選出次小的數(shù)，與第出次小的數(shù)，與第2 2個(gè)數(shù)交換位置；個(gè)數(shù)交換位置； (3) (3) 重復(fù)重復(fù)(1)n-1(1)n-1遍，最后構(gòu)成遞增序列。遍，最后構(gòu)成遞增序列。3、選擇法、選擇法n n個(gè)數(shù)選擇法遞增排序程序清單：個(gè)數(shù)選擇法遞增排序程序清單：Dim a%(), i%, j%, n%Dim a%(), i%, j%, n% n = InputBox n = InputBox(請(qǐng)輸入一個(gè)正整數(shù)請(qǐng)輸入一個(gè)正整數(shù)) ReDim ReDim a(1 To n)

29、 a(1 To n) For i = 1 To n For i = 1 To n a(i) = Int(Rnd a(i) = Int(Rnd * * 100): Print a(i 100): Print a(i);); Next i Next i For i = 1 To n 1 For i = 1 To n 1 k=i k=i For j = i + 1 To n For j = i + 1 To n If a( If a(j j) a() a(k k) Then k=j) Then k=j Next j Next j if ki then t=a(i): a(i)=a(k): a(k if ki then t=a(i): a(i)=a(k): a(k)=t)=t Next i Next i Print Print For i = 1 To n For i = 1 To n Print a(i Print a(i);); Next i Next i4 插入法插入法147 10 13 16 19 22 25a數(shù)組數(shù)組key=20例例7 將一個(gè)數(shù)插入到有序的（由小到大）數(shù)列中，插將一個(gè)數(shù)插入到有序的（由小到大）數(shù)列中，插入后數(shù)列仍然有序。入后數(shù)列仍然有序。20 20 20 20 2020 20 20147 10 13 16 19 222