算法與數(shù)據(jù)結(jié)構(gòu)無廢話筆記（二）

??算法與數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)學(xué)生的必修課，基礎(chǔ)中的基礎(chǔ)，所以快速上手，找到學(xué)習(xí)方向和感覺十分重要。我在學(xué)習(xí)過程中遇到一本好書，《我的第一本算法書》，把算法講得很淺顯易懂，所以基于這本書的內(nèi)容，提煉出其中的精華，再加上個人的理解，旨在把最干的干貨分享給大家。推薦大家去閱讀原書！

排序

由于排序是一個比較基礎(chǔ)的問題，所以排序算法的種類也比較多。

冒泡排序

從序列右邊開始比較相鄰兩個數(shù)字的大小，再根據(jù)結(jié)果交換兩個數(shù)字的位置。數(shù)字會像泡泡一樣，慢慢從右往左“浮”到序列的頂端。

選擇排序

從待排序的數(shù)據(jù)中尋找最小值，將其與序列最左邊的數(shù)字進行交換。

插入排序

從序列左端開始依次對數(shù)據(jù)進行排序的算法。在排序過程中，左側(cè)的數(shù)據(jù)陸續(xù)歸位，而右側(cè)留下的就是還未被排序的數(shù)據(jù)。插入排序的思路就是從右側(cè)的未排序區(qū)域內(nèi)取出一個數(shù)據(jù)，然后將它插入到已排序區(qū)域內(nèi)合適的位置上。 跟冒泡沒什么區(qū)別，每次從右邊取值后就弄一次冒泡。

堆排序

堆排序的特點是利用了數(shù)據(jù)結(jié)構(gòu)中的堆。首先，在堆中存儲所有的數(shù)據(jù)，并按降序來構(gòu)建堆。所有數(shù)據(jù)都存進堆里了。為了排序，需要再從堆中把數(shù)據(jù)一個個取出來。每次取數(shù)只取堆頂（當(dāng)前最大值），將數(shù)放至數(shù)組的末尾，然后重新構(gòu)造堆，再取堆頂，放數(shù)至數(shù)組末尾前面，不斷重復(fù)直到數(shù)組填滿。

歸并排序

歸并排序算法會把序列分成長度相同的兩個子序列，當(dāng)無法繼續(xù)往下分時（也就是每個子序列中只有一個數(shù)據(jù)時），就對子序列進行歸并。歸并指的是把兩個排好序的子序列合并成一個有序序列。該操作會一直重復(fù)執(zhí)行，直到所有子序列都歸并為一個整體為止。

有點小復(fù)雜，不過看圖秒懂，重點就是每次比較序列的首位數(shù)字。

快速排序

快速排序算法首先會在序列中隨機選擇一個基準(zhǔn)值（pivot），然后將除了基準(zhǔn)值以外的數(shù)分為“比基準(zhǔn)值小的數(shù)”和“比基準(zhǔn)值大的數(shù)”這兩個類別，再將其排列成以下形式。

接著，對兩個“[ ]”中的數(shù)據(jù)進行排序之后，整體的排序便完成了。對“[ ]”里面的數(shù)據(jù)進行排序時同樣也會使用快速排序。

數(shù)組的查找

線性查找

線性查找的操作很簡單，只要在數(shù)組中從頭開始依次往下查找即可。

二分查找

二分查找也是一種在數(shù)組中查找數(shù)據(jù)的算法。和線性查找不同，它只能查找已經(jīng)排好序的數(shù)據(jù)。二分查找通過比較數(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)常用的方法。

上一篇 ! 下一篇 ！加油！