哇編程！-跟小明一起學(xué)算法

??

?悢???怺?乚?

???


???



??

文文前.indd前.indd122020/4/14020/4/14115:53:295:53:29

內(nèi)容簡(jiǎn)介

本書融入了游戲設(shè)計(jì)思想，通過游戲攻關(guān)的方式，介紹各種算法的原理和應(yīng)用。全書共分

8章，具體包括排序算法、窮舉算法、遞歸算法、回溯算法、貪心算法、分治算法，棧、隊(duì)列、

樹三種數(shù)據(jù)結(jié)構(gòu)，動(dòng)態(tài)規(guī)劃算法，圖論相關(guān)算法等內(nèi)容。

本書適合程序員和參加NOIP、NOI、ACM/ICPC競(jìng)賽的讀者閱讀學(xué)習(xí)，也可作為高等院校

計(jì)算機(jī)、數(shù)學(xué)及相關(guān)專業(yè)的師生用書和培訓(xùn)學(xué)校的教材。

圖書在版編目（CIP）數(shù)據(jù)

哇，編程！:跟小明一起學(xué)算法/游明偉,吳健之編著.—北京：

中國(guó)鐵道出版社有限公司，2020.5

ISBN978-7-113-26736-0

Ⅰ.①哇…Ⅱ.①游…②吳…Ⅲ.①程序設(shè)計(jì)－算法－少兒讀物

Ⅳ.①TP311.1-49

中國(guó)版本圖書館CIP數(shù)據(jù)核字（2020）第046339號(hào)

書名：哇，編程！——跟小明一起學(xué)算法

WA,BIANCHENG!——GENXIAOMINGYIQIXUESUANFA

作者：游明偉吳健之

責(zé)任編輯：于先軍讀者熱線電話：（010）63560056

責(zé)任印制：趙星辰封面設(shè)計(jì)：

出版發(fā)行：中國(guó)鐵道出版社有限公司（100054，北京市西城區(qū)右安門西街8號(hào)）

印刷：三河市航遠(yuǎn)印刷有限公司

版次：2020年5月第1版2020年5月第1次印刷

開本：787mm×1092mm1/16印張：17.25字?jǐn)?shù)：330千

書號(hào)：ISBN978-7-113-26736-0

定價(jià)：69.80元

版權(quán)所有侵權(quán)必究

凡購(gòu)買鐵道版圖書，如有印制質(zhì)量問題，請(qǐng)與本社讀者服務(wù)部聯(lián)系調(diào)換。電話：（010）51873174

打擊盜版舉報(bào)電話：（010）51873659

文文前.indd前.indd222020/4/14020/4/14115:53:345:53:34

配套資源下載地址：

/2020/0404/14246.shtml

前言

近些年來，隨著人工智能、大數(shù)據(jù)等技術(shù)的迅猛發(fā)展，計(jì)算機(jī)編程開始逐漸進(jìn)入大眾的

視野，特別是教育行業(yè)，各種少兒編程班如雨后春筍般層出不窮。人們開始漸漸意識(shí)到，培

養(yǎng)孩子的邏輯和計(jì)算思維能力，已經(jīng)成為一項(xiàng)必不可少的教育方式。而這些在我的童年時(shí)期，

是一項(xiàng)遙不可及的事物，甚至在我小學(xué)和初中期間，計(jì)算機(jī)還仍未被普及。那時(shí)候人們對(duì)計(jì)

算機(jī)的認(rèn)識(shí)，還只限于QQ和各種網(wǎng)頁(yè)小游戲。計(jì)算機(jī)科學(xué)發(fā)展到現(xiàn)在，我們?cè)诟袊@科技發(fā)

展迅速的同時(shí)，也必須感謝這個(gè)美好的時(shí)代。

我第一次接觸計(jì)算機(jī)編程是在初三保送高中階段，其他同學(xué)還在埋頭準(zhǔn)備中考時(shí)，我有

幸遇到了我的恩師——NOI金牌教練董永建。恰逢董老師在保送生中選拔信息學(xué)奧賽學(xué)生，

中考期間和整個(gè)暑假，我們42名保送生提前開始了高中生活，跟隨董老師從零開始接觸計(jì)

算機(jī)、學(xué)習(xí)算法，直到暑假結(jié)束僅剩4名同學(xué)堅(jiān)持了下來。后來，我們4個(gè)人從機(jī)房搬進(jìn)了

“小黑屋”，認(rèn)識(shí)了各位師兄，開始了真正的“封閉式訓(xùn)練”。高中三年我們沒有周末、沒

