《插入排序算法》教學(xué)課件

插入排序算法

排序算法設(shè)計插入排序算法算法原理訓(xùn)練項目程序設(shè)計算法評估教學(xué)目標教學(xué)目標掌握插入排序算法原理熟練控制類模板函數(shù)的返回值掌握利用for與while循環(huán)語句以多種方法編寫插入排序函數(shù)的方法掌握根據(jù)實際需要對算法函數(shù)程序進行控制的方法插入排序算法教學(xué)目標訓(xùn)練項目程序設(shè)計算法評估算法原理

與選擇排序算法不同，插入排序（InsertionSorting）是從無序部分不經(jīng)選擇，任取一元，然后插入到有序部分的正確位置。

關(guān)鍵在于我們能否改變循環(huán)結(jié)構(gòu)并實現(xiàn)算法。該算法步驟如下：將L[1…n]分為兩部分：L[1..i]為已排序部分，L[i+1…n]為未排序部分。（1）i=1

（2）把L[i+1…n]插入到L[1..i]中的正確位置，i++

（3）if(i<n)goto（2）（4）結(jié)束插入排序算法教學(xué)目標訓(xùn)練項目程序設(shè)計算法評估算法原理

程序分析：template<classType>TypeInsertSort(Types[],intn){ Typetemp;for(inti=1;i<=n-1;i++){ for(intj=i-1,temp=s[i];j>=0;j--){ if(s[j]>temp)s[j+1]=s[j]; else{s[j+1]=temp;break;k=0;} } } return*s;}

插入排序算法教學(xué)目標算法原理訓(xùn)練項目程序設(shè)計算法評估訓(xùn)練項目：

請同學(xué)們修正上述程序的錯誤，并進行完整的編程實踐。插入排序算法教學(xué)目標算法概念動畫演示程序設(shè)計算法評估設(shè)待排序數(shù)組為s[]其中，第i個元素為s[i]

第j個元素為s[j]fori=1,k=1J=i-1非零J>=0s[J+1]=s[J]非零零零v=s[i]i<=n-1s[J+1]=v;break;k=0;i++forJ=i-1s[J]>vJ--K==1s[J+1]=v零零非零非零插入排序算法教學(xué)目標算法概念動畫演示程序設(shè)計算法評估了解插入排序算法函數(shù)template<classType>TypeInsertSort(Types[],intn){ Typetemp;intk;for(inti=1;i<=n-1;i++){ k=1;for(intj=i-1,temp=s[i];j>=0;j--){ if(s[j]>temp)s[j+1]=s[j]; else{s[j+1]=temp;break;k=0;} } if(k==1)s[j+1]=temp;} return*s;}

插入排序算法教學(xué)目標算法概念動畫演示程序設(shè)計算法評估

編程實操請同學(xué)們，根據(jù)插入排序算法函數(shù)的原理，并增加輸入輸出功能，編寫完成的算法程序。

插入排序算法教學(xué)目標算法概念動畫演示程序設(shè)計算法評估插入排序算法與選擇排序算法都有兩重循環(huán)，但卻有一個重要的差別，就是在選擇排序算法中，內(nèi)層循環(huán)次數(shù)是確定的，而在插入排序算法中，內(nèi)層循環(huán)次數(shù)是不確定的，因此，其最壞情形和平均情形的時間復(fù)雜度是不同的。顯然，插入排序最壞情形出現(xiàn)在內(nèi)層循環(huán)中，變量j的值都是從i-1變到0。例如，當(dāng)L[1…n]的元素值不同且恰為降序排列時，最壞情形出現(xiàn)，

W(n)=插入排序的最好情形，顯然是內(nèi)層循環(huán)每次只進行一次比較。例如當(dāng)L[1…n]的元素值本身就是按升序排列時，B(n)=n-1插入排序算法教學(xué)目標算法概念問題長度程序設(shè)計算法評估

作業(yè)1請使用兩種不同的插入排序算法程序