專題4-算法思維（2021版）

計(jì)算思維導(dǎo)論大學(xué)計(jì)算機(jī)公共基礎(chǔ)教學(xué)部4算法思維算法Raptor可視化程序設(shè)計(jì)（重難點(diǎn)）常用算法：統(tǒng)計(jì)、查找、排序（重難點(diǎn)）4.1算法計(jì)算機(jī)求解問(wèn)題的步驟(1)確定并理解問(wèn)題；(2)尋找解決問(wèn)題的方法與步驟，并將其表示成算法(Algorithm)

；(3)使用某種程序設(shè)計(jì)語(yǔ)言描述該算法(編程),并編譯成目標(biāo)程序和進(jìn)行調(diào)試；(4)運(yùn)行程序，獲得問(wèn)題的解答；(5)進(jìn)行評(píng)估，改進(jìn)算法和程序1.什么是算法？算法是解決問(wèn)題的方法與步驟例：有三個(gè)硬幣，其中一個(gè)是偽造的，另兩個(gè)是真的，偽幣與真幣重量略有不同。現(xiàn)在提供一座天平，如何找出偽幣呢？分析：方法明確而有序按提供的條件進(jìn)行操作任何人均可仿照進(jìn)行(共享智能)開(kāi)始C是偽幣B是偽幣A是偽幣A＝B？A＝C？是否否是ABC關(guān)于算法的三方面問(wèn)題如何確定算法（算法設(shè)計(jì)）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？2.算法設(shè)計(jì)舉例典型問(wèn)題：如何對(duì)數(shù)據(jù)進(jìn)行排序問(wèn)題：任給一組(n個(gè))整數(shù)，將它們從小到大進(jìn)行排序“選擇排序”算法的思路：①?gòu)乃姓麛?shù)中選一個(gè)最小數(shù)，作為已排序的第一個(gè)數(shù)②從剩下未排序整數(shù)中選最小的數(shù)，添加到已排序整數(shù)的后面③反復(fù)執(zhí)行步驟②，直到所有整數(shù)都處理完畢“選擇排序”算法舉例2345789第6次循環(huán)后，排序結(jié)束2937845與首元素交換，第1次循環(huán)結(jié)束4937825數(shù)組的初態(tài)，全部是未排序元素4937825在未排序元素中確定最小數(shù)位置2397845與首元素交換，第2次循環(huán)結(jié)束2937845在未排序元素中確定最小數(shù)位置2347895與首元素交換，第3次循環(huán)結(jié)束2397845在未排序元素中確定最小數(shù)位置3.算法的表示流程圖表示偽代碼描述算法的流程圖表示流程圖由結(jié)點(diǎn)和有向邊構(gòu)成，它描述了算法所執(zhí)行操作的順序及執(zhí)行操作的條件流程圖符號(hào)：比文字描述簡(jiǎn)明，但當(dāng)算法比較復(fù)雜時(shí)，理解困難，容易產(chǎn)生錯(cuò)誤端點(diǎn)符處理判斷預(yù)定義功能原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i=i+1i=n?結(jié)束開(kāi)始用流程圖表示選擇排序算法算法控制結(jié)構(gòu)——順序結(jié)構(gòu)一種簡(jiǎn)單的程序設(shè)計(jì)結(jié)構(gòu)自始至終嚴(yán)格按照程序中語(yǔ)句的先后順序逐條執(zhí)行最基本最常用的結(jié)構(gòu)形式根據(jù)條件表達(dá)式真假性執(zhí)行不同的語(yǔ)句算法的控制結(jié)構(gòu)——選擇(分支)結(jié)構(gòu)根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同功能的程序段（循環(huán)體）。當(dāng)型循環(huán)：先判斷條件，條件成立執(zhí)行循環(huán)體直到型循環(huán)：先執(zhí)行循環(huán)體后判斷條件算法的控制結(jié)構(gòu)——循環(huán)結(jié)構(gòu)將原始數(shù)據(jù)放在數(shù)組A中；設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到i=n：{確定A[i]到A[n]中最小整數(shù)的位置，設(shè)為j；交換A[i]和[j]；i=i+1}使用偽代碼描述“選擇排序”算法使用偽代碼描述算法偽代碼(Pseudocode)是用來(lái)描述算法的一種語(yǔ)言，它既類似于自然語(yǔ)言，又使用與程序設(shè)計(jì)語(yǔ)言相似的方法描述算法優(yōu)點(diǎn)：結(jié)構(gòu)清晰，代碼簡(jiǎn)單，可讀性好，可以容易地以任何一種編程語(yǔ)言(Pascal,C,Java等)實(shí)現(xiàn)每個(gè)整數(shù)是A的一個(gè)元素：A[1],A[2],···,A[n]4.算法的分析算法分析的基本內(nèi)容正確性：給定有效輸入后，經(jīng)過(guò)有限時(shí)間的計(jì)算，產(chǎn)生正確的輸出結(jié)果簡(jiǎn)單性算法是否容易理解，是否容易驗(yàn)證其正確性，程序是否容易調(diào)試簡(jiǎn)單的算法效率不一定高，要在保證一定效率的前提下力求算法簡(jiǎn)單時(shí)間復(fù)雜性(TimeComplexity)