有節(jié)假日、沒有寒暑假，把所有的課余時(shí)間全貢獻(xiàn)給“小黑屋”，董老師帶著我們參加各

種培訓(xùn)、參加高校ACM比賽，為了鍛煉體能，帶著我們爬山，偷玩游戲被發(fā)現(xiàn)了，罰我們

操場(chǎng)跑圈……和師兄、師弟、師妹們?cè)凇靶『谖荨崩锏娜陼r(shí)光，是我至今回想都覺得快

樂的時(shí)光，也是影響我一生的時(shí)光。在接觸編程后半年，我第一次參加了NOIP（National

OlympiadinInformaticsinProvinces，信息學(xué)奧林匹克聯(lián)賽），第一年初出茅廬，只是讓我

們見識(shí)了世面，師兄們才是當(dāng)年的主力。我們充當(dāng)了一年陪考，直到第二年，經(jīng)過一年多的

積累，我們成了主力，在2017年NOIP競(jìng)賽，我獲得了省一等獎(jiǎng)。所有光鮮的背后，都隱

藏著熬過無數(shù)個(gè)不為人知的黑夜。

非常感謝董永建老師的悉心教導(dǎo)，讓我在初中時(shí)期開始，對(duì)計(jì)算機(jī)編程和算法有了初步

的認(rèn)識(shí)。也緣于NOIP競(jìng)賽，讓我取得了保送武漢大學(xué)的資格，并因此決定了我畢業(yè)以后的

工作和生活。人生選擇一條路，一直走到盡頭，不退讓，不更改，是件幸事。

文文前.indd前.indd322020/4/14020/4/14115:53:355:53:35

哇，編程！——跟小明一起學(xué)算法

NOIP競(jìng)賽對(duì)于很多孩子和家長(zhǎng)來說，還是一個(gè)比較陌生的事物。它由中國(guó)計(jì)算機(jī)學(xué)會(huì)

（CCF）統(tǒng)一組織，每年在同一時(shí)間、不同地點(diǎn)以各省市為單位由特派員組織。這個(gè)競(jìng)賽最

初設(shè)立的目的是向中學(xué)階段的青少年普及計(jì)算機(jī)科學(xué)知識(shí)，帶來新的學(xué)習(xí)思路，并借此選拔

人才。得益于近年來計(jì)算機(jī)知識(shí)的普及，許多對(duì)算法思想感興趣的學(xué)生和家長(zhǎng)已經(jīng)開始把

NOIP當(dāng)成一種新的學(xué)習(xí)思路和方法。本書所講的算法便是基于NOIP競(jìng)賽內(nèi)容進(jìn)行闡述的，

從基礎(chǔ)的排序算法到圖論算法，逐步深入了解算法思路。

為了便于各位讀者對(duì)枯燥算法內(nèi)容的理解，本書融入了游戲設(shè)計(jì)思想，通過游戲攻關(guān)的

方式，介紹各種算法的原理和應(yīng)用。當(dāng)你通讀完本書后，會(huì)發(fā)現(xiàn)原來我們平常玩的各種手游，

比如“吃雞”“王者”，它們的設(shè)計(jì)思路就是采用了各種算法，這時(shí)候你就已經(jīng)開始領(lǐng)略到

算法的奧妙，并開始進(jìn)入算法的魔法大門了。

為什么寫這本書?

寫這本書的原因，是來自朋友和妻子的啟發(fā)。得益于NOIP競(jìng)賽，我大學(xué)的專業(yè)學(xué)的是

軟件工程，畢業(yè)后從事的也是軟件開發(fā)工作。在快要邁入而立之年的某一天，我的妻子問了

我一個(gè)問題：“你做了這么多年軟件開發(fā)，早年也參加過NOIP，是不是現(xiàn)在得有所沉淀了？”

這時(shí)候我們的女兒剛出生6個(gè)月，我因此開始思考教育的問題。這時(shí)候我的一個(gè)朋友告訴

我：“你可以嘗試寫一本書，將你在NOIP競(jìng)賽所學(xué)及多年工作積累記錄下來，說不定以后

還能用來給你女兒當(dāng)教材?！庇谑牵阌辛诉@本《哇，編程！——跟小明一起學(xué)算法》。

■本書導(dǎo)讀

全書共分8章：

第1章主要介紹排序算法，介紹了經(jīng)典的三種排序方法，同時(shí)介紹了時(shí)間復(fù)雜度、空間

