☆怦然*%心☆_☆動(dòng)传轰，你好剩盒！
我們昨天的內(nèi)容算是一個(gè)鋪墊，確立了評(píng)判計(jì)算機(jī)算法好壞的基礎(chǔ)和標(biāo)準(zhǔn)慨蛙。今天我們以計(jì)算機(jī)科學(xué)中最常見(jiàn)的算法——排序算法為例辽聊，說(shuō)說(shuō)提高效率的本質(zhì)。
排序是我們?cè)谏钪薪?jīng)常會(huì)遇到的事情期贫。在學(xué)校里老師會(huì)把一個(gè)年級(jí)的學(xué)生按照成績(jī)排序跟匆，或者按照中學(xué)所在的地域排序；做電商的人通砍，可能需要把所銷(xiāo)售的各種商品按照收入或者交易量排序玛臂。排完序，我們有時(shí)就能看出很多規(guī)律埠帕，或者作進(jìn)一步的處理了垢揩。比如，給學(xué)生排完序老師就可以評(píng)獎(jiǎng)學(xué)金或者建議推研了敛瓷，電商對(duì)銷(xiāo)售根據(jù)一些選項(xiàng)排序后，就能改進(jìn)自己的業(yè)務(wù)了斑匪。將現(xiàn)實(shí)世界的這些問(wèn)題呐籽，變成計(jì)算機(jī)可以運(yùn)行的程序，中間的橋梁就是排序算法蚀瘸。
計(jì)算機(jī)最早的排序算法源于人的生活和經(jīng)驗(yàn)狡蝶，這就如同最早的計(jì)算機(jī)下棋是模仿人，最早設(shè)計(jì)的飛行器是模仿鳥(niǎo)一樣贮勃。那么我們?nèi)耸窃趺磁判虻哪靥叭牵咳绻挥腥鍌€(gè)數(shù)字，我們可以掃一眼就排完了序寂嘉。但如果到幾十個(gè)數(shù)字奏瞬，這就有點(diǎn)麻煩了枫绅，因?yàn)槿绻麤](méi)有一個(gè)必須嚴(yán)格遵守的流程，排完序經(jīng)常會(huì)有些小錯(cuò)誤硼端。我在中學(xué)時(shí)還沒(méi)有計(jì)算機(jī)并淋，我們常常幫助老師統(tǒng)計(jì)同學(xué)們的期末考試成績(jī)，發(fā)現(xiàn)把一個(gè)班上五十個(gè)人的成績(jī)排序絲毫沒(méi)有錯(cuò)誤珍昨，并不容易县耽。后來(lái)我們發(fā)現(xiàn)比較可靠的辦法其實(shí)是下面兩種笨辦法：
方法一：第一次挑出成績(jī)最高的同學(xué)，第二次挑出成績(jī)次高的镣典，如此重復(fù)兔毙，肯定能完成成績(jī)的排序，一定不會(huì)錯(cuò)兄春。
方法二：先將成績(jī)單上第一個(gè)同學(xué)的名字和成績(jī)寫(xiě)到旁邊一張白紙的中央瞒御，如果第二個(gè)同學(xué)成績(jī)比他高，就寫(xiě)到第一個(gè)同學(xué)的上方神郊，如果比他低肴裙，就寫(xiě)到下方。等看到第三個(gè)同學(xué)的成績(jī)后涌乳，根據(jù)他的成績(jī)與前兩個(gè)同學(xué)成績(jī)的比較蜻懦，插入到相應(yīng)的位置。比如他的成績(jī)正好在兩個(gè)同學(xué)之間夕晓，就在旁邊那張排序的紙上宛乃，把他的名字插入到前兩個(gè)人之間。當(dāng)然蒸辆，那張排序的紙要留夠空白征炼，以方便插入后來(lái)同學(xué)的名字。
用這兩種方法排50個(gè)人的成績(jī)躬贡，工作量并不算小谆奥，比大家想象的大很多。是否有更好的排序方法拂玻，我和我高中的同學(xué)都沒(méi)有想出來(lái)酸些，其實(shí)也懶得想，因?yàn)槲覀兯诘氖澜缰車(chē)湍敲葱┤碎苎粒@兩種笨辦法夠用了魄懂。
其實(shí)，早期的計(jì)算機(jī)科學(xué)家比我們也強(qiáng)不到哪里去闯第，他們提出的排序算法就是上面兩種市栗。第一種算法被稱為冒泡排序，因?yàn)槊恳淮芜x出一個(gè)最好的，如同從水里冒出的氣泡填帽。第二種被稱為插入排序蛛淋，因?yàn)槊恳淮我业胶线m的位置插入。
接下來(lái)我們就用高德納的思想盲赊，分析一下上述算法的復(fù)雜度铣鹏。第一種算法很容易估算，50個(gè)人中找出最大的要比較49次哀蘑，第二大的要比較48次诚卸，以此類(lèi)推，大約是1200多次绘迁，是50的平方的一半左右合溺。第二種算法的復(fù)雜度，也是和50的平方有關(guān)缀台，這里就不再分析了棠赛。如果我們把50擴(kuò)展到任意一個(gè)整數(shù)N，事實(shí)上使用上述排序的復(fù)雜度都是N平方左右膛腐。我們昨天講到睛约，在衡量計(jì)算機(jī)算法復(fù)雜度時(shí)，科學(xué)家們不關(guān)心幾倍的差別哲身，因此辩涝，在用數(shù)學(xué)公式表達(dá)復(fù)雜度的時(shí)候，高德納干脆刪除了前面的常數(shù)因子勘天，只保留后面的變量怔揩，他用了微積分中的一個(gè)概念——大寫(xiě)的O的概念，所有同等復(fù)雜度的算法脯丝，都被認(rèn)為它們?cè)?大O的概念"下是相等的商膊。比如，上述冒泡排序算法的復(fù)雜度是O（N平方）宠进，插入排序也是O（N平方）晕拆，屬于同一個(gè)量級(jí)。此外砰苍，早期的計(jì)算機(jī)科學(xué)家還想出了其他的排序算法潦匈，復(fù)雜度都和它們差不多，在一個(gè)量級(jí)赚导。
接下來(lái)怎么提高計(jì)算機(jī)算法的效率呢？節(jié)省20%的計(jì)算量是沒(méi)有意義的事情赤惊，就算省個(gè)三五倍也沒(méi)有意義吼旧，要省就干脆多省一點(diǎn)，省它個(gè)成千上萬(wàn)倍甚至更多未舟。于是圈暗，全世界所有的算法專(zhuān)家經(jīng)過(guò)了十多年掂为，終于發(fā)現(xiàn)從經(jīng)驗(yàn)出發(fā)的排序速度慢的原因，就是做了無(wú)數(shù)的無(wú)用功员串。要提高效率勇哗，就需要讓計(jì)算機(jī)少做事情。
以冒泡排序?yàn)槔缙耄月担且驗(yàn)槊恳淮芜x出一個(gè)最大的數(shù)，都要和其它所有的數(shù)字相比渺鹦，其實(shí)并不需要這么麻煩扰法，要想提高效率，就要減少數(shù)據(jù)之間的相互比較毅厚。最早對(duì)冒泡排序的改進(jìn)是一種叫做歸并排序的算法塞颁，它就利用了少做事情的思想，歸并排序的思想大致如下：
首先吸耿，科學(xué)家們發(fā)現(xiàn)祠锣，如果我們把全班同學(xué)分成兩組，分別排序咽安，那么從每一組中挑選出一個(gè)最大的伴网，就能省去一半的相互比較時(shí)間。于是他們就先將整個(gè)班級(jí)一分為二板乙，先分別進(jìn)行排序是偷，再把兩個(gè)排好序的組，合并成為一個(gè)有序的序列募逞。相比排序蛋铆，對(duì)有序的序列合并是很快的。歸并排序這個(gè)詞就是這么來(lái)的放接。這樣做大約可以節(jié)省一半時(shí)間刺啦。當(dāng)然，我們?cè)谇懊嬉仓v過(guò)纠脾，節(jié)省一半時(shí)間意義不大玛瘸，但是別著急，因?yàn)閷?duì)一個(gè)班級(jí)分出來(lái)的兩個(gè)小組苟蹈，排序時(shí)也可以采用上述技巧糊渊。
第二步，就是對(duì)兩個(gè)組的排序慧脱。顯然我們不應(yīng)該再用冒泡排序渺绒。聰明一點(diǎn)的人馬上會(huì)想到，既然能分成兩組，就能把每個(gè)小組再分為兩組宗兼，即分成四組躏鱼，重復(fù)上面的算法，分別排序再合并殷绍。這樣就能省3/4的時(shí)間染苛。
再接下來(lái)，四組可以分為八組主到，能省7/8的時(shí)間茶行，八組可以分為十六組，時(shí)間就不斷省得越來(lái)越多镰烧。分到最后每個(gè)小組只剩下兩個(gè)人的時(shí)候拢军，其實(shí)就不用排序了，只要比較一次大小即可怔鳖。
這種方法其實(shí)可以理解為兩個(gè)過(guò)程茉唉，先是自頂向下細(xì)分，再自底向上合并结执。那么這種算法的復(fù)雜度等于多少呢度陆？它相當(dāng)于N乘以log（N），log（N）就是N的對(duì)數(shù)函數(shù)献幔，大家不必在意N乘以log（N）是什么東西懂傀，只要記住它和N平方不一樣，而且這個(gè)復(fù)雜度比前面的N平方小很多就行了蜡感。
為了便于你理解它小了多少蹬蚁，我們看看當(dāng)N分別是100，1萬(wàn)郑兴，1百萬(wàn)犀斋，1億時(shí)，兩種算法的復(fù)雜度的情形：
第一種：即N平方情连，當(dāng)N是100叽粹，1萬(wàn)，1百萬(wàn)却舀，1億時(shí)虫几，它對(duì)應(yīng)1萬(wàn)，1億挽拔，1萬(wàn)億辆脸，1億億。
第二種：即N乘以log（N）螃诅，它對(duì) 應(yīng)700每强，13萬(wàn)始腾，2000萬(wàn)州刽，23億空执。
你可以看出N比較大了以后，N乘以log（N）比N平方要小很多穗椅，即23億和1億億的差別辨绊，相差大約400萬(wàn)倍。400萬(wàn)是什么概念呢匹表？大約是一支毛筆的長(zhǎng)度和北京到上海距離的差別门坷，或者是你和我兩個(gè)人的重量和瓦良格號(hào)航空母艦重量的差別。
這樣一對(duì)比袍镀，你就能感覺(jué)到為什么計(jì)算機(jī)的算法是如此重要默蚌。算法沒(méi)有學(xué)好的人，寫(xiě)出來(lái)的程序經(jīng)常是不合格的苇羡，因?yàn)楹苋菀拙屠速M(fèi)掉成千上萬(wàn)倍的計(jì)算機(jī)資源绸吸。大家不要覺(jué)得一個(gè)億是什么了不得的大數(shù)字，且不說(shuō)騰訊或者阿里巴巴這樣公司的用戶數(shù)早就超過(guò)了一個(gè)億设江，即使你編寫(xiě)一款游戲锦茁，只要有人使用，幾天下來(lái)的日志都有上億行叉存，對(duì)一億個(gè)數(shù)排序码俩，在計(jì)算機(jī)應(yīng)用中是很常見(jiàn)的事情。
歸并排序算法相比之前的算法為什么效率提高這么多歼捏？因?yàn)樗僮隽撕芏嗖⒉恍枰龅谋容^稿存。很多人問(wèn)我，你為什么效率這么高瞳秽？并不是我效率高瓣履，而是做事情比大家少。效率＝產(chǎn)出／所做的事情寂诱。人的產(chǎn)出是很難提高的拂苹，但是所做的事情是可以減少的。
我一直強(qiáng)調(diào)工程師水平差一級(jí)痰洒，貢獻(xiàn)可能就差出10倍瓢棒，有人不服氣，說(shuō)會(huì)差這么大么丘喻？從上面的一個(gè)例子大家可以看出脯宿，可能差得還不止十倍。很多人問(wèn)泉粉，我想改行搞計(jì)算機(jī)连霉，自己找兩本書(shū)看看是否就可以了榴芳？我的答案是不可以，在今天這樣一個(gè)人多粥少跺撼，人的技能普遍高出行業(yè)基本要求的時(shí)代窟感，進(jìn)入任何一個(gè)行業(yè)，都要有點(diǎn)專(zhuān)業(yè)精神歉井，把自己當(dāng)作科班出身來(lái)要求柿祈。在農(nóng)耕文明時(shí)代，沒(méi)有力氣的人最不濟(jì)也能產(chǎn)生壯勞力1/3的生產(chǎn)力哩至。在工業(yè)時(shí)代躏嚎，靠手工一件件生產(chǎn)商品，可能效率能有機(jī)器的1%菩貌。但是到了智能時(shí)代卢佣，本事差一點(diǎn)，效果可能差幾百萬(wàn)倍箭阶，幾億倍虚茶，專(zhuān)業(yè)和不專(zhuān)業(yè)就差得更遠(yuǎn)了。
為什么到了智能時(shí)代學(xué)習(xí)變得非常重要了呢尾膊？因?yàn)橐恍┗镜姆椒ê偷览砣绻粚W(xué)習(xí)媳危，靠自己腦子苦思冥想可能需要十年甚至更多的時(shí)間，而學(xué)習(xí)加練習(xí)冈敛，可能只要一個(gè)月的時(shí)間就夠了待笑。早期的計(jì)算機(jī)科學(xué)家因?yàn)槭芟抻谧约旱纳瞽h(huán)境，也想不出好的排序方法抓谴，今天比較常用的排序算法"快速排序（Quicksort）"暮蹂，是在計(jì)算機(jī)誕生后13年才出現(xiàn)的。這個(gè)算法癌压，我下次花十分鐘時(shí)間仰泻，就可以給大家講清楚，大家可以自己判斷滩届，是應(yīng)該學(xué)習(xí)集侯，還是自己琢磨呢？
明天我們會(huì)談?wù)効焖倥判蛑南约八澈蟮姆椒ㄕ摗?/p>
今天的思考題是這樣的：歸并排序相比那些效率低的簡(jiǎn)單排序棠枉，其實(shí)還說(shuō)明了一個(gè)道理，就是將一個(gè)復(fù)雜問(wèn)題分解成很多簡(jiǎn)單的問(wèn)題泡挺，一個(gè)個(gè)解決辈讶，最后比直接解決復(fù)雜問(wèn)題要省很多時(shí)間。能否就這件事發(fā)表你的看法娄猫？
已讀
