前端-計(jì)算機(jī)基礎(chǔ)

前端-計(jì)算機(jī)基礎(chǔ)一、網(wǎng)絡(luò)#1UDP面向報(bào)文UDP是一個(gè)面向報(bào)文（報(bào)文可以理解為一段段的數(shù)據(jù)）的協(xié)議。意思就是UDP只是報(bào)文的搬運(yùn)工,不會(huì)對報(bào)文進(jìn)行任何拆分和拼接操作具體來說在發(fā)送端，應(yīng)用層將數(shù)據(jù)傳遞給傳輸層的UDP協(xié)議，UDP只會(huì)給數(shù)據(jù)增加一個(gè)UDP頭標(biāo)識(shí)下是UDP協(xié)議，然后就傳遞給網(wǎng)絡(luò)層了在接收端，網(wǎng)絡(luò)層將數(shù)據(jù)傳遞給傳輸層，UDP只去除IP報(bào)文頭就傳遞給應(yīng)用層，不會(huì)任何拼接操作不可靠性UDP是無連接的，也就是說通信不需要建立和斷開連接。UDP也是不可靠的。協(xié)議收到什么數(shù)據(jù)就傳遞什么數(shù)據(jù)，并且也不會(huì)備份數(shù)據(jù),對方能不能收到是不關(guān)心的UDP沒有擁塞控制，一直會(huì)以恒定的速度發(fā)送數(shù)據(jù)。即使網(wǎng)絡(luò)條件不好，也不會(huì)對發(fā)送速率進(jìn)行調(diào)整。這樣實(shí)現(xiàn)的弊端就是在網(wǎng)絡(luò)條件不好的情況下可能會(huì)導(dǎo)致丟包，但是優(yōu)點(diǎn)也很明顯，在某些實(shí)時(shí)性要求高的場景（比如電話會(huì)議）就需要使用UDP而不是TCP高效?因?yàn)閁DP沒有TCP那么復(fù)雜，需要保證數(shù)據(jù)不丟失且有序到達(dá)。所以UDP的頭部開銷小，只有八字節(jié)，相比TCP的至少二十字節(jié)要少得多，在傳輸數(shù)據(jù)報(bào)文時(shí)是很高效的UDPHeader頭部包含了以下幾個(gè)數(shù)據(jù)兩個(gè)十六位的端口號(hào)，分別為源端口（可選字段）和目標(biāo)端口整個(gè)數(shù)據(jù)報(bào)文的長度整個(gè)數(shù)據(jù)報(bào)文的檢驗(yàn)和（IPv4可選字段），該字段用于發(fā)現(xiàn)頭部信息和數(shù)據(jù)中的錯(cuò)誤傳輸方式UDP不止支持一對一的傳輸方式，同樣支持一對多，多對多，多對一的方式，也就是說UDP提供了單播，多播，廣播的功能#2TCP2.1頭部TCP頭部比UDP頭部復(fù)雜的多TCPHeader對于TCP頭部來說，以下幾個(gè)字段是很重要的Sequencenumber,這個(gè)序號(hào)保證了TCP傳輸?shù)膱?bào)文都是有序的，對端可以通過序號(hào)順序的拼接報(bào)文AcknowledgementNumber,這個(gè)序號(hào)表示數(shù)據(jù)接收端期望接收的下一個(gè)字節(jié)的編號(hào)是多少，同時(shí)也表示上一個(gè)序號(hào)的數(shù)據(jù)已經(jīng)收到WindowSize,窗口大小，表示還能接收多少字節(jié)的數(shù)據(jù)，用于流量控制標(biāo)識(shí)符URG=1:該字段為一表示本數(shù)據(jù)報(bào)的數(shù)據(jù)部分包含緊急信息，是一個(gè)高優(yōu)先級(jí)數(shù)據(jù)報(bào)文，此時(shí)緊急指針有效。緊急數(shù)據(jù)一定位于當(dāng)前數(shù)據(jù)包數(shù)據(jù)部分的最前面，緊急指針標(biāo)明了緊急數(shù)據(jù)的尾部。ACK=1:該字段為一表示確認(rèn)號(hào)字段有效。此外，TCP還規(guī)定在連接建立后傳送的所有報(bào)文段都必須把ACK置為一PSH=1：該字段為一表示接收端應(yīng)該立即將數(shù)據(jù)push給應(yīng)用層，而不是等到緩沖區(qū)滿后再提交。RST=1:該字段為一表示當(dāng)前TCP連接出現(xiàn)嚴(yán)重問題，可能需要重新建立TCP連接，也可以用于拒絕非法的報(bào)文段和拒絕連接請求。SYN=1:當(dāng)SYN=1,ACK=0時(shí)，表示當(dāng)前報(bào)文段是一個(gè)連接請求報(bào)文。當(dāng)SYN=1,ACK=1時(shí)，表示當(dāng)前報(bào)文段是一個(gè)同意建立連接的應(yīng)答報(bào)文。FIN=1:該字段為一表示此報(bào)文段是一個(gè)釋放連接的請求報(bào)文

2.2狀態(tài)機(jī)HTTP是無連接的，所以作為下層的TCP協(xié)議也是無連接的，雖然看似TCP將兩端連接了起來，但是其實(shí)只是兩端共同維護(hù)了一個(gè)狀態(tài)■■■Aunusualevent><cbem/receivefpalhAservef/senderpath(Start)LISTEN/-CONNECT6YN(Step1ofthe3handshake)CLOSE/-CLOSE/-(Step2ofthe3-way-handshake)SYN/SYN+ACKRECEIVEDDataexchangeoccurs■■■Aunusualevent><cbem/receivefpalhAservef/senderpath(Start)LISTEN/-CONNECT6YN(Step1ofthe3handshake)CLOSE/-CLOSE/-(Step2ofthe3-way-handshake)SYN/SYN+ACKRECEIVEDDataexchangeoccursLISTENSEND/SYNSYN/SYN+ACK(simultaneousopen)SYN