復(fù)雜度。

第2章主要介紹了五種基礎(chǔ)的算法，是信息學(xué)奧賽中常見的五種算法，一道算法題往往

會(huì)包含多種基礎(chǔ)算法，本章也為后續(xù)篇章的算法奠定基礎(chǔ)。

第3、4章主要介紹了三種數(shù)據(jù)結(jié)構(gòu)——棧、隊(duì)列、樹，數(shù)據(jù)結(jié)構(gòu)是一門語(yǔ)言的基礎(chǔ)，

本章在介紹算法的同時(shí)也強(qiáng)化了C++語(yǔ)言，補(bǔ)充了一些C++基礎(chǔ)學(xué)習(xí)中未涉及的內(nèi)容。

第5章主要介紹了動(dòng)態(tài)規(guī)劃算法，動(dòng)態(tài)規(guī)劃算法往往是NOIP（普及組、提高組）的

壓軸題，也是能區(qū)分競(jìng)賽選手差距的題目，本章由最經(jīng)典的背包問題開始講解動(dòng)態(tài)規(guī)劃算法，

理解本章才算是開始理解“算法的精髓”。

·4·

文文前.indd前.indd422020/4/14020/4/14115:53:355:53:35

第6、7、8章主要介紹圖論相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、圖的遍歷、

最小生成樹、并查集、最短路徑等。這三章所講的算法屬于進(jìn)階算法，圖論相關(guān)算法其本質(zhì)依

然是前面章節(jié)所講的基礎(chǔ)算法，在介紹圖論算法時(shí)，也繼續(xù)幫助讀者鞏固前面部分的基礎(chǔ)算法。

閱讀本書的讀者，需要具備基本的C++語(yǔ)言基礎(chǔ)，本書算法盡量采用通俗易懂的例子

給讀者講解。學(xué)習(xí)算法并不是一件難事，算法本身也并不高深，難在理解算法后怎么再用通

俗的話語(yǔ)講解出來。本書所涉及的算法，也是我從初中就開始接觸并學(xué)習(xí)的，我相信初中程

度的讀者也能夠理解并使用本書所寫的算法。

■致謝

在開始寫這本書之前，我一直猶豫要不要寫，因?yàn)閯偝錾呐畠簬缀跽加昧宋宜兄苣?/p>

和空閑時(shí)間，是妻子的鼓勵(lì)，讓我下定決心要寫完這本書，作為送給女兒的禮物。在我寫書

的這半年里，所有的節(jié)假日我都躲在圖書館度過，感謝我的妻子這半年里辛勞的付出，感謝

她在背后的支持。

感謝我的大學(xué)室友——JazyWoo同學(xué)提供了給我寫書的機(jī)會(huì)，幫我聯(lián)絡(luò)各方資源，也

感謝他在寫書期間，與我共同探討，共同完成此書。

還要再一次感謝董永建老師，是他的諄諄教導(dǎo)才能讓我有幸寫了這本算法書。

游明偉

2019年4月

·5·

文文前.indd前.indd522020/4/14020/4/14115:53:355:53:35

目錄

第1章整理下背包.....................................................................................1

1.1桶排序........................................................................................................2

1.2冒泡排序.....................................................................................................8

1.3快速排序....................................................................................................15

1.4時(shí)間和空間復(fù)雜度.....................................................................................20

第2章開始闖關(guān)吧...................................................................................22

2.1忘記密碼了——窮舉算法...........................................................................23

2.2漢諾塔——遞歸算法..................................................................................25

2.3八皇后——回溯算法...................................................................................31

2.4分裝備——貪心算法...................................................................................41

2.5二分查找——分治算法..............................................................................45

第3章爆滿的服務(wù)器與背包.....................................................................53

3.1服務(wù)器爆滿——隊(duì)列..................................................................................54

3.2合成寶石——優(yōu)先隊(duì)列...............................................................................61

3.3背包里的道具——棧..................................................................................65

3.4十進(jìn)制轉(zhuǎn)任意進(jìn)制.....................................................................................74

文文前.indd前.indd622020/4/14020/4/14115:53:355:53:35

第4章點(diǎn)亮技能樹...................................................................................77

4.1樹.............................................................................................................78

4.1.1樹的定義...........................................................................................................................79

4.1.2樹的相關(guān)術(shù)語(yǔ)...................................................................................................................80

4.2二叉樹......................................................................................................83

4.2.1二叉樹性質(zhì).......................................................................................................................84

4.2.2特殊的二叉樹...................................................................................................................85