：當(dāng)問(wèn)題的規(guī)模n充分大時(shí)，運(yùn)行該算法所需要的時(shí)間的數(shù)量級(jí)表示空間復(fù)雜性(SpaceComplexity)：除原始數(shù)據(jù)之外，額外占用的存儲(chǔ)空間的大小S(n)＝O(f(n))，其中，n為問(wèn)題的規(guī)模（1）時(shí)間復(fù)雜度指執(zhí)行算法所需要的計(jì)算工作量算法的時(shí)間復(fù)雜度=T(n)，n為問(wèn)題的規(guī)模。

常用量級(jí)相同的函數(shù)f(n)來(lái)表示，并記為T(n)=O(f(n))。常見(jiàn)的f(n)函數(shù)有1、log2n、n、nlog2n、n2、n3和2n等量級(jí)關(guān)系如下：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)O(1)表示常量時(shí)間，與問(wèn)題規(guī)模n無(wú)關(guān)。時(shí)間復(fù)雜度選講：

選擇排序算法的時(shí)間復(fù)雜性假設(shè)參加排序的整數(shù)有n個(gè)（1）比較操作的次數(shù)： 在第i趟排序中選出最小整數(shù)時(shí)，需做n-i次比較操作， 因此，總的比較操作次數(shù)為：n(n-1)/2=(n2-n)/2（2）移動(dòng)操作的次數(shù)： 最好情況(原始數(shù)據(jù)已經(jīng)排序)時(shí)，移動(dòng)次數(shù)為0

最壞情況(原始數(shù)據(jù)逆序排列)時(shí)，每趟均要執(zhí)行交換操作(3次傳送)，總的移動(dòng)次數(shù)取最大值為：3(n-1)所以，直接選擇排序的時(shí)間復(fù)雜性為O(n2)設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到I=n：{確定A[i]到A[n]中最小的整數(shù)元素的位置，設(shè)為j；交換A[i]和[j]；i=i+1}(2)算法的空間復(fù)雜度度量空間的復(fù)雜性，即執(zhí)行算法的程序在計(jì)算機(jī)中運(yùn)行時(shí)所占用的內(nèi)存空間的大小。關(guān)于算法的小結(jié)計(jì)算機(jī)中處處是算法！例1：Word程序如何在文檔中查找用戶指定的詞語(yǔ)？例2：在Word文檔的表格中如何將表格內(nèi)容排序？例3：如何把一幅彩色圖片轉(zhuǎn)換為灰度(黑白)圖片？例4：Windows如何在硬盤中找到用戶指定的文件？例5：媒體播放器如何把MP3文件轉(zhuǎn)換成動(dòng)聽(tīng)的音樂(lè)？例6：搜索引擎如何在WWW網(wǎng)中找到用戶需要的網(wǎng)頁(yè)？計(jì)算機(jī)算法的4個(gè)特點(diǎn)目的：完成某個(gè)特定的信息處理任務(wù)必須滿足的性質(zhì)：①確定性：算法中每一步操作的含義必須清楚明確，無(wú)二義性②可行性：算法中有待實(shí)現(xiàn)的操作都是計(jì)算機(jī)可執(zhí)行的，即必須在計(jì)算機(jī)的能力范圍之內(nèi)③有窮性：算法在執(zhí)行了有限步操作后必須結(jié)束④擁有足夠的情報(bào)通用算法實(shí)際問(wèn)題算法思想4.2Raptor可視化程序設(shè)計(jì)程序的基本編寫方法Raptor基礎(chǔ)控制結(jié)構(gòu)常用函數(shù)和數(shù)組常用算法（統(tǒng)計(jì)\最值\閏年\素?cái)?shù)）程序的基本編寫方法IPOI（Input輸入）-鍵盤接收用戶輸入的初始數(shù)據(jù)-也有其他輸入方式，如文件輸入等P（