SENTESTABLISHED(Step3ofthe3-way-handshake)SYN+ACK/ACKCLOS日臼NCLOS日臼NCLOS日FINFIN/ACKAN/ACKFINWAIT1]RN+ACK/ACKACKAFINWAIT2FIN/ACKActiveCLOSECLOSINGACK/-=AN/ACKFINWAIT1]RN+ACK/ACKACKAFINWAIT2FIN/ACKActiveCLOSECLOSINGACK/-=TIMEWAITTimeout(Gobacktostart)[CLOSEDTCP的狀態(tài)機(jī)是很復(fù)雜的，并且與建立斷開連接時(shí)的握手息息相關(guān)，接下來就來詳細(xì)描述下兩種握手。在這之前需要了解一個(gè)重要的性能指標(biāo)RTTo該指標(biāo)表示發(fā)送端發(fā)送數(shù)據(jù)到接收到對端數(shù)據(jù)所需的往返時(shí)間建立連接三次握手ClientServerClient在TCP協(xié)議中，主動(dòng)發(fā)起請求的一端為客戶端，被動(dòng)連接的一端稱為服務(wù)端。不管是客戶端還是服務(wù)端，TCP連接建立完后都能發(fā)送和接收數(shù)據(jù)，所以TCP也是一個(gè)全雙工的協(xié)議。起初，兩端都為CLOSED狀態(tài)。在通信開始前，雙方都會(huì)創(chuàng)建TCB。服務(wù)器創(chuàng)建完TCB后遍進(jìn)入LISTEN狀態(tài)，此時(shí)開始等待客戶端發(fā)送數(shù)據(jù)第一次握手客戶端向服務(wù)端發(fā)送連接請求報(bào)文段。該報(bào)文段中包含自身的數(shù)據(jù)通訊初始序號(hào)。請求發(fā)送后，客戶端便進(jìn)入SYN-SENT狀態(tài)，x表示客戶端的數(shù)據(jù)通信初始序號(hào)。第二次握手服務(wù)端收到連接請求報(bào)文段后，如果同意連接，則會(huì)發(fā)送一個(gè)應(yīng)答，該應(yīng)答中也會(huì)包含自身的數(shù)據(jù)通訊初始序號(hào)，發(fā)送完成后便進(jìn)入SYN-RECEIVED狀態(tài)。第三次握手當(dāng)客戶端收到連接同意的應(yīng)答后，還要向服務(wù)端發(fā)送一個(gè)確認(rèn)報(bào)文。客戶端發(fā)完這個(gè)報(bào)文段后便進(jìn)入ESTABLISHED狀態(tài)，服務(wù)端收到這個(gè)應(yīng)答后也進(jìn)入ESTABLISHED狀態(tài)，此時(shí)連接建立成功。PS:第三次握手可以包含數(shù)據(jù)，通過TCP快速打開（TFO）技術(shù)。其實(shí)只要涉及到握手的協(xié)議，都可以使用類似TFO的方式，客戶端和服務(wù)端存儲(chǔ)相同cookie,下次握手時(shí)發(fā)出cookie達(dá)到減少RTT的目的你是否有疑惑明明兩次握手就可以建立起連接，為什么還需要第三次應(yīng)答？因?yàn)檫@是為了防止失效的連接請求報(bào)文段被服務(wù)端接收，從而產(chǎn)生錯(cuò)誤

可以想象如下場景。客戶端發(fā)送了一個(gè)連接請求A,但是因?yàn)榫W(wǎng)絡(luò)原因造成了超時(shí)，這時(shí)TCP會(huì)啟動(dòng)超時(shí)重傳的機(jī)制再次發(fā)送一個(gè)連接請求B。此時(shí)請求順利到達(dá)服務(wù)端，服務(wù)端應(yīng)答完就建立了請求。如果連接請求A在兩端關(guān)閉后終于抵達(dá)了服務(wù)端，那么這時(shí)服務(wù)端會(huì)認(rèn)為客戶端又需要建立TCP連接，從而應(yīng)答了該請求并進(jìn)入ESTABLISHED狀態(tài)。此時(shí)客戶端其實(shí)是CLOSED狀態(tài)，那么就會(huì)導(dǎo)致服務(wù)端一直等待，造成資源的浪費(fèi)PS:在建立連接中，任意一端掉線，TCP都會(huì)重發(fā)SYN包，一般會(huì)重試五次，在建立連接中可能會(huì)遇到SYNFLOOD攻擊。遇到這種情況你可以選擇調(diào)低重試次數(shù)或者干脆在不能處理的情況下拒絕請求斷開鏈接四次握手InitiatorReceiverESTABLISHEDconnectionCLOSE_WAITpassivecloseLAST_ACKCLOSED第一次握手若客戶端A認(rèn)為數(shù)據(jù)發(fā)送完成，則它需要向服務(wù)端B發(fā)送連接釋放請求.第二次握手B收到連接釋放請求后，會(huì)告訴應(yīng)用層要釋放TCP鏈接。然后會(huì)發(fā)送ACK包，并進(jìn)入CLOSE_WAIT狀態(tài)，表示A到B的連接已經(jīng)釋放，不接收A發(fā)的數(shù)據(jù)了。但是因?yàn)門CP連接時(shí)雙向的，后以B仍舊可以發(fā)送數(shù)據(jù)給A。第三次握手B如果此時(shí)還有沒發(fā)完的數(shù)據(jù)會(huì)繼續(xù)發(fā)送，完畢后會(huì)向A發(fā)送連接釋放請求，然后B便進(jìn)入LASTACK狀態(tài)。PS：通過延遲確認(rèn)的技術(shù)（通常有時(shí)間限制，否則對方會(huì)誤認(rèn)為需要重傳），可以將第二次和第三次握手合并，延遲ACK包的發(fā)送。第四次握手A收到釋放請求后，向B發(fā)送確認(rèn)應(yīng)答，此時(shí)A進(jìn)入TIME-WAIT狀態(tài)。該狀態(tài)會(huì)持續(xù)2MSL（最大段生存期，指報(bào)文段在網(wǎng)絡(luò)中生存的時(shí)間，超時(shí)會(huì)被拋棄）時(shí)間，若該時(shí)間段內(nèi)沒有B的重發(fā)請求的話，就進(jìn)入CLOSED狀態(tài)。當(dāng)B收到確認(rèn)應(yīng)答后，也便進(jìn)入CLOSED狀態(tài)。為什么A要進(jìn)入TIME-WAIT狀態(tài)，等待2MSL時(shí)間后才進(jìn)入CLOSED狀態(tài)？為了保證B能收到A的確認(rèn)應(yīng)答。若A發(fā)完確認(rèn)應(yīng)答后直接進(jìn)入CLOSED狀態(tài)，如果確認(rèn)應(yīng)答因?yàn)榫W(wǎng)絡(luò)問題一直沒有到達(dá)，那么會(huì)造成B不能正常關(guān)閉3HTTPHTTP協(xié)議是個(gè)無狀態(tài)協(xié)議，不會(huì)保存狀態(tài)Post和Get的區(qū)另ljGet請求能緩存，Post不能Post相對Get安全一點(diǎn)點(diǎn)，因?yàn)镚et請求都包含在URL里，且會(huì)被瀏覽器保存歷史紀(jì)錄，Post不會(huì)，但是在抓包的情況下都是一樣的。Post可以通過requestbody來傳輸比Get更多的數(shù)據(jù)，Get沒有這個(gè)技術(shù)URL有長度限制，會(huì)影響Get請求，但是這個(gè)長度限制是瀏覽器規(guī)定的，不是RFC規(guī)定的Post支持更多的編碼類型且不對數(shù)據(jù)類型限制常見狀態(tài)碼2XX成功2000K,表示從客戶端發(fā)來的請求在服務(wù)器端被正確處理204Nocontent,表示請求成功，但響應(yīng)報(bào)文不含實(shí)體的主體部分205ResetContent,表示請求成功，但響應(yīng)報(bào)文不含實(shí)體的主體部分，但是與204響應(yīng)不同在于要求請求方重置內(nèi)容206PartialContent,進(jìn)行范圍請求3XX重定向301movedpermanently,永久性重定向，表示資源已被分配了新的URL302found,臨時(shí)性重定向，表示資源臨時(shí)被分配了新的URL303seeother,表示資源存在著另一個(gè)URL,應(yīng)使用GET方法丁香獲取資源304notmodified,表示服務(wù)器允許訪問資源，但因發(fā)生請求未滿足條件的情況307temporaryredirect,臨時(shí)重定向，和302含義類似，但是期望客戶端保持請求方法不變向新的地址發(fā)出請求4XX客戶端錯(cuò)誤400badrequest,請求報(bào)文存在語法錯(cuò)誤401unauthorized,表示發(fā)送的請求需要有通過HTTP認(rèn)證的認(rèn)證信息403forbidden,表示對請求資源的訪問被服務(wù)器拒絕404notfound,表示在服務(wù)器上沒有找到請求的資源5XX服務(wù)器錯(cuò)誤500internalsevererror,表示服務(wù)器端在執(zhí)行請求時(shí)發(fā)生了錯(cuò)誤501NotImplemented,表示服務(wù)器不支持當(dāng)前請求所需要的某個(gè)功能503serviceunavailable,表明服務(wù)器暫時(shí)處于超負(fù)載或正在停機(jī)維護(hù)，無法處理請求3.3HTTP首部通用字段作用Cache-Control控制緩存的行為Connection瀏覽器想要優(yōu)先使用的連接類型，比如keep-aliveDate創(chuàng)建報(bào)文時(shí)間Pragma報(bào)文指令Via代理服務(wù)器相關(guān)信息Transfer-Encoding傳輸編碼方式Upgrade要求客戶端升級(jí)協(xié)議Warning在內(nèi)容中可能存在錯(cuò)誤請求字段作用Accept能正確接收的媒體類型Accept-Charset能正確接收的字符集Accept-Encoding能正確接收的編碼格式列表Accept-Language能正確接收的語言列表Expect期待服務(wù)端的指定行為From請求方郵箱地址Host服務(wù)器的域名If-Match兩端資源標(biāo)記比較