4.2.3二叉樹的遍歷...................................................................................................................87

4.2.4二叉樹的存儲(chǔ)結(jié)構(gòu).........................................................................................................105

4.3堆...........................................................................................................107

4.3.1大根堆與小根堆.............................................................................................................107

4.3.2堆的操作.........................................................................................................................109

4.4堆排序.....................................................................................................132

第5章爆裝備啦，快來?yè)?.....................................................................139

5.1撿到完美的海螺——遞推算法....................................................................140

5.201背包——?jiǎng)右?guī)算法................................................................................143

5.3完全背包——?jiǎng)右?guī)算法.............................................................................148

5.4多重背包——?jiǎng)右?guī)算法.............................................................................152

第6章迷宮............................................................................................156

6.1圖的概念..................................................................................................157

6.1.1圖的定義.........................................................................................................................158

6.1.2圖的存儲(chǔ)結(jié)構(gòu).................................................................................................................162

文文前.indd前.indd722020/4/14020/4/14115:53:355:53:35

6.2圖的遍歷.................................................................................................167

6.2.1深度優(yōu)先搜索法.............................................................................................................168

6.2.2廣度優(yōu)先搜索法.............................................................................................................172

6.3并查集.....................................................................................................176

6.3.1分析.................................................................................................................................177

6.3.2并查集的原理.................................................................................................................179

6.3.3并查集的操作.................................................................................................................180

6.4最小生成樹..............................................................................................186

6.4.1Prim算法........................................................................................................................187

6.4.2Kruskal算法...................................................................................................................192

第7章探索地圖每個(gè)角落......................................................................197

7.1深度優(yōu)先搜索...........................................................................................198

7.2廣度優(yōu)先搜索...........................................................................................211

第8章快逃命去吧.................................................................................229

8.1拓?fù)渑判?................................................................................................230

8.2最短路徑................................................................................................240

8.2.1Floyd算法.......................................................................................................................240

8.2.2Dijkstra算法...................................................................................................................250

8.2.3Bellman-Ford算法.........................................................................................................255

8.2.4SPFA算法.......................................................................................................................261

文文前.indd前.indd822020/4/14020/4/14115:53:355:53:35

第1章

整理下背包

正正文.indd文.indd122020/4/14020/4/14115:54:325:54:32

哇，編程！——跟小明一起學(xué)算法

1.1桶排序

?Ρ??????????????????????????????????Ρ?

???????????????????úú??ǎ

???к??????????t????????????t??????????

???????????t????????????ζ?????t?????????

??????????????ǎ???к?????Ν????

??????????????????ǒ?????ǔǎ?????????????

?????????????????????????????ΓΡ??????ΓΡ?

????????????????NPC?????????????????????

ǎ???????????????????????ΓΡ?

????????????3??????1??????6?????????????

?ǎ??????3????????10??????7??āā????????????

?????????1?????????Χ????????????????????

?3??????3??????6??????7????????10??āā?????

?????????????????Χ????????

·2·

正正文.indd文.indd222020/4/14020/4/14115:54:345:54:34

第1章整理下背包

?????Ρ????????ǎ??Ρ???????????????р?????

?Ρ???????????????úú???ǎ

??????????????????????????????????????

?????????????????ǎ

??????Ρ????Χ?????ǎ

第1步首先，我們知道裝備價(jià)格最大是10，所以我們先準(zhǔn)備10個(gè)編號(hào)分別為1～10號(hào)

的桶，同時(shí)將每個(gè)桶的計(jì)數(shù)器設(shè)置為0，如下圖所示。

第2步我們將斗篷（3金）放入3號(hào)桶中，3號(hào)桶計(jì)數(shù)器+1。

第3步將護(hù)腕（1金）放入1號(hào)桶中，1號(hào)桶計(jì)數(shù)器+1。

·3·

正正文.indd文.indd322020/4/14020/4/14115:54:345:54:34

哇，編程！——跟小明一起學(xué)算法

第4步將冰杖（6金）放入6號(hào)桶中，6號(hào)桶計(jì)數(shù)器+1。

第5步將水銀鞋（3金）放入3號(hào)桶中，3號(hào)桶計(jì)數(shù)器+1，此時(shí)3號(hào)計(jì)數(shù)器累加到2，

表示有2個(gè)價(jià)格為3的裝備。

·4·

正正文.indd文.indd422020/4/14020/4/14115:54:345:54:34

第1章整理下背包