Process處理）-包含各種運(yùn)算與賦值操作，負(fù)責(zé)將初始數(shù)據(jù)加工成為運(yùn)算結(jié)果-處理方法統(tǒng)稱為算法，它是程序的靈魂O（Output輸出）-顯示計(jì)算結(jié)果Raptor基礎(chǔ)Raptor環(huán)境基本符號(hào)常量和變量數(shù)據(jù)類型算術(shù)運(yùn)算符輸入操作輸出操作賦值操作Raptor環(huán)境基于流程圖的可視化程序設(shè)計(jì)環(huán)境工作區(qū)工具欄菜單欄編寫區(qū)符號(hào)區(qū)主工作區(qū)即：程序編寫區(qū)變量觀察區(qū)RaptorRaptor程序是一組連接的符號(hào)，表示要執(zhí)行的一系列動(dòng)作符號(hào)間的連接箭頭確定所有操作的執(zhí)行順序Raptor程序執(zhí)行時(shí)，從開(kāi)始（Start）符號(hào)起步，并按照箭頭所指方向執(zhí)行程序，Raptor程序執(zhí)行到結(jié)束（End）符號(hào)時(shí)停止Raptor的基本符號(hào)常量和變量常量：在程序運(yùn)行過(guò)程中，其值不能改變的量例如：14，“hello，world”，3.14，‘A’Raptor預(yù)定義了四個(gè)符號(hào)常量pi（圓周率）定義為3.1416e（自然對(duì)數(shù)的底）定義為2.7183true/yes(布爾值:真)定義為1false/no(布爾值：假)定義為0變量：在程序運(yùn)行過(guò)程中，其值可以改變的量

例如：a,b,z,name標(biāo)識(shí)符命名規(guī)則：以英文字母開(kāi)頭的英文字母、數(shù)字和下劃線組成的字符串?dāng)?shù)據(jù)類型決定了數(shù)據(jù)所屬的值的范圍，以及能夠?qū)υ擃悢?shù)據(jù)進(jìn)行的操作和在內(nèi)存中的存儲(chǔ)方式Raptor數(shù)據(jù)類型：數(shù)值（Number）類型，數(shù)字型數(shù)據(jù)如：12，567，-4，3.1415，0.000371字符串（String）類型，多個(gè)字符組成的數(shù)據(jù)如：“Helloworld”，“JamesBond”字符（Character）類型，單個(gè)字符數(shù)據(jù)如：’A’，’8’，’!’算術(shù)運(yùn)算符Raptor的輸入操作把輸入符號(hào)拖到程序編寫區(qū)雙擊之后將彈出一個(gè)窗口第一個(gè)文本框填入輸入提示注意：提示信息要加雙引號(hào)第二個(gè)文本框填入將要被賦值的變量演示：Raptor的輸入操作Raptor的輸出操作把輸出符號(hào)拖入編寫區(qū)雙擊彈出窗口填入想要輸出的內(nèi)容可以是具體的值也可以是變量Raptor輸出操作演示Raptor的賦值操作插入賦值符號(hào)雙擊該符號(hào)彈出窗口在“Set”輸入框填入要賦值的變量在“to”輸入框填入要賦值的值表達(dá)式演示：Raptor的賦值操作Raptor的控制結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)控制結(jié)構(gòu)——順序結(jié)構(gòu)例題：從鍵盤輸入兩個(gè)數(shù)輸出它們的和