If-Modified-SinceIf-None-MatchUser-AgentMax-ForwardsProxy-AuthorizationRangeRefererTE響應(yīng)字段Accept-RangesAgeETagLocationProxy-AuthenticateServerWWW-Authenticate實(shí)體字段AllowContent-EncodingContent-LanguageContent-LengthContent-Location本地資源未修改返回304（比較時(shí)間）本地資源未修改返回304（比較標(biāo)記）客戶端信息限制可被代理及網(wǎng)關(guān)轉(zhuǎn)發(fā)的次數(shù)向代理服務(wù)器發(fā)送驗(yàn)證信息請求某個(gè)內(nèi)容的一部分表示瀏覽器所訪問的前一個(gè)頁面?zhèn)鬏斁幋a方式作用是否支持某些種類的范圍資源在代理緩存中存在的時(shí)間資源標(biāo)識(shí)客戶端重定向到某個(gè)URL向代理服務(wù)器發(fā)送驗(yàn)證信息服務(wù)器名字獲取資源需要的驗(yàn)證信息作用資源的正確請求方式內(nèi)容的編碼格式內(nèi)容使用的語言requestbody長度返回?cái)?shù)據(jù)的備用地址Content-MD5Base64加密格式的內(nèi)容MD5檢驗(yàn)值Content-RangeContent-TypeExpiresLast_modified內(nèi)容的位置范圍內(nèi)容的媒體類型內(nèi)容的過期時(shí)間內(nèi)容的最后修改時(shí)間#4DNSDNS的作用就是通過域名查詢到具體的IP.因?yàn)镮P存在數(shù)字和英文的組合（IPv6）,很不利于人類記憶，所以就出現(xiàn)了域名。你可以把域名看成是某個(gè)IP的別名，DNS就是去查詢這個(gè)別名的真正名稱是什么在TCP握手之前就已經(jīng)進(jìn)行了DNS查詢，這個(gè)查詢是操作系統(tǒng)自己做的。當(dāng)你在瀏覽器中想訪問時(shí)，會(huì)進(jìn)行一下操作操作系統(tǒng)會(huì)首先在本地緩存中查詢沒有的話會(huì)去系統(tǒng)配置的DNS服務(wù)器中查詢?nèi)绻@時(shí)候還沒得話，會(huì)直接去DNS根服務(wù)器查詢，這一步查詢會(huì)找出負(fù)責(zé)com這個(gè)一級(jí)域名的服務(wù)器然后去該服務(wù)器查詢google這個(gè)二級(jí)域名接下來三級(jí)域名的查詢其實(shí)是我們配置的，你可以給WWW這個(gè)域名配置一個(gè)IP,然后還可以給別的三級(jí)域名配置一個(gè)IP以上介紹的是DNS迭代查詢，還有種是遞歸查詢，區(qū)別就是前者是由客戶端去做請求，后者是由系統(tǒng)配置的DNS服務(wù)器做請求，得到結(jié)果后將數(shù)據(jù)返回給客戶端。二、數(shù)據(jù)結(jié)構(gòu)2.1棧概念棧是一個(gè)線性結(jié)構(gòu)，在計(jì)算機(jī)中是一個(gè)相當(dāng)常見的數(shù)據(jù)結(jié)構(gòu)。棧的特點(diǎn)是只能在某一端添加或刪除數(shù)據(jù)，遵循先進(jìn)后出的原則實(shí)現(xiàn)每種數(shù)據(jù)結(jié)構(gòu)都可以用很多種方式來實(shí)現(xiàn)，其實(shí)可以把?？闯墒菙?shù)組的一個(gè)子集，所以這里使用數(shù)組來實(shí)現(xiàn)classStack{constructor(){this.stack=[]}push(item){this.stack.push(item)}pop(){this.stack.pop()}peek(){returnthis.stack[this.getCount()-1]}getCount(){returnthis.stack.length)一isEmpty(){returnthis.getCount()===0)一}應(yīng)用匹配括號(hào)，可以通過棧的特性來完成varisValid=function(s){letmap={'('：-1,1),：1,'['：-2,']'：2,-3,3)letstack=[]for(leti=0;i<s.length;i++){if(map[s[i]]<0){stack.push(s[i])}else{letlast=stack.pop()if(map[last]+map[s[i]]!=0)returnfalse}'')if(stack.length>0)returnfalsereturntrue}；#2.2隊(duì)列概念隊(duì)列一個(gè)線性結(jié)構(gòu)，特點(diǎn)是在某一端添加數(shù)據(jù)，在另一端刪除數(shù)據(jù)，遵循先進(jìn)先出的原則實(shí)現(xiàn)這里會(huì)講解兩種實(shí)現(xiàn)隊(duì)列的方式，分別是單鏈隊(duì)列和循環(huán)隊(duì)列? 單鏈隊(duì)列classQueue{constructor(){this.queue=[]}enQueue(item){this,queue.push(item)}deQueue(){returnthis.queue.shift()}getHeader(){returnthis.queue[0]}getLength(){returnthis.queue.length}一isEmpty(){returnthis.getLength()===0}「‘)因?yàn)閱捂滉?duì)列在出隊(duì)操作的時(shí)候需要0(n)的時(shí)間復(fù)雜度，所以引入了循環(huán)隊(duì)列。循環(huán)隊(duì)列的出隊(duì)操作平均是0(1)的時(shí)間復(fù)雜度? 循環(huán)隊(duì)列classSqQueue{constructor(length){this.queue=newArray(length+1)//隊(duì)頭this.first=0//隊(duì)尾this.last=0//當(dāng)前隊(duì)列大小this.size=0}enQueue(item){//判斷隊(duì)尾+1是否為隊(duì)頭//如果是就代表需要擴(kuò)容數(shù)組//%this.queue.length是為了防止數(shù)組越界if(this.first===(this.last+1)%this.queue.length){this.resize(this.getLength()*2+1)}一一this.queue[this.last]=itemthis.size++this.last=(this.last+1)%this.queue.length)一deQueue(){if(this.isEmpty()){throwError('Queueisempty'))letr=this.queue[this.first]this.queue[this.first]=nullthis.first=(this.first+1)%this.queue.lengththis,size--//判斷當(dāng)前隊(duì)列大小是否過小//為了保證不浪費(fèi)空間，在隊(duì)列空間等于總長度四分之一時(shí)//且不為2時(shí)縮小總長度為當(dāng)前的一半if(this.size===this.getLength()/4&&this.getLength()/2!==0){this.resize(this.getLength()/2)}..一returnr)getHeader(){if(this.isEmptyO){throwError('Queueisempty*))returnthis.queue[this.first]}getLength(){returnthis.queue.length-1)isEmpty(){returnthis.first===this.last}resize(length){letq=newArray(length)for(leti=0;i<length;i++){q[i]=this.queue[(i+this.first)%this.queue.length]}this.queue=qthis.first=0this.last=this.size))#2.3鏈表概念鏈表是一個(gè)線性結(jié)構(gòu)，同時(shí)也是一個(gè)天然的遞歸結(jié)構(gòu)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域,空間開銷比較大實(shí)現(xiàn)? 單向鏈表classNode{constructor(v,next){this.value=vthis.next=next})classLinkList{constructor(){//鏈表長度this.size=0//虛擬頭部this.dummyNode=newNode(null,null)}find(header,index,currentindex){if(index===currentindex)returnheaderreturnthis.find(header.next,index,currentindex+1)addNode(v,index){this.checkindex(index)//當(dāng)往鏈表末尾插入時(shí)，prev.next為空//其他情況時(shí)，因?yàn)橐迦牍?jié)點(diǎn)，所以插入的節(jié)點(diǎn)//的next應(yīng)該是prev.next//然后設(shè)置prev.next為插入的節(jié)點(diǎn)letprev=this.find(this.dummyNode,index,0)prev.next=newNode(v,prev.next)this.size++returnprev.next}insertNodeCv,index){returnthis.addNode(Vjindex))addToFirst(v){returnthis.addNode(v,0)}addToLast(v){returnthis?addNode(v,this.size)}removeNode(index,isLast){this.checkindex(index)index=isLast?index-1:indexletprev=this.find(this.dummyNodejindex,0)letnode=prev.nextprev.next=node.nextnode.next=nullthis,size-returnnode}removeFirstNode(){returnthis.removeNode(O))removeLastNode(){returnthis.removeNode(this.size,true)}checkindex(index){if(index<0||index>this.size)throwError(1Indexerror')}getNode(index){this.checkindex(index)if(this.isEmpty())returnreturnthis.find(this.dummyNode,index,0).next}isEmpty(){returnthis.size===0}getSize(){returnthis.size#2.4樹二叉樹樹擁有很多種結(jié)構(gòu)，二叉樹是樹中最常用的結(jié)構(gòu)，同時(shí)也是一個(gè)天然的遞歸結(jié)構(gòu)。二叉樹擁有一個(gè)根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)至多擁有兩個(gè)子節(jié)點(diǎn)，分別為：左節(jié)點(diǎn)和右節(jié)點(diǎn)。樹的最底部節(jié)點(diǎn)稱之為葉節(jié)點(diǎn)，當(dāng)一顆樹的葉數(shù)量數(shù)量為滿時(shí)，該樹可以稱之為滿二叉樹二分搜索樹二分搜索樹也是二叉樹，擁有二叉樹的特性。但是區(qū)別在于二分搜索樹每個(gè)節(jié)點(diǎn)的值都比他的左子樹的值大，比右子樹的值小這種存儲(chǔ)方式很適合于數(shù)據(jù)搜索。如下圖所示，當(dāng)需要查找6的時(shí)候，因?yàn)樾枰檎业闹当雀?jié)點(diǎn)的值大，所以只需要在根節(jié)點(diǎn)的右子樹上尋找，大大提高了搜索效率5實(shí)現(xiàn)classNode{constructor(value){this.value=valuethis.left=nullthis.right=null)}classBST{constructor(){this.root=nullthis.size=0)getSize(){returnthis.size)isEmpty(){returnthis.size===0)addNode(v){this.root=this._addChild(this.root,v)//添加節(jié)點(diǎn)時(shí)，需要比較添加的節(jié)點(diǎn)值和當(dāng)前//節(jié)點(diǎn)值的大小_addChild(nodeJv){if(!node){this.size++returnnewNode(v)}if(node.value>v){node.left=this._addChild(node.left,v)}elseif(node.value<v){node.right=this._addChild(node.right,v)}一一「returnnode以上是最基本的二分搜索樹實(shí)現(xiàn)，接下來實(shí)現(xiàn)樹的遍歷。對于樹的遍歷來說，有三種遍歷方法，分別是先序遍歷、中序遍歷、后序遍歷。三種遍歷的區(qū)別在于何時(shí)訪問節(jié)點(diǎn)。在遍歷樹的過程中，每個(gè)節(jié)點(diǎn)都會(huì)遍歷三次，分別是遍歷到自己，遍歷左子樹和遍歷右子樹。如果需要實(shí)現(xiàn)先序遍歷，那么只需要第一次遍歷到節(jié)點(diǎn)時(shí)進(jìn)行操作即可//先序遍歷可用于打印樹的結(jié)構(gòu)//先序遍歷先訪問根節(jié)點(diǎn)，然后訪問左節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)。preTraversal(){this._pre(this.root)}"_pre(node){'if(node){console.log(node.value)this._pre(node.left)this._pre(node.right)))//中序遍歷可用于排序//對于BST來說，中序遍歷可以實(shí)現(xiàn)一次遍歷就//得到有序的值//中序遍歷表示先訪問左節(jié)點(diǎn)，然后訪問根節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)。midTraversal(){this._mid(this,root)}一_mid(node){if(node){this._mid(node.left)console.log(node.value)this._mid(node.right)))//后序遍歷可用于先操作子節(jié)點(diǎn)//再操作父節(jié)點(diǎn)的場景//后序遍歷表示先訪問左節(jié)點(diǎn)，然后訪問右節(jié)點(diǎn)，最后訪問根節(jié)點(diǎn)。backTraversal(){this._back(this.root)}一_back(node){-if(node){this._back(node.left)this._back(node.right)console.log(node.value)以上的這幾種遍歷都可以稱之為深度遍歷，對應(yīng)的還有種遍歷叫做廣度遍歷，也就是一層層地遍歷樹。對于廣度遍歷來說，我們需要利用之前講過的隊(duì)列結(jié)構(gòu)來完成breadthTraversal(){if(ithis.root)returnnullletq=newQueue()//將根節(jié)點(diǎn)入隊(duì)q,enQueue(this.root)//循環(huán)判斷隊(duì)列是否為空，為空//代表樹遍歷完畢while(!q.isEmpty()){//將隊(duì)首出隊(duì)，判斷是否有左右子樹//有的話，就先左后右入隊(duì)letn=q.deQueue()console.log(n.value)if(n.left)q.enQueue(n.left)if(n.right)q.enQueue(n.right)}}接下來先介紹如何在樹中尋找最小值或最大數(shù)。因?yàn)槎炙阉鳂涞奶匦?，所以最小值一定在根?jié)點(diǎn)的最左邊，最大值相反getMin(){returnthis.__getMin(this.root).value}一_getMin(node){if(inode.left)returnnodereturnthis._getMin(node.left)}一^getMax(){returnthis._getMax(this.root).value}一_getMax(node){if(!node.right)returnnodereturnthis.__getMin(node.right)向上取整和向下取整，這兩個(gè)操作是相反的，所以代碼也是類似的，這里只介紹如何向下取整。既然是向下取整，那么根據(jù)二分搜索樹的特性，值一定在根節(jié)點(diǎn)的左側(cè)。只需要一直遍歷左子樹直到當(dāng)前節(jié)點(diǎn)的值不再大于等于需要的值，然后判斷節(jié)點(diǎn)是否還擁有右子樹。如果有的話，繼續(xù)上面的遞歸判斷floor(v){letnode=this._floor(this.root^v)returnnode?node.value:null}_floor(node,v){if(!node)returnnullif(node.value===v)returnv//如果當(dāng)前節(jié)點(diǎn)值還比需要的值大，就繼續(xù)遞歸if(node.value>v){returnthis._floon(node.leftv)}//判斷當(dāng)前節(jié)點(diǎn)是否擁有右子樹letright=this.__floon(node.right,v)if(right)returnrightreturnnode}排名，這是用于獲取給定值的排名或者排名第幾的節(jié)點(diǎn)的值，這兩個(gè)操作也是相反的，所以這個(gè)只介紹如何獲取排名第幾的節(jié)點(diǎn)的值。對于這個(gè)操作而言，我們需要略微的改造點(diǎn)代碼，讓每個(gè)節(jié)點(diǎn)擁有一個(gè)size屬性。該屬性表示該節(jié)點(diǎn)下有多少子節(jié)點(diǎn)(包含自身)classNode{constructor(value){this.value=valuethis.left=nullthis.right=null//修改代碼this.size=1)}//新增代碼_getSize(node){returnnode?node.size:0}_addChild(nodeJv){if(inode){returnnewNode(v))if(node.value>v){//修改代碼node.size++node.left=this._addChild(node.left,v)}elseif(node.value<v){//修改代碼node.size++node.right=this._addChild(node.right,v)returnnode)select(k){letnode=this._select(this.rootk)returnnode?node.value:null}_select(nodejk){if(inode)returnnull//先獲取左子樹下有幾個(gè)節(jié)點(diǎn)letsize=node.left?node.left.size:0//判斷size是否大于k//如果大于k,代表所需要的節(jié)點(diǎn)在左節(jié)點(diǎn)if(size>k)returnthis._select(node.left,k)//如果小于k,代表所需要的節(jié)點(diǎn)在右節(jié)點(diǎn)//注意這里需要重新計(jì)算k,減去根節(jié)點(diǎn)除了右子樹的節(jié)點(diǎn)數(shù)量if(size<k)returnthis._select(node.right,k-size-1)returnnode)接下來講解的是二分搜索樹中最難實(shí)現(xiàn)的部分：刪除節(jié)點(diǎn)。因?yàn)閷τ趧h除節(jié)點(diǎn)來說，會(huì)存在以下幾種情況需要?jiǎng)h除的節(jié)點(diǎn)沒有子樹需要?jiǎng)h除的節(jié)點(diǎn)只有一條子樹需要?jiǎng)h除的節(jié)點(diǎn)有左右兩條樹對于前兩種情況很好解決，但是第三種情況就有難度了，所以先來實(shí)現(xiàn)相對簡單的操作：刪除最小節(jié)點(diǎn)，對于刪除最小節(jié)點(diǎn)來說，是不存在第三種情況的，刪除最大節(jié)點(diǎn)操作是和刪除最小節(jié)點(diǎn)相反的，所以這里也就不再贅述delectMin(){this.root=this._delectMin(this.root)console.log(this.root)}_delectMin(node){//一直遞歸左子樹//如果左子樹為空，就判斷節(jié)點(diǎn)是否擁有右子樹//有右子樹的話就把需要?jiǎng)h除的節(jié)點(diǎn)替換為右子樹if((node!=null)&!node.left)returnnode.rightnode.left=this._delectMin(node.left)//最后需要重新維濟(jì)下節(jié)點(diǎn)的'size'node.size=this._getSize(node.left)+this._getSize(node.right)+1returnnode}最后講解的就是如何刪除任意節(jié)點(diǎn)了。對于這個(gè)操作，T.Hibbard在1962年提出了解決這個(gè)難題的辦法，也就是如何解決第三種情況。?當(dāng)遇到這種情況時(shí)，需要取出當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)(也就是當(dāng)前節(jié)點(diǎn)右子樹的最小節(jié)點(diǎn))來替換需要?jiǎng)h除的節(jié)點(diǎn)。然后將需要?jiǎng)h除節(jié)點(diǎn)的左子樹賦值給后繼結(jié)點(diǎn)，右子樹刪除后繼結(jié)點(diǎn)后賦值給他。你如果對于這個(gè)解決辦法有疑問的話，可以這樣考慮。因?yàn)槎炙阉鳂涞奶匦?父節(jié)點(diǎn)一定比所有左子節(jié)點(diǎn)大，比所有右子節(jié)點(diǎn)小。那么當(dāng)需要?jiǎng)h除父節(jié)點(diǎn)時(shí),勢必需要拿出一個(gè)比父節(jié)點(diǎn)大的節(jié)點(diǎn)來替換父節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)肯定不存在于左子樹，必然存在于右子樹。然后又需要保持父節(jié)點(diǎn)都是比右子節(jié)點(diǎn)小的，那么就可以取出右子樹中最小的那個(gè)節(jié)點(diǎn)來替換父節(jié)點(diǎn)delect(v){this.root=this._delect(this.rootv)}一_delect(nodejv){if(!node)returnnull//尋找的節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)小，去左子樹找if(node.value<v){node.right=this._delect(node.right,v)}elseif(node.value>v){//尋找的節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)大，去右子樹找node.left=this._delect(node.left,v)}else{//進(jìn)入這個(gè)條件說明己經(jīng)找到節(jié)點(diǎn)//先判斷節(jié)點(diǎn)是否擁有擁有左右子樹中的一個(gè)//是的話，將子樹返回出去，這里和'_delectMin'的操作一樣if(!node.left)returnnode.rightif(!node.right)returnnode.left//進(jìn)入這里，代表節(jié)點(diǎn)擁有左右子樹//先取出當(dāng)前節(jié)點(diǎn)的后繼結(jié)點(diǎn)，也就是取當(dāng)前節(jié)點(diǎn)右子樹的最小值letmin=this._getMin(node.right)//取出最小值后，刪除最小值//然后把刪除節(jié)點(diǎn)后的子樹賦值給最小值節(jié)點(diǎn)min.right=this._delectMin(node.right)//左子樹不動(dòng)min.left=node.leftnode=min}//維護(hù)sizenode.size=this._getSize(node.left)+this._getSize(node.right)+1returnnode}2.5堆概念?堆通常是一個(gè)可以被看做一棵樹的數(shù)組對象。?堆的實(shí)現(xiàn)通過構(gòu)造二叉堆，實(shí)為二叉樹的一種。這種數(shù)據(jù)結(jié)構(gòu)具有以下性質(zhì)。

