第1部分第二章§11.2排序問題與算法的多樣性課件

1、第二章算法初步1算法的基本思想理解教材新知應(yīng)用創(chuàng)新演練考點(diǎn)一把握熱點(diǎn)考向考點(diǎn)二1.2排序問題與算法的多樣性12排序問題與算法的多樣性 由于人類具有主觀能動(dòng)性，將數(shù)據(jù)a插入到有序列a1，a2，an中時(shí)，能很快找到適當(dāng)?shù)奈恢?，而?jì)算機(jī)解決此類問題時(shí)，其解決方式不同計(jì)算機(jī)每次只能比較兩個(gè)數(shù)據(jù)的大小，不能直接“看”出應(yīng)插到有序列a1，a2，an的哪個(gè)位置，因此要想用計(jì)算機(jī)解決排序問題必須要設(shè)計(jì)算法，使得每次僅比較兩個(gè)數(shù)的大小 問題：若將3插入到有序列3，2,2,4,7中，排序方法有幾種？ 提示：有兩種 1排序 為了便于查詢和檢索，常常根據(jù)某種要求把被查詢的對象用 表示出來，并把 按大小排列，是信息處理

2、中一項(xiàng)基本的工作，通常稱為排序 2排序的方法 (1) 排序法； (2) 排序法數(shù)字(或者符號)數(shù)字有序列直接插入折半插入 1有序列直接插入排序法蘊(yùn)涵的算法思想： 有序列直接插入法主要是通過逐一比較，通過有限次的“操作”將某一個(gè)數(shù)據(jù)插入原有序列的一種算法，它主要包含以下兩步： 對于一個(gè)有序列：a1a2a3an，欲將新數(shù)據(jù)A插入到有序列中，形成新的有序列 將數(shù)據(jù)A與原有序列中的數(shù)據(jù)從右到左依次進(jìn)行比較，直到發(fā)現(xiàn)某一數(shù)據(jù)ai，使得aiA，把A插入到ai的右邊； 如果數(shù)據(jù)A小于原有序列中的所有數(shù)據(jù)，則將A插入到原序列的最左邊 2有序列折半插入排序法蘊(yùn)涵的算法思想及插入的方法和步驟： 折半插入排序的基本

3、思想與二分法的思想一致，即逐步縮小所要比較的數(shù)據(jù)的范圍，直到確定出所要插入的數(shù)據(jù)的位置為止 插入的方法如下： 先將新數(shù)據(jù)與有序列中“中間位置”的數(shù)據(jù)進(jìn)行比較 若有序列有2n1個(gè)數(shù)據(jù)，則“中間位置”的數(shù)據(jù)指的是第n1個(gè)數(shù)；若有序列有2n個(gè)數(shù)據(jù)，則“中間位置”的數(shù)據(jù)指的是第n個(gè)數(shù) 如果新數(shù)據(jù)小于“中間位置”的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)該在靠左邊的一半；如果新數(shù)據(jù)等于“中間位置”的數(shù)據(jù)，則將新數(shù)據(jù)插入到“中間位置”的數(shù)據(jù)的右邊；如果新數(shù)據(jù)大于“中間位置”的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)該在靠右邊的一半 也就是說，一次比較就排除了數(shù)據(jù)列中一半的位置，反復(fù)進(jìn)行這種比較直到確定新數(shù)據(jù)的位置，像這樣的插入排序方

4、法就稱為折半插入排序方法 例1將4插入有序列8，3,0,2,6中，分別用直接插入排序法和折半插入排序法寫出算法 思路點(diǎn)撥(1)利用直接插入排序法，只要按從右到左的順序?qū)?逐個(gè)與有序列中數(shù)據(jù)進(jìn)行比較即可； (2)利用折半插入排序法，應(yīng)找到中間位置a30與4進(jìn)行比較，然后把剩下數(shù)據(jù)中間位置的數(shù)據(jù)依次與4比較，直到找到4的位置 精解詳析法一：直接插入排序法： (1)4與6比較，由于46，則4在6的左邊； (2)4與2比較，由于42，則4在2的左邊； (3)4與0比較，由于40，則4在0的左邊； (4)4與3比較，由于48，則4在8的右邊，則4在8與3之間； (6)得新的有序列8，4，3,0,2,6

5、法二：折半插入排序法： (1)4與0比較，由于48，則4在8的右邊； (3)4與3比較，由于43，則4在3的左邊，故 4在8與3之間； (4)得新的有序列8，4，3,0,2,6 一點(diǎn)通兩種算法的共同點(diǎn)是每次將新數(shù)據(jù)與有序列中的數(shù)據(jù)進(jìn)行比較；不同點(diǎn)是直接插入排序法總是將數(shù)據(jù)A與原有序列中的數(shù)據(jù)從右到左依次進(jìn)行比較，而折半插入排序法總是將新數(shù)據(jù)與該有序列中的“中間位置”的數(shù)據(jù)進(jìn)行比較1將數(shù)據(jù)6通過直接插入排序的方法插入有序列1,3,5,7,9,11,13中，需要作比較大小的次數(shù)為 ()A3B4C5 D6解析：數(shù)據(jù)6依次與13,11,9,7,5比較，共作5次比較大小答案：C2若用折半插入排序法將4插

6、入到有序列0,1,2,3中，則第一次應(yīng)與該有序列中的哪個(gè)數(shù)比較 ()A0 B1C2 D3解析：因?yàn)橛行蛄兄杏?2個(gè)數(shù)，所以應(yīng)先與第2個(gè)數(shù)1進(jìn)行比較答案：B3請利用直接插入排序和折半插入排序的方法分別寫出將數(shù)據(jù)43插入有序列21,39,46,57,67,73,84,96的算法解：直接插入排序算法：將43與96比較，4396，所以43在96的左邊；將43與84比較，4384，所以43在84的左邊；將43與73比較，4373，所以43在73的左邊；將43與67比較，4367，所以43在67的左邊；將43與57比較，4357，所以43在57的左邊；將43與46比較，4339，故43在39與46之間排序

7、后這一有序列為21,39,43,46,57,67,73,84,96折半插入排序算法：共8個(gè)數(shù)，中間位置上的數(shù)是57，將43與57進(jìn)行比較，4357,43在有序列的左半部分；再將余下數(shù)據(jù)的中間位置上的數(shù)39與43進(jìn)行比較，3943,43在數(shù)據(jù)39的右邊，又435，且125，8在5的右側(cè)，取序列12,17的中間數(shù)12，817，25應(yīng)在17的右側(cè)，插入得序列1,5,8,12,17,25； 6將15插入到1,5,8,12,17,25中，取序列的中間數(shù)8，158，15應(yīng)在8的右側(cè)，取序列12,17,25的中間數(shù)17，1512，15應(yīng)在12的右側(cè)，故應(yīng)將15插入到12與17之間得序列1,5,8,12,15

8、,17,25 一點(diǎn)通對一組無序的數(shù)據(jù)列進(jìn)行排序時(shí)，通常將這組無序的數(shù)據(jù)列的第一個(gè)數(shù)據(jù)看成一個(gè)有序列，將第二個(gè)數(shù)據(jù)插入到這個(gè)有序列得到一個(gè)有序列；然后，將第三個(gè)數(shù)據(jù)插入到上面的有序列中，又得到一個(gè)有序列，按照這種方法，直到將最后一個(gè)數(shù)據(jù)插入到有序列中，得到一個(gè)有序列，這樣實(shí)質(zhì)上就是完成了對無序的數(shù)據(jù)列排序，最后得到的有序列就是對無序的數(shù)據(jù)組排序的結(jié)果4將有序列5,4,3,2,1按照從小到大的順序輸出，需要排序的次數(shù)為 ()A7 B8C9 D10解析：1.把4插入到5中，得4,5，需1次排序；2把3插入到4,5中，得3,4,5，需2次排序；3把2插入到3,4,5中，得2,3,4,5，需3次排序；4

9、把1插入到2,3,4,5中，得1,2,3,4,5，需4次排序故共需123410次排序答案：D5設(shè)計(jì)算法，將36,6,12,24,38,46,0排序解：1.36是有序列，將36與6比較，因?yàn)?66，故得到有序列6,36；2將12與6,36各數(shù)進(jìn)行比較，因?yàn)?26，故得到有序列6,12,36；3將24與6,12,36各數(shù)進(jìn)行比較，因?yàn)?412,2436，故得到有序列6,12,24,36,38；5將46與6,12,24,36,38各數(shù)進(jìn)行比較，因?yàn)?638，故得到有序列6,12,24,36,38,46；6將0與6,12,24,36,38,46各數(shù)進(jìn)行比較，因?yàn)?6，故得到有序列0,6,12,24,36,38,46所以排序之后的結(jié)果為0,6,12,24,36,38,46 1對于一個(gè)無序列將其重新進(jìn)行有序排列的方法： 方法一：利用有序列插入排序法來解決 方法二：利用“選擇排序”的方法來解決例如：給定一個(gè)無序列23,