排序算法一輪復習

1、排序算法一輪復習（一）安吉縣昌碩高級中學 吳志成排序算法在高考中的典型考法由排序代碼判斷數(shù)據(jù)加工后的結果(2016.04,11)統(tǒng)計趟數(shù)、比較次數(shù)和交換次數(shù)(2015.09,12)跟蹤指定數(shù)據(jù)的位置變化情況(2016.10,16)跟蹤指定位置的數(shù)據(jù)變化情況(相關資料)雙向排序(2017.04,12)排序的優(yōu)化(2015.10,16)排序中剔除重復數(shù)據(jù)(2017.11,16)只對某些特征數(shù)據(jù)排序(2018.04,16)如何應對排序算法考點越來越高要求基本原則：重基礎，重細節(jié) 應對措施：理解冒泡排序和選擇排序的排序過程，能熟練運用兩種排序方法對具體的數(shù)據(jù)序列進行排序掌握冒泡排序和選擇排序的代碼推導

2、方法，能通過閱讀代碼還原出具體的排序過程了解冒泡排序和選擇排序的典型應用，能通過具體案例代碼判斷屬于什么應用 從最基本入手，考察排序過程103672冒泡排序從右往左冒小泡：從左往右冒大泡：1036723627326710236710規(guī)律：1、n個元素，需要執(zhí)行n-1趟2、比較次數(shù)：n(n-1)/23、交換次數(shù)：比較次數(shù)想一想：n個元素冒泡排序，執(zhí)行的趟數(shù)，比較次數(shù)和交換次數(shù)？76310276103271063210763210276310如何更好地理解冒泡排序代碼冒泡排序的算法實現(xiàn)，是一趟一趟重復執(zhí)行的過程，因此，重點是實現(xiàn)第i趟執(zhí)行的過程（從右往左冒小泡）a(1)a(2)a(i-1)a(i)

3、a(i+1)a(i+2)a(n-2)a(n-1)a(n)目前執(zhí)行第i趟：a(n)-a(i)相鄰數(shù)據(jù)兩兩比較：a(n)與a(n-1)a(n-1)與a(n-2)a(i+1)與a(i)a(j)a(j-1)ifthentemp=a(j)a(j)=a(j+1)a(j+1)=tempEnd ifFor j=1 to n-iNext jFor i=1 to n-1Next i12i-1從最基本入手，考察排序過程選擇排序選出小值放左邊：103726237106237106236107236710選出大值放右邊：103726637210632710236710236710想一想：n個元素選擇排序，執(zhí)行的趟數(shù)，比

4、較次數(shù)和交換次數(shù)？規(guī)律：1、n個元素，需要執(zhí)行n-1趟2、比較次數(shù)：n(n-1)/23、交換次數(shù)：執(zhí)行趟數(shù)與冒泡排序效率的比較：就憑這一點，選擇排序效率更高如何更好地理解選擇排序代碼選擇排序的算法實現(xiàn)，是一趟一趟重復執(zhí)行的過程，因此，重點是實現(xiàn)第i趟執(zhí)行的過程（選出小值放左邊）a(1)a(2)a(i-1)a(i)a(i+1)a(i+2)a(n-2)a(n-1)a(n)目前執(zhí)行第i趟：a(i)-a(n)先假定當前第一個位置值最小p=i打擂臺，后續(xù)元素依次與擂臺上面的元素比較，小值留在擂臺上，比完后，擂臺上就是最小值（注意：擂臺為p，表示小值位置）a(i+1)與a(p)a(i+2)與a(p)a(n

5、)與a(p)a(j)a(p)ifthenp=jEnd ifFor j=i+1 to nNext jpiifthentemp=a(p)a(p)=a(i)a(i)=tempEnd ifFor i=1 to n-1Next i擂臺比武，選出所需，體現(xiàn)出“選”的特色趟數(shù)循環(huán)p=i假定當前第一個位置最小第i趟循環(huán)擂臺上不是小值，易主第i趟選出真正最小值后，若不在當前第一個位置上，交換如何更好地理解選擇排序代碼選擇排序的算法實現(xiàn)，是一趟一趟重復執(zhí)行的過程，因此，重點是實現(xiàn)第i趟執(zhí)行的過程（選出大值放右邊）a(1)a(2)a(3)a(i-1)a(i)a(i+1)a(n-1)a(n)nn-1i+1目前執(zhí)行第i趟：a(1)-a(i)i先假定當前最后一個位置值最小p=i打擂臺，前面元素依次與擂臺上面的元素比較，大值留在擂臺上，比完后，擂臺上就是最大值（注意：擂臺為p，表示大值位置）a(i-1)與a(p)a(i-2)與a(p)a(1)與a(p)a(j)a(p)ifthenp=jEnd ifFor j=i-1 to 1 step -1Next jIfpithentemp=a(p)a(p)=a(i)a(i)=tempEnd ifp=iFor i=n to 2Next i小結冒泡排序與選擇排序的過程（自己會排就了）冒泡排序與選擇排序的規(guī)律、