控制結(jié)構(gòu)——選擇結(jié)構(gòu)插入選擇符號(hào)后，雙擊該符號(hào)，在彈出的窗口中輸入框中輸入決策表達(dá)式。決策表達(dá)式是一組值（常量或變量）和關(guān)系運(yùn)算符的結(jié)合,

期望得到Y(jié)ES/NO這樣的結(jié)果。表達(dá)式語(yǔ)句真（非0）假（0）表達(dá)式語(yǔ)句1語(yǔ)句2

非0

0關(guān)系運(yùn)算符與布爾運(yùn)算符運(yùn)算符說(shuō)明例=等于3=

4結(jié)果為

No(false)!=/=不等于3!=

4結(jié)果為Yes(true)3/=

4結(jié)果為

Yes(true)<小于3<

4結(jié)果為Yes(true)<=小于或等于3<=

4結(jié)果為Yes(true)>大于3>

4結(jié)果為No(false)>=大于或等于3>=4結(jié)果為No(false)and與(3<4)

and(10<

20)，結(jié)果為Yes(true)or或(3<4)

or(10

>20)，結(jié)果為Yes(true)not非not(3<

4)，結(jié)果為No(false)演示：Raptor的選擇結(jié)構(gòu)例題：從鍵盤輸入兩個(gè)數(shù)輸出兩個(gè)數(shù)中較大值練習(xí)：Raptor的選擇結(jié)構(gòu)從鍵盤輸入一個(gè)數(shù)，輸出其絕對(duì)值分析：1.鍵盤輸入數(shù)據(jù)2.判斷數(shù)的正負(fù)3.正數(shù)或0直接輸出4.負(fù)數(shù)輸出其相反數(shù)思考題：輸出三個(gè)數(shù)的最大值分析：從鍵盤輸入3個(gè)數(shù)比較2次輸出最大值Raptor操作演示控制結(jié)構(gòu)——循環(huán)結(jié)構(gòu)指在程序中需要反復(fù)執(zhí)行某個(gè)功能而設(shè)置的一種程序結(jié)構(gòu)。三要素：循環(huán)變量初始值循環(huán)結(jié)束的條件循環(huán)變量的改變量在Raptor中一個(gè)橢圓和一個(gè)菱形符號(hào)被用來(lái)表示一個(gè)循環(huán)循環(huán)執(zhí)行的次數(shù)，由菱形符號(hào)中的表達(dá)式來(lái)控制要重復(fù)執(zhí)行的語(yǔ)句可以放在菱形符號(hào)上方或下方。演示：Raptor的循環(huán)結(jié)構(gòu)編程實(shí)現(xiàn)：1+2+3+…+100輸出結(jié)果練習(xí)：Raptor的循環(huán)結(jié)構(gòu)編程實(shí)現(xiàn)5！分析：1.使用循環(huán)結(jié)構(gòu)2.循環(huán)變量從1增加到53.結(jié)果變量初始化為14.循環(huán)一次進(jìn)行一次乘法運(yùn)算思考：如果要計(jì)算10！，如何修改程序？Raptor演示10！Raptor的常用函數(shù)與數(shù)組常用函數(shù)三角函數(shù)數(shù)組Raptor的常用函數(shù)函數(shù)形式功能舉例abs(x)計(jì)算x的絕對(duì)值abs(-23)=23max(x,y)計(jì)算x,y的最大值max(23,43)=43min(x,y)計(jì)算x,y的最小值min(23,43)=23floor(x)計(jì)算不大于x的最大整數(shù)floor(15.9)=15ceiling(x)計(jì)算不小于x的最小整數(shù)ceiling(15.9)=16random計(jì)算[0.0,1.0)之間的隨機(jī)數(shù)floor(random*6+1)log自然對(duì)數(shù)(以e為底)log(e)=1sqrt平方根sqrt(4)=2length_of對(duì)數(shù)組變量，返回?cái)?shù)組元素的個(gè)數(shù)；對(duì)字符串變量，則返回字符個(gè)數(shù)str←”Sellnow”length_of(str)=8Raptor的三角函數(shù)演示：Raptor的常用函數(shù)輸出max(2,-3)輸出floor(13.7)輸出floor(-13.7)輸出ceiling(13.7)輸出ceiling(-13.7)Raptor演示練習(xí)：隨機(jī)函數(shù)生成[a，b](a>b)之間的隨機(jī)整數(shù)分析：1.使用random生成[0.0,1.0)之間的隨機(jī)數(shù)2.random*(b-a+1)+a生成[a，b]之間的隨機(jī)數(shù)3.使用floor取整函數(shù):floor(random*(b-a+1)+a)思考：如何獲得[1，1000]之間的隨機(jī)整數(shù)？floor(random*(1000-1+1)+1)Raptor演示練習(xí)：函數(shù)的應(yīng)用隨機(jī)生成兩個(gè)[64,512]之間的整數(shù)，輸出這兩個(gè)數(shù)中較大的數(shù)。分析：1.使用兩次floor(random*(512-64+1)+64)生成[64,512]之間的2個(gè)隨機(jī)整數(shù)2.使用max()函數(shù)輸出兩個(gè)隨機(jī)整數(shù)的較大值