任意節(jié)點(diǎn)小于（或大于）它的所有子節(jié)點(diǎn)堆總是一棵完全樹。即除了最底層,其他層的節(jié)點(diǎn)都被元素填滿，且最底層從左到右填入。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。優(yōu)先隊(duì)列也完全可以用堆來實(shí)現(xiàn)，操作是一模一樣的。實(shí)現(xiàn)大根堆堆的每個(gè)節(jié)點(diǎn)的左邊子節(jié)點(diǎn)索引是i*2+1,右邊是i*2+2,父節(jié)點(diǎn)是（i-1）/2。? 堆有兩個(gè)核心的操作，分別是shiftUp和shiftDown。前者用于添加元素，后者用于刪除根節(jié)點(diǎn)。shiftUp的核心思路是一路將節(jié)點(diǎn)與父節(jié)點(diǎn)對比大小，如果比父節(jié)點(diǎn)大，就和父節(jié)點(diǎn)交換位置。?? S—StoiE?@?。-黑瞄一Jr)swimup、?? S—StoiE?@?。-黑瞄一Jr)swimup、removethemaximum /^\ .(TJ!"—krytortmovt????-嗑六石、—violatesheaporder?%<7$ --removenode市Yr；????classMaxHeap{constructor(){this.heap=[]}size(){returnthis.heap.length)一w2?3w???Heapoperationssinkdownempty(){returnthis.size()==0}add(item){this,heap.push(item)this._shiftllp(this.size()-1)}一removeMax(){this._shiftDown(0)}一getParentlndex(k){returnparselnt((k-1)/2)}getLeftlndex(k){returnk*2+1)_shiftllp(k){一//如果當(dāng)前節(jié)點(diǎn)比父節(jié)點(diǎn)大，就交換while(this.heap[k]>this.heap[this.getParentIndex(k)]){this._swap(k,this.getParentIndex(k))//將素引變成父節(jié)點(diǎn)k=this.getParentindex(k))一)_shiftDown(k){//交換首位并刪除末尾this?_swap(k,this.size()-1)this.heap.splice(this.size()-1,1)//判斷節(jié)點(diǎn)是否有左孩子，因?yàn)槎娑训奶匦?，有右必有左while(this.getLeftIndex(k)<this.size()){letj=this.getLeftlndex(k)//判斷是否有右孩子，并且右孩子是否大于左孩子if(j+1<this.size()&&this.heap[j+1]>this.heap[j])j++//判斷父節(jié)點(diǎn)是否已經(jīng)比子節(jié)點(diǎn)都大if(this.heap[k]>=this.heap[j])breakthis._swap(kJj)k=j)}_swap(left,right){letrightvalue=this.heap[right]this.heap[right]=this.heap[left]this.heap[left]=rightvalue#三、算法3.1時(shí)間復(fù)雜度通常使用最差的時(shí)間復(fù)雜度來衡量一個(gè)算法的好壞。常數(shù)時(shí)間0(1)代表這個(gè)操作和數(shù)據(jù)量沒關(guān)系，是一個(gè)固定時(shí)間的操作，比如說四則運(yùn)算。對于一個(gè)算法來說，可能會(huì)計(jì)算出如下操作次數(shù)aN+1,N代表數(shù)據(jù)量。那么該算法的時(shí)間復(fù)雜度就是0(N)。因?yàn)槲覀冊谟?jì)算時(shí)間復(fù)雜度的時(shí)候，數(shù)據(jù)量通常是非常大的，這時(shí)候低階項(xiàng)和常數(shù)項(xiàng)可以忽略不計(jì)。當(dāng)然可能會(huì)出現(xiàn)兩個(gè)算法都是0(N)的時(shí)間復(fù)雜度，那么對比兩個(gè)算法的好壞就要通過對比低階項(xiàng)和常數(shù)項(xiàng)了3.2位運(yùn)算位運(yùn)算在算法中很有用，速度可以比四則運(yùn)算快很多。在學(xué)習(xí)位運(yùn)算之前應(yīng)該知道十進(jìn)制如何轉(zhuǎn)二進(jìn)制，二進(jìn)制如何轉(zhuǎn)十進(jìn)制。這里說明下簡單的計(jì)算方式十進(jìn)制33可以看成是32+1,并且33應(yīng)該是六位二進(jìn)制的(因?yàn)?3近似32,而32是2的五次方，所以是六位)，那么十進(jìn)制33就是100001,只要是2的次方，那么就是1否則都為0那么二進(jìn)制100001同理，首位是27,末位是2A0,相加得出33左移"10<<1//->20左移就是將二進(jìn)制全部往左移動(dòng)，1。在二進(jìn)制中表示為101。，左移一位后變成10100，轉(zhuǎn)換為十進(jìn)制也就是20,所以基本可以把左移看成以下公式a*(2人b)算數(shù)右移>>10>>1//->5算數(shù)右移就是將二進(jìn)制全部往右移動(dòng)并去除多余的右邊，10在二進(jìn)制中表示為右移一位后變成轉(zhuǎn)換為十進(jìn)制也就是5,所以基本可以把右移看成以下公式intv=a/(2Ab)右移很好用，比如可以用在二分算法中取中間值13>>1//->6按位操作?按位與每一位都為1,結(jié)果才為18&7//->0//1000&0111->0000->0?按位或其中一位為1,結(jié)果就是18|7//->15//1000|0111->1111->15?按位異或每一位都不同，結(jié)果才為18A7//->158A8//->0//1000A0111->1111->15//1000A1000->0000->0面試題：兩個(gè)數(shù)不使用四則運(yùn)算得出和這道題中可以按位異或，因?yàn)榘次划惢蚓褪遣贿M(jìn)位加法，8八8=0如果進(jìn)位了，就是16了，所以我們只需要將兩個(gè)數(shù)進(jìn)行異或操作，然后進(jìn)位。那么也就是說兩個(gè)二進(jìn)制都是1的位置，左邊應(yīng)該有一個(gè)進(jìn)位1,所以可以得出以下公式a+b=(aAb)+((a&b)?1),然后通過迭代的方式模擬加法functionsum(a,b){if(a==0)returnbif(b==0)returnaletnewA=aAbletnewB=(a&b)<<1returnsum(newAjnewB)}#3.3排序冒泡排序冒泡排序的原理如下，從第一個(gè)元素開始，把當(dāng)前元素和下一個(gè)索引元素進(jìn)行比較。如果當(dāng)前元素大，那么就交換位置，重復(fù)操作直到比較到最后一個(gè)元素，那么此時(shí)最后一個(gè)元素就是該數(shù)組中最大的數(shù)。下一輪重復(fù)以上操作，但是此時(shí)最后一個(gè)元素已經(jīng)是最大數(shù)了，所以不需要再比較最后一個(gè)元素，只需要比較到length-1的位置

以下是實(shí)現(xiàn)該算法的代碼functionbubble(array){checkArray(array);for(leti=array.length-1;i>0;i--){〃從0到'length-1'遍歷for(letj=0;j<i;j++){if(array[j]>array[j+1])swap(array,j,j+1)))returnarray;該算法的操作次數(shù)是一個(gè)等差數(shù)列n+(n-1)+(n-2)+1,去掉常數(shù)項(xiàng)以后得出時(shí)間復(fù)雜度是0(n*n)插入排序入排序的原理如下。第一個(gè)元素默認(rèn)是已排序元素，取出下一個(gè)元素和當(dāng)前元素比較，如果當(dāng)前元素大就交換位置。那么此時(shí)第一個(gè)元素就是當(dāng)前的最小數(shù)，所以下次取出操作從第三個(gè)元素開始，向前對比，重復(fù)之前的操作

以下是實(shí)現(xiàn)該算法的代碼3626以下是實(shí)現(xiàn)該算法的代碼3626functioninsertion(array){checkArray(array);for(leti=1;i<array.length;i++){for(letj=i-1;j>=0&&array[j]>array[j+1];j--)swap(array,j,j+1)；)returnarray;}該算法的操作次數(shù)是一個(gè)等差數(shù)列n+(n-1)+(n-2)+1,去掉常數(shù)項(xiàng)以后得出時(shí)間復(fù)雜度是0(n*n)選擇排序選擇排序的原理如下。遍歷數(shù)組，設(shè)置最小值的索引為0,如果取出的值比當(dāng)前最小值小，就替換最小值索引，遍歷完成后，將第一個(gè)元素和最小值索引上的值交換。如上操作后，第一個(gè)元素就是數(shù)組中的最小值，下次遍歷就可以從索引1開始重復(fù)上述操作

381536381536以下是實(shí)現(xiàn)該算法的代碼functionselection(array){checkArray(array);for(leti=0;i<array.length-1;i++){letminindex=i;for(letj=i+1;j<array.length;j++){minindex=array［j］<array［minlndex］?j:minindex;)一swap(array,i,minindex);}returnarray;)該算法的操作次數(shù)是一個(gè)等差數(shù)列n+(n-1)+(n-2)+1,去掉常數(shù)項(xiàng)以后得出時(shí)間復(fù)雜度是0(n*n)歸并排序歸并排序的原理如下。遞歸的將數(shù)組兩兩分開直到最多包含兩個(gè)元素，然后將數(shù)組排序合并，最終合并為排序好的數(shù)組。假設(shè)我有一組數(shù)組［3,1,2,8,9,7,6］,中間數(shù)索引是3,先排序數(shù)組［3,1,2,8］.在這個(gè)左邊數(shù)組上，繼續(xù)拆分直到變成數(shù)組包含兩個(gè)元素(如果數(shù)組長度是奇數(shù)的話，會(huì)有一個(gè)拆分?jǐn)?shù)組只包含一個(gè)元素)。然后排序數(shù)組［3,1］和［2,8］,然后再排序數(shù)組［1,3,2,8］,這樣左邊數(shù)組就排序完成，然后按照以上思路排序右邊數(shù)組，最后將數(shù)組［1,2,3,8］和［6,7,9］排序

以下是實(shí)現(xiàn)該算法的代碼functionsort(array){checkArray(array);mergeSort(array,0,array.length-1);returnarray;}functionmergeSort(array,left,right){//左右索引相同說明已經(jīng)只有一個(gè)數(shù)if(left===right)return;//尊同于'left+(right-left)/2'//相比'(left+right)/2'來說更加安全，不會(huì)溢出//使用位運(yùn)算是因?yàn)槲贿\(yùn)算比四則運(yùn)算快letmid=parselnt(left+((right-left)>>1));mergeSort(array.,left,mid);mergeSort(array,mid+1,right);lethelp=[];leti=0;letpl=left;letp2=mid+1;while(pl<=mid&&p2<=right){help[i++]=array[pl]<array[p2]?array[pl++]:array[p2++];)'while(pl<=mid){help[i++]=array[pl++];}while(p2<=right){help[i++]=array[p2++];for(leti=0;i<help.length;i++){array[left+i]=help[i];)returnarray;}以上算法使用了遞歸的思想。遞歸的本質(zhì)就是壓棧，每遞歸執(zhí)行一次函數(shù)，就將該函數(shù)的信息(比如參數(shù)，內(nèi)部的變量，執(zhí)行到的行數(shù))壓棧，直到遇到終止條件，然后出棧并繼續(xù)執(zhí)行函數(shù)。對于以上遞歸函數(shù)的調(diào)用軌跡如下mergeSort(data,0,6)//mid=3mergeSort(data,0,3)//mid=1mergeSort(data,0,1)//mid=0mergeSortCdata,0,0)//遇到終止，回退到上一步mergeSort(data,1,1)//遇到終止，回退到上一步//排序pl=0,p2=mid+1=1//回退到'mergeSort(data,0,3)'執(zhí)行下一個(gè)遞歸mergeSort(2,3)//mid=2mergeSort(3,3)//遇到終止，回退到上一步//排序pl=2,p2=mid+1=3//回退到'mergeSort(data,0,3)'執(zhí)行合并邏輯//排序pl=p2=mid+1=2//執(zhí)行完畢回退//左邊數(shù)組排序完畢，右邊也是如上軌跡該算法的操作次數(shù)是可以這樣計(jì)算：遞歸了兩次，每次數(shù)據(jù)量是數(shù)組的一半，并且最后把整個(gè)數(shù)組迭代了一次，所以得出表達(dá)式2T(N/2)+T(N)(T代表時(shí)間，N代表數(shù)據(jù)量)。根據(jù)該表達(dá)式可以套用該公式得出時(shí)間復(fù)雜度為0(N*logN)快排

快排的原理如下。隨機(jī)選取一個(gè)數(shù)組中的值作為基準(zhǔn)值，從左至右取值與基準(zhǔn)值對比大小。比基準(zhǔn)值小的放數(shù)組左邊，大的放右邊，對比完成后將基準(zhǔn)值和第一個(gè)比基準(zhǔn)值大的值交換位置。然后將數(shù)組以基準(zhǔn)值的位置分為兩部分，繼續(xù)遞歸以上操作。以下是實(shí)現(xiàn)該算法的代碼functionsort(array){checkArray(array);quicksort(array,0,array.length-1);returnarray;}functionquicksort(arrayleft,right){if(left<right){swap(array,,right)//隨機(jī)取值，然后和末尾交換，這樣做比固定取一個(gè)位置的復(fù)雜度略低letindexs=part(array,parseInt(Math.random()*(right-left+1))+left,right);quicksort(arrayleft,indexs[0]);quickSortCarray^indexs[l]+1,right);}}functionpart(array,left,right){letless=left-1;letmore=right;while(left<more){if(array[left]<array[right]){//當(dāng)前值比基準(zhǔn)值小，'less'和'left'都加一++less;++left;}elseif(array[left]>array[right]){〃當(dāng)前值比基準(zhǔn)值大，將當(dāng)前值和右邊的值交換//并且不改變'left',因?yàn)楫?dāng)前換過來的值還沒有判斷過大小swap(array,--more,left);}else{//和基準(zhǔn)值相同，只移動(dòng)下標(biāo)left++;))//將基準(zhǔn)值和比基準(zhǔn)值大的第一個(gè)值交換位置//這樣數(shù)組就變成'[比基準(zhǔn)值小，基準(zhǔn)值，比基準(zhǔn)值大]'swap(array,right,more);return[less,more];)該算法的復(fù)雜度和歸并排序是相同的，但是額外空間復(fù)雜度比歸并排序少，只需O(logN),并且相比歸并排序來說，所需的常數(shù)時(shí)間也更少面試題SortColors：該題目來自LeetCode,題目需要我們將[2,2,1,0]排序成[0,0,1,1,2,2],這個(gè)問題就可以使用三路快排的思想vansortcolors=function(nums){letleft=-1;letright=nums.length;leti=0;//下標(biāo)如果遇到right,說明已經(jīng)排序完成while(i<right){if(nums[i]==0){swap(nums,i++,++left);}elseif(nums[i]==1){i++；}else{swap(nums,i,--right);)))；#3.4鏈表反轉(zhuǎn)單向鏈表該題目來自LeetCode,題目需要將一個(gè)單向鏈表反轉(zhuǎn)。思路很簡單，使用三個(gè)變量分別表示當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的前后節(jié)點(diǎn)，雖然這題很簡單，但是卻是一道面試?？碱}vanreverseList=function(head){//判斷下變量邊界問題if(!head||!head.next)returnhead//初始設(shè)置為空，因?yàn)榈谝粋€(gè)節(jié)點(diǎn)反轉(zhuǎn)后就是尾部，尾部節(jié)點(diǎn)指向nullletpre=nullletcurrent=headletnext//判斷當(dāng)前節(jié)點(diǎn)是否為空//不為空就先獲取當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)//然后把當(dāng)前節(jié)點(diǎn)的next設(shè)為上一個(gè)節(jié)點(diǎn)//然后把current設(shè)為下一個(gè)節(jié)點(diǎn)，pre設(shè)為當(dāng)前節(jié)點(diǎn)while(current){next=current.nextcurrent.next=prepre=currentcurrent=next)returnpre};3.5樹二叉樹的先序，中序，后序遍歷先序遍歷表示先訪問根節(jié)點(diǎn)，然后訪問左節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)。?中序遍歷表示先訪問左節(jié)點(diǎn)，然后訪問根節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)。后序遍歷表示先訪問左節(jié)點(diǎn)，然后訪問右節(jié)點(diǎn)，最后訪問根節(jié)點(diǎn)遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)相當(dāng)簡單，代碼如下functionTreeNode(val){this.val=val;this.left=this.right=null;}一vartraversal=function(root){if(root){//先序console.log(root);traversal(root,left);//中序//console.log(root);traversal(root.right);//后序//console.log(root);}}；對于遞歸的實(shí)現(xiàn)來說，只需要理解每個(gè)節(jié)點(diǎn)都會(huì)被訪問三次就明白為什么這樣實(shí)現(xiàn)了非遞歸實(shí)現(xiàn)非遞歸實(shí)現(xiàn)使用了棧的結(jié)構(gòu)，通過