1057
??算法與數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)學(xué)生的必修課，基礎(chǔ)中的基礎(chǔ)，所以快速上手，找到學(xué)習(xí)方向和感覺(jué)十分重要。我在學(xué)習(xí)過(guò)程中遇到一本好書，《我的第一本算法書》，把算法講得很淺顯易懂，所以基于這本書的內(nèi)容，提煉出其中的精華，再加上個(gè)人的理解，旨在把最干的干貨分享給大家。推薦大家去閱讀原書！
排序
由于排序是一個(gè)比較基礎(chǔ)的問(wèn)題，所以排序算法的種類也比較多。
冒泡排序
從序列右邊開(kāi)始比較相鄰兩個(gè)數(shù)字的大小，再根據(jù)結(jié)果交換兩個(gè)數(shù)字的位置。數(shù)字會(huì)像泡泡一樣，慢慢從右往左“浮”到序列的頂端。
選擇排序
從待排序的數(shù)據(jù)中尋找最小值，將其與序列最左邊的數(shù)字進(jìn)行交換。
插入排序
從序列左端開(kāi)始依次對(duì)數(shù)據(jù)進(jìn)行排序的算法。在排序過(guò)程中，左側(cè)的數(shù)據(jù)陸續(xù)歸位，而右側(cè)留下的就是還未被排序的數(shù)據(jù)。插入排序的思路就是從右側(cè)的未排序區(qū)域內(nèi)取出一個(gè)數(shù)據(jù)，然后將它插入到已排序區(qū)域內(nèi)合適的位置上。 跟冒泡沒(méi)什么區(qū)別，每次從右邊取值后就弄一次冒泡。
堆排序
堆排序的特點(diǎn)是利用了數(shù)據(jù)結(jié)構(gòu)中的堆。首先，在堆中存儲(chǔ)所有的數(shù)據(jù)，并按降序來(lái)構(gòu)建堆。所有數(shù)據(jù)都存進(jìn)堆里了。為了排序，需要再?gòu)亩阎邪褦?shù)據(jù)一個(gè)個(gè)取出來(lái)。每次取數(shù)只取堆頂（當(dāng)前最大值），將數(shù)放至數(shù)組的末尾，然后重新構(gòu)造堆，再取堆頂，放數(shù)至數(shù)組末尾前面，不斷重復(fù)直到數(shù)組填滿。
歸并排序
歸并排序算法會(huì)把序列分成長(zhǎng)度相同的兩個(gè)子序列，當(dāng)無(wú)法繼續(xù)往下分時(shí)（也就是每個(gè)子序列中只有一個(gè)數(shù)據(jù)時(shí)），就對(duì)子序列進(jìn)行歸并。歸并指的是把兩個(gè)排好序的子序列合并成一個(gè)有序序列。該操作會(huì)一直重復(fù)執(zhí)行，直到所有子序列都?xì)w并為一個(gè)整體為止。
有點(diǎn)小復(fù)雜，不過(guò)看圖秒懂，重點(diǎn)就是每次比較序列的首位數(shù)字。
快速排序
快速排序算法首先會(huì)在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值（pivot），然后將除了基準(zhǔn)值以外的數(shù)分為“比基準(zhǔn)值小的數(shù)”和“比基準(zhǔn)值大的數(shù)”這兩個(gè)類別，再將其排列成以下形式。
接著，對(duì)兩個(gè)“[ ]”中的數(shù)據(jù)進(jìn)行排序之后，整體的排序便完成了。對(duì)“[ ]”里面的數(shù)據(jù)進(jìn)行排序時(shí)同樣也會(huì)使用快速排序。
數(shù)組的查找
線性查找
線性查找的操作很簡(jiǎn)單，只要在數(shù)組中從頭開(kāi)始依次往下查找即可。
二分查找
二分查找也是一種在數(shù)組中查找數(shù)據(jù)的算法。和線性查找不同，它只能查找已經(jīng)排好序的數(shù)據(jù)。二分查找通過(guò)比較數(shù)組中間的數(shù)據(jù)與目標(biāo)數(shù)據(jù)的大小，可以得知目標(biāo)數(shù)據(jù)是在數(shù)組的左邊還是右邊。因此，比較一次就可以把查找范圍縮小一半。重復(fù)執(zhí)行該操作就可以找到目標(biāo)數(shù)據(jù)，或得出目標(biāo)數(shù)據(jù)不存在的結(jié)論。 就是人們腦里猜數(shù)經(jīng)常用的方法。
上一篇 ! 下一篇 ！加油！