Raptor演示Raptor的數(shù)組數(shù)組是有序數(shù)據(jù)的集合。數(shù)組中的每一個(gè)元素都屬于同一個(gè)數(shù)據(jù)類型（數(shù)值、字符、字符串）。數(shù)組的優(yōu)勢(shì)：用一個(gè)統(tǒng)一的數(shù)組名和下標(biāo)（index）來(lái)唯一地確定數(shù)組變量中的元素。下標(biāo)可以參與計(jì)算，因而可以動(dòng)態(tài)遍歷數(shù)組元素?cái)?shù)組名下標(biāo)演示：Raptor的數(shù)組初始化初始化一個(gè)具有10個(gè)數(shù)組元素的全0數(shù)組，輸出該數(shù)組。分析：初始化數(shù)組輸出數(shù)組Raptor演示分析：輸出語(yǔ)句使用了字符串連接運(yùn)算練習(xí)：Raptor的數(shù)組初始化初始化一個(gè)具有10個(gè)數(shù)組元素的一維數(shù)組，使數(shù)組元素的值等于其下標(biāo)值的平方，輸出該數(shù)組。分析：如何修改剛才的程序？Raptor演示練習(xí)：Raptor的數(shù)組元素求和初始化一個(gè)具有10個(gè)數(shù)組元素的一維數(shù)組，使數(shù)組元素的值等于其下標(biāo)值的平方，輸出該數(shù)組和元素之和。分析：如何修改剛才的程序？Raptor演示存放元素之和變量初始為0求和常用算法統(tǒng)計(jì)最值問(wèn)題閏年素?cái)?shù)統(tǒng)計(jì)算法在給定的范圍內(nèi)求出符合設(shè)定條件的記錄個(gè)數(shù)基本思想：用一個(gè)條件語(yǔ)句判斷當(dāng)前記錄是否符合給定條件，符合則統(tǒng)計(jì)個(gè)數(shù)加一，用循環(huán)實(shí)現(xiàn)對(duì)所有記錄的操作求解步驟：定義代表所有統(tǒng)計(jì)要求的計(jì)數(shù)器變量令所有計(jì)數(shù)器變量的初值為0構(gòu)建循環(huán)體，當(dāng)滿足指定的計(jì)數(shù)要求時(shí)，就將相應(yīng)的計(jì)數(shù)器的值加1（執(zhí)行類似于n=n+1的操作）構(gòu)建循環(huán)條件，根據(jù)問(wèn)題的具體要求，選用相應(yīng)的循環(huán)語(yǔ)句輸出所有計(jì)數(shù)器的值統(tǒng)計(jì)實(shí)例：求三位正整數(shù)中能夠被3和5整除的數(shù)字的個(gè)數(shù)分析：定義計(jì)數(shù)器count，初值為0構(gòu)建循環(huán)體：若循環(huán)變量n能被3和5整除，則計(jì)數(shù)器加1循環(huán)條件：n從100到999如何判斷整除：取余運(yùn)算

modnmod3==0andnmod5==0Raptor演示練習(xí)：統(tǒng)計(jì)一個(gè)字符串中數(shù)字的個(gè)數(shù)分析：定義計(jì)數(shù)器count，初值為0構(gòu)建循環(huán)體：若當(dāng)前元素是數(shù)字，則計(jì)數(shù)器加1循環(huán)條件：n從1到length_of(str)如何判斷字符是數(shù)字：str[i]>=’0’andstr[i]<=‘9’Raptor演示最值問(wèn)題算法最大最小最多最少最長(zhǎng)最短等問(wèn)題稱之為“最值問(wèn)題”求解步驟：定義x代表N個(gè)數(shù)中的一個(gè)數(shù)。分別定義存放最大值和最小值的變量maxN和minN。令maxN=所有數(shù)據(jù)中的第1個(gè)數(shù)，minN=所有數(shù)據(jù)中的第1個(gè)數(shù)。構(gòu)建循環(huán)體，然后將x與maxN比較，如果x比maxN大，令maxN=x；將x與minN比較，如果x比minN小，令minN=x。構(gòu)建循環(huán)條件，根據(jù)問(wèn)題的具體要求，選用相應(yīng)的循環(huán)語(yǔ)句。輸出maxN和minN的值。最值問(wèn)題實(shí)例：求五個(gè)數(shù)中的最大值最小值分析：數(shù)組a存放5個(gè)隨機(jī)整數(shù)（0-100）maxN=a[1]minN=a[1]構(gòu)建循環(huán)體：若a[i]>maxN,則maxN=a[i]若a[i]<minN,則minN=a[i]循環(huán)條件：i從2到length_of(a)輸出maxN和minNRaptor演示部分截圖練習(xí)：輸出一個(gè)字符串中碼值最大的字符及其下標(biāo)分析：變量a存放字符串maxi=1構(gòu)建循環(huán)體：若a[i]>a[maxi],則maxi=i循環(huán)條件：i從2到length_of(a)輸出a[maxi]和maxiRaptor演示閏年問(wèn)題：判斷一個(gè)年份是否是閏年分析：閏年判斷標(biāo)準(zhǔn)：能被4整除且不能被100整除或者能被400整除Raptor演示練習(xí)：輸出1900~2021之間所有的閏年年份分析：year從1900~2021循環(huán),若year是閏年，則輸出Raptor演示素?cái)?shù)判斷：判斷一個(gè)大于2的自然數(shù)是否是素?cái)?shù)分析：若n不能被2-根號(hào)n之間的整數(shù)整除，則是素?cái)?shù)，否則不是素?cái)?shù)設(shè)置一個(gè)flag為1循環(huán)變量從2到根號(hào)n，若n能被循環(huán)變量整除，則flag=0，結(jié)束循環(huán)根據(jù)flag的值確定自然數(shù)是否是素?cái)?shù)。Raptor演示練習(xí)：輸出3-100之間的所有素?cái)?shù)分析：雙重循環(huán)外層循環(huán)n從3-100內(nèi)層循環(huán)從2到根號(hào)n，判斷n是否是素?cái)?shù)Raptor演示練習(xí)：輸出3-100之間的所有素?cái)?shù)，使用子圖分析：判斷素?cái)?shù)保存為子圖prime主程序中循環(huán)n從3-100調(diào)用primeRaptor演示4.3查找與排序查找排序交換類排序插入類排序選擇類排序概述查找和排序是數(shù)據(jù)處理領(lǐng)域中的重要內(nèi)容，算法的效率將直接影響到數(shù)據(jù)處理的效率。查找是在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。排序是將一個(gè)無(wú)序的元素序列處理成有序序列。不同的數(shù)據(jù)結(jié)構(gòu)、不同的方法，算法效率不同。應(yīng)根據(jù)應(yīng)用問(wèn)題場(chǎng)景選擇合適的數(shù)據(jù)結(jié)構(gòu)、算法。查找(1)順序查找(2)二分法查找viewview(1)順序查找順序查找一般指在線性表中查找指定的元素。方法：從線性表的第1個(gè)元素開(kāi)始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等，則表示查找成功；若線性表中所有元素都與被查找元素進(jìn)行了比較，但均不相等，則表示查找失敗。示例:在線性表中查找元素60123458172886397元素?zé)o序只能采用順序查找的方法由過(guò)程可見(jiàn)，每比較1次，查找范圍僅減少1個(gè)60查找失敗(1)順序查找順序查找演示分析：數(shù)據(jù)存放數(shù)組中設(shè)置一個(gè)flag，初始0，查到賦值1構(gòu)建循環(huán)體：從第一個(gè)元素開(kāi)始依次比較，直到找到或者比較完數(shù)組所有元素Raptor演示(2)二分法查找二分查找也稱「折半查找」。是一種高效的查找算法。使用二分查找，須滿足兩個(gè)條件：①順序存儲(chǔ)；②元素有序。方法：將待查找元素x與有序線性表的中間項(xiàng)元素進(jìn)行比較:（設(shè)有序線性表是遞增的）若x=中間項(xiàng)元素，則表示找到;若x<中間項(xiàng)元素，則在線性表前半部分以二分法繼續(xù);若x>中間項(xiàng)元素，則在線性表后半部分以二分法繼續(xù)示例:在線性表中查找元素60順序表且元素有序123455361728490959767891①中間元素:8460<84→在[53,61,72]中找②中間元素:6160<61→在[53]中找③中間元素:5360>53→沒(méi)找到由過(guò)程可見(jiàn)，每比較1次，查找范圍縮小一半折半查找算法步驟數(shù)據(jù)存放數(shù)組a中，升序排列設(shè)置一個(gè)flag，初始0，查到賦值1top=1,bottom=length_of(a)循環(huán)比較：mid=floor((top+bottom)/2)如果key==a[mid],則flag=1，循環(huán)結(jié)束如果key>a[mid],則到下半部查找，top=mid+1如果key<a[mid],則到上半部查找，bottom=mid-1循環(huán)結(jié)束條件：flag=1（已找到）或top>bottom（已找完）折半查找Raptor實(shí)現(xiàn)key=60Raptor演示key=84Raptor演示交換類排序(1)冒泡排序法(2)快速排序法viewview(1)冒泡排序法①算法描述②示例③小結(jié)viewviewview①算法描述——冒泡排序法（設(shè)由小→大排序）算法思想:將相鄰兩個(gè)數(shù)比較，較大的數(shù)放到后面第1遍:對(duì)n個(gè)數(shù)進(jìn)行第1遍掃描

比較第1個(gè)數(shù)與第2個(gè)數(shù)，若a1>a2，則交換；

比較第2個(gè)數(shù)與第3個(gè)數(shù)，若a2>a3，則交換；

依次類推…

比較第n-1個(gè)數(shù)和第n個(gè)數(shù)，若an-1>an

，則交換；經(jīng)過(guò)(n-1)次比較后，最大的數(shù)被放在an第2遍:

對(duì)前n-1個(gè)數(shù)進(jìn)行第2遍掃描:

經(jīng)過(guò)(n-2)次比較后，第2大的數(shù)被放在an-1……第n-1遍:

對(duì)前2個(gè)數(shù)進(jìn)行第n-1遍掃描:

經(jīng)過(guò)1次比較后，第2小的數(shù)被放a2

至此，排序過(guò)程結(jié)束?？偨Y(jié):用冒泡法對(duì)n個(gè)數(shù)小→大排序,共需掃描(n-1)遍，第i遍掃描時(shí)需要比較(n-i)次②示例——使用冒泡排序法由小→大排序初始序列:4 2 3 1(n=4)第1遍:第2遍:第3遍:比較1:2

4

3 1比較2:2

3 4

1比較3:2 3 1

42 3 1 比較1:比較2:2 1

3

比較1:1

2用冒泡法對(duì)4個(gè)數(shù)排序，共需要掃描3次，第i遍掃描需要比較(4-i)次冒泡排序動(dòng)圖③小結(jié)——冒泡排序法使用冒泡排序法對(duì)n個(gè)數(shù)排序，最壞的情況下，需比較的次數(shù)：n(n-1)/2該算法的時(shí)間復(fù)雜度為:O(n2)(2)快速排序法①算法描述②示例③小結(jié)viewviewview①算法描述——快速排序法（設(shè)由小→大排序）算法思想:a)從線性表中選定一個(gè)元素t;b)然后，將線性表后面的元素與t比較，小于t的移至前面，而前面大于t的移至后面。經(jīng)過(guò)一輪后，元素t的位置確定。c)對(duì)元素t之前的子表和元素t之后的子表進(jìn)行同樣的操作。直至，所有元素都有序。②示例——使用快速排序法由小→大排序初始序列:52,45,80,36,14,75,58,96,23,61(n=10)第1遍:選定元素52

×,45,80,36,14,75,58,96,23,6123,45,80,36,14,75,58,96,×,6123,45,×,36,14,75,58,96,80,6123,45,14,36,×,75,58,96,80,6123,45,14,36,52,75,58,96,80,61第3遍:…第2遍:子序列1選定元素23,子序列2選定元素75

23,45,14,36,52,75,58,96,80,6114,23,45,36,52,61,58,75,80,96×,45,14,36,14,45,×,36,14,×,45,36,×,58,96,80,6161,58,96,80,×61,58,×,80,96③小結(jié)——快速排序法快速排序本質(zhì)上是對(duì)冒泡排序的一種改進(jìn)。每次比較后將待排序序列分割成子序列?？焖倥判虻臅r(shí)間主要耗費(fèi)在子序列分割操作上。最壞的情況下，時(shí)間復(fù)雜度是O(n2)最好的情況下，時(shí)間復(fù)雜度是O(nlog2n)插入類排序(1)直接插入排序法(2)希爾排序法viewview(1)直接插入排序法①算法描述②示例③小結(jié)viewviewview①算法描述——直接插入排序法算法思想:a)將第1個(gè)元素視為已排好序；b)然后，將第2個(gè)元素插入到已排好序的序列中。依次類推，將第3個(gè)元素直至第n個(gè)元素插入到已排好序的序列中。②示例——使用直接插入排序法由小→大排序待排序序列:48,62,35,77,55,14,37,9848,62,35,77,55,14,37,98第1遍:48,62,35,77,55,14,37,98第2遍:35,48,62,77,55,14,37,98第3遍:35,48,62,77,55,14,37,98第4遍:35,48,55,62,77,14,37,98第5遍:14,35,48,55,62,77,37,98第6遍:14,35,37,48,55,62,77,98第7遍:14,35,37,48,55,62,77,98第8遍:插入排序動(dòng)圖③小結(jié)——直接插入排序法直接插入排序法，最壞的情況下需比較n(n-1)/2次，時(shí)間復(fù)雜度是O(n2)(2)希爾排序法①算法描述②示例③小結(jié)viewviewview①算法描述——希爾排序法算法思想:a)將待排序的序列分為若干組，在每組內(nèi)進(jìn)行直接插入排序。b)然后，再對(duì)整個(gè)序列進(jìn)行直接插入排序。這一算法思想的關(guān)鍵在于分組。分組沒(méi)有固定方式。通常做法是：將相隔某個(gè)增量r的元素分為一組；

然后，每次r減半，直到r為1②示例——使用希爾排序法由小→大排序待排序序列:51,45,80,36,14,75,58,96(n=8)第1遍:(r=4)51,45,80,36,14,75,58,9614,45,58,36,51,75,80,96第2遍:(r=2)14,45,58,36,51,75,80,9614,36,51,45,58,75,80,96第3遍:(r=1)14,36,51,45,58,75,80,96希爾排序動(dòng)圖③小結(jié)——希爾插入排序法希爾排序，屬于插入類排序算法。對(duì)直接插入排序法進(jìn)行了改進(jìn)。最壞的情況下時(shí)間復(fù)雜度是O(n1.5)選擇類排序(1)直接選擇排序法(2)堆排序法viewview(1)直接選擇排序法①算法描述②示例③小結(jié)viewviewview①算法描述——直接選擇排序法（設(shè)由小→大排序）算法思想:選出n個(gè)數(shù)中最小的數(shù)與第1個(gè)數(shù)對(duì)換；選出次小的數(shù)與第2個(gè)數(shù)對(duì)換；依此類推，…；選出第2大的數(shù)與第(n-1)個(gè)數(shù)對(duì)換。②示例——使用直接選擇排序法由小→大排序待排序序列:(n=8)52,45,80,36,14,75,58,96第1遍:14,45,80,36,52,75,58,96第2遍:14,36,80,45,52,75,58,96第3遍:14,36,45,80,52,75,58,96第4遍:14,36,45,52,80,75,58,96第5遍:14,36