第6步將風(fēng)暴巨劍（10金）放入10號(hào)桶中，10號(hào)桶計(jì)數(shù)器+1。

第7步將圣杯（7金）放入7號(hào)桶中，7號(hào)桶計(jì)數(shù)器+1。

1?????????0?????????????????????????????

ǎ?2?????2??????????????1??

0??????????????Ρ?????1?10??????????????

2????2???āā??1????1??????????????

?1??2?????3???2??4?????5?????6???1??7??1

?1??8?????9?????10???1?ǎ??

????????????

·5·

正正文.indd文.indd522020/4/14020/4/14115:54:355:54:35

哇，編程！——跟小明一起學(xué)算法

?Χ???????????????????????Ρ?Ν??????????

???????Χ????ǎ?

???Ρ????????????Λ????

第1步首先，我們準(zhǔn)備一個(gè)數(shù)組bucket[11]來代表桶，bucket單詞就是桶的意思，

bucket[1]就表示編號(hào)為1的桶，用來對(duì)價(jià)格為1的裝備進(jìn)行計(jì)數(shù)；有同學(xué)可能會(huì)覺得奇怪

了，明明只要10個(gè)桶，bucket[]數(shù)組長(zhǎng)度為什么定義成11呢？同學(xué)們回想一下，我們?cè)?/p>

C語(yǔ)言基礎(chǔ)里學(xué)過的數(shù)組概念，由于數(shù)組的下標(biāo)是從0開始，bucket[11]表示是從bucket[0]

到bucket[10]的長(zhǎng)度為11的數(shù)組；如果我們只定義bucket[10]，那數(shù)組的最后一個(gè)元素是

bucket[9]，我們就沒地方放價(jià)格為10的道具。

第2步定義好bucket[]后，我們用memset函數(shù)將數(shù)組初始化，表示計(jì)數(shù)器初始化設(shè)置

為0。

第3步然后循環(huán)6個(gè)裝備的價(jià)格，將每個(gè)價(jià)格對(duì)應(yīng)的計(jì)數(shù)器+1。

第4步最后，按1～10順序，根據(jù)bucket數(shù)量，打印出數(shù)組下標(biāo)。

ǘΛ???ǚ

#include<iostream>

#include<cstdio>

usingnamespacestd;

intmain()

{

inti,j;

·6·

正正文.indd文.indd622020/4/14020/4/14115:54:355:54:35

第1章整理下背包

intn=6;

inta[6]={3,1,6,3,10,7};

//a[]最大數(shù)為10，需申請(qǐng)空間大小為10的buckets[]

intbuckets[11];

//將buckets中的所有數(shù)據(jù)都初始化為0，表示初始時(shí)每個(gè)桶的計(jì)數(shù)器都是0。

memset(buckets,0,sizeof(buckets));

//將a[]中的數(shù)分別放入對(duì)應(yīng)標(biāo)號(hào)的buckets中，每放入一個(gè)，計(jì)數(shù)器+1

for(i=0;i<n;i++){

buckets[a[i]]++;

}

//循環(huán)桶的標(biāo)號(hào)，根據(jù)每個(gè)桶的計(jì)數(shù)器打印出桶的標(biāo)號(hào)

for(i=1;i<11;i++)

for(j=0;j<buckets[i];j++)

{

printf("%d",i);

}

return0;

}

????????

???????????N????????????????Ρ?????????

?????????????????????????????????????ǎ

?????????????Ρ????????????????????????

???????????????????????к??Ρ??[2,1,9999999]????

???????Ρ???????bucket[1000000]????????Ρ???bucket[1]?

bucket[2]?bucket[9999999]???Γ??????Ρ???ǎ?Ν?????ζ?????

??????????????????ǎ

?Ρ????????????????????????O?n???????р?

?Ρ??t???????ǎ

??????????????????????????????????????

?????????Ν??????????úú???2.0?????????????

????????ǎ

к??Ρ?bucket[0]???Χ?0?9??????bucket[1]???Χ?10?19?

āā???Ρ????bucket[0]????bucket[2]???Χ?20?29????????

??????????????bucket[1]????????????????bucket[2]?

?????????????āā

·7·

正正文.indd文.indd722020/4/14020/4/14115:54:355:54:35

哇，編程！——跟小明一起學(xué)算法

???Ρ????????????10Ф???bucket[0]???Χ?0?99???

??Ρ????ζ????100Ф?1000Ф?????????Χ?0?999??????

??????????????????????2.5????????Ρ???????

??2.0Λ??ǎ

1.2冒泡排序

???????????????????????????????????Ρ??

??????????????t?????????????????????????

?????ǎ

???????????????????????????????bz?????d??

?????fbjj?????hw?????sb??????syx???Ρ?Ν????????

?р???ǎ

?????????Χ????????6.5??????Χ???????????

????????????????????????????????

?Ρ??t???????????úú????ǎ???????????????

???????????????????Ρ????????????????????

???ζ???????????ǎ???????????????????úú???

·8·

正正文.indd文.indd822020/4/14020/4/14115:54:355:54:35

第1章整理下背包

??????ǎ??

?Ρ?????????????Χ??????????????????

?????10??????7??????3??????1??????6?????

??3??

1．第一趟冒泡排序

第1步進(jìn)行第一次比較，比對(duì)第一位10和第二位7，10>7，交換位置。

第2步進(jìn)行第二次比較，比對(duì)第二位10（因上輪位置交換，此時(shí)第二位是10）和第三位3，

10>3，交換位置。

第3步進(jìn)行第三次比較，比對(duì)第三位10和第四位1，10>1，交換位置。

第4步進(jìn)行第四次比較，比對(duì)第四位10和第五位6，10>6，交換位置。

第5步進(jìn)行第五次比較，比對(duì)第五位10和第六位3，10>3，交換位置。

???????????????????????????????10???з?

?10??t????ǎ??????????ǎ????Ρ?Ν?????????з?

????Ρ?????????????????ǎ

2．第二趟冒泡排序

第1步進(jìn)行第一次比較，比對(duì)第一位7和第二位3，7>3，交換位置。

·9·

正正文.indd文.indd922020/4/14020/4/14115:54:365:54:36

哇，編程！——跟小明一起學(xué)算法

第2步進(jìn)行第二次比較，比對(duì)第二位7（因上輪位置交換，此時(shí)第二位是7）和第三位1，

7>1，交換位置。

第3步進(jìn)行第三次比較，比對(duì)第三位7和第四位6，7>6，交換位置。

第4步進(jìn)行第四次比較，比對(duì)第四位7和第五位3，7>3，交換位置。

?7????10?????????????????????????????з??

????????????????????????????????????????

?????t?????10???7????????з?????????????з?

??Ρ??????????????7?10??????N-1???????????ǎ?

????Ρ?????????????????ǎ

3．第三趟冒泡排序

第1步進(jìn)行第一次比較，比對(duì)第一位3和第二位1，3>1，交換位置。

第2步進(jìn)行第二次比較，比對(duì)第二位3（因上輪位置交換，此時(shí)第二位是3）和第三位6，

3<6，不交換位置。

第3步進(jìn)行第三次比較，比對(duì)第三位6（因上輪位置不交換，此時(shí)第三位還是6）和第四位3，

6>3，交換位置。

·10·

正正文.indd文.indd101022020/4/14020/4/14115:54:365:54:36

第1章整理下背包

?6????7?????????????ǎ???????????????з??

?????????????????????????????????3<6???

??δ??????????Ν?????????ǎ?Ρ??????????????

???ζ??t??ǎ????Ρ?????????????????ǎ???????з

???????????????????Ν??????Ρ???????????

??Ρ????????????????????????????????Ρ????

??t?????????1?3?3?Ρ?????Ρ??????????6?7?10?з??

??????t?????Ρ?????????????Ρ?????????????

р?????????Ρt???ǎ

4．第四趟冒泡排序

第1步進(jìn)行第一次比較，比對(duì)第一位1和第二位3，1<3，不交換位置。

第2步進(jìn)行第二次比較，比對(duì)第二位3和第三位3，此時(shí)兩個(gè)數(shù)值相等，我們可以進(jìn)行位

置交換，也可以不進(jìn)行位置交換，對(duì)最終排序結(jié)果沒有影響，為了少進(jìn)行一次交換操作，我

們不交換位置。

·11·

正正文.indd文.indd111122020/4/14020/4/14115:54:365:54:36

哇，編程！——跟小明一起學(xué)算法

?3????6?????????????ǎ???????????????з??

????Ρ????????????????????????Ρ???3???ǎ??

??Ρ?????????????????ǎ

5．第五趟冒泡排序

?????????????1????3?1<3??????ǎ

·12·

正正文.indd文.indd121222020/4/14020/4/14115:54:365:54:36

第1章整理下背包

?3????3?????????????ǎ???????????????з??

????Ρ???????????ǎ??????????????????t1???

???1?????????ǎ?