1、西北農林科技大學西北農林科技大學信息工程學院信息工程學院 張晶張晶 基于基于BOPPPS模式教學模式教學通過比較通過比較和插入來和插入來排序排序算法是程序的算法是程序的靈魂靈魂；算法是在算法是在有限步驟內有限步驟內求解某一問題所使用的一組求解某一問題所使用的一組定義明確的規則定義明確的規則。計算機算法，就是通過計算機算法，就是通過計算機計算機來解決問題的來解決問題的方法和方法和步驟步驟。 如何利用插入排序算法來得到如何利用插入排序算法來得到名次呢名次呢？11.411.1910.8111.310.8810.94有序有序待排待排11.411.1910.8111.310.8810.9411.411.

2、411.1910.8111.310.8810.94有序有序待排待排第一次第一次小小11.411.1910.8111.310.8810.9411.1911.19比較比較確定在位置確定在位置111.411.1910.8111.310.8810.94待排待排11.411.1911.411.1910.8111.310.8810.94有序有序第一次第一次11.19比較比較確定在位置確定在位置1騰出空位騰出空位插入插入11.411.1910.8111.310.8810.94待排待排11.411.1910.8111.310.8810.9410.81有序有序第二次第二次小小10.81比較比較11.411.19

3、10.8111.310.8810.94待排待排11.411.1910.8111.310.8810.94有序有序第二次第二次小小10.81比較比較確定在位置確定在位置111.411.1910.8111.310.8810.94待排待排11.411.1910.8111.310.8810.9411.411.1910.81有序有序第二次第二次10.81比較比較確定在位置確定在位置1騰出空位騰出空位插入插入11.411.1910.8111.310.8810.94待排待排11.411.1910.8111.310.8810.9411.3有序有序第三次第三次小小大大11.3比較比較確定在位置確定在位置311.4

4、11.1910.8111.310.8810.94待排待排11.411.1910.8111.310.8810.9411.411.3有序有序第三次第三次11.3比較比較確定在位置確定在位置3騰出空位騰出空位插入插入11.411.1910.8111.310.8810.94待排待排11.411.1910.8111.310.8810.94有序有序第四次第四次10.88比較比較確定在位置確定在位置2騰出空位騰出空位插入插入11.411.1910.8111.310.8810.94待排待排11.411.1910.8111.310.8810.94有序有序第五次第五次10.94比較比較確定在位置確定在位置3騰出空

5、位騰出空位插入插入總結總結：插入排序算法的思想：插入排序算法的思想排序排序結束結束11.411.1910.8111.310.8810.94有序有序插入排序算法插入排序算法Step1Step1：將第一個數作為參照，置于有將第一個數作為參照，置于有序序列的第一個，此時，需要排序的數序序列的第一個，此時，需要排序的數據被分成了據被分成了有序序列有序序列和和待排序列。待排序列。Step2Step2：取取待排序列待排序列中的第一個數與有中的第一個數與有序序列中的數由后向前一一比較，確序序列中的數由后向前一一比較，確定其所在位置，定其所在位置，騰騰出出位置位置，將該數據，將該數據插入插入。Step3Ste

6、p3：重復重復Step1Step1、Step2Step2，直至待排，直至待排序列中數據個數為序列中數據個數為零零。對算法策略進行對算法策略進行優化優化。減少比較次數和移動次數，盡量減少比較次數和移動次數，盡量提高速度提高速度。已經學過的排序算法如何優化？已經學過的排序算法如何優化？希爾排希爾排序算法序算法基于基于“記錄越少，速度越快記錄越少，速度越快”的思想，在插的思想，在插入排序時對入排序時對待排序列待排序列進行進行“跳躍式跳躍式”移動。移動。11.411.1910.8111.310.8810.94第一次，位置間隔為第一次，位置間隔為311.411.1910.8111.310.8810.94

7、11.411.310.8811.1911.310.8810.8111.411.1910.94第第二二次，位置間隔為次，位置間隔為210.8110.8811.1910.9411.311.4第三次，位置間隔為第三次，位置間隔為110.8110.8810.9411.1911.311.4結束結束插入排插入排序算法序算法比較比較次數次數和和移動次數移動次數：待排序列有序效率很：待排序列有序效率很高；待排序數據隨機，比較和移動次數均為高；待排序數據隨機，比較和移動次數均為n n2 2/4/4次。次。時間時間復復雜雜度為度為O(n2)最后一個最后一個位置間隔位置間隔為為1 1，則時間復雜度為，則時間復雜度為

8、O(nO(n3/23/2) )希爾排希爾排序算法序算法為什么關為什么關于于排序要排序要講講這么多這么多不同的算不同的算法法？0101條條大路通羅馬條條大路通羅馬為什么要為什么要優化算法優化算法策略？策略？0202學習算法學習算法和優化算和優化算法有什么法有什么作用？作用？0303精益求精精益求精事半功倍事半功倍培養思維，培養思維，提高解決問題的提高解決問題的能力與效率能力與效率將需要排序的數分成有序和待排兩部分，初始將需要排序的數分成有序和待排兩部分，初始時第一個數在有序序列中。時第一個數在有序序列中。 依次將待排序列中的數據跟有序序列中的數依次將待排序列中的數據跟有序序列中的數據比較，按規則插入有序序列。據比較，按規則插入有序序列。將需要排序的數按照某位置間隔分成若干序將需要排序的數按照某位置間隔分成若干序列，每個序列內部分別進行列，每個序列內部分別進行插入排序。插入排序。依次依次縮小間隔，直到縮小間隔，直到間隔間隔為為1 1。“跳躍式跳躍式”移動的排序方法。移動的排序方法。結合課堂結合課堂講述，講述，理解算法策