常见数据结构与算法整理总结（下）
原文鏈接：https://www.jianshu.com/p/42f81846c0fb
這篇文章是常見數(shù)據(jù)結(jié)構(gòu)與算法整理總結(jié)的下篇，上一篇主要是對(duì)常見的數(shù)據(jù)結(jié)構(gòu)進(jìn)行集中總結(jié)，這篇主要是總結(jié)一些常見的算法相關(guān)內(nèi)容，文章中如有錯(cuò)誤，歡迎指出。
一、概述 二、查找算法 三、排序算法 四、其它算法 五、常見算法題 六、總結(jié)一、概述
以前看到這樣一句話，語言只是工具，算法才是程序設(shè)計(jì)的靈魂。的確，算法在計(jì)算機(jī)科學(xué)中的地位真的很重要，在很多大公司的筆試面試中，算法掌握程度的考察都占據(jù)了很大一部分。不管是為了面試還是自身編程能力的提升，花時(shí)間去研究常見的算法還是很有必要的。下面是自己對(duì)于算法這部分的學(xué)習(xí)總結(jié)。
算法簡(jiǎn)介
算法是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。對(duì)于同一個(gè)問題的解決，可能會(huì)存在著不同的算法，為了衡量一個(gè)算法的優(yōu)劣，提出了空間復(fù)雜度與時(shí)間復(fù)雜度這兩個(gè)概念。
時(shí)間復(fù)雜度
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記為 ** T(n) = O(f(n)) **，它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。這里需要重點(diǎn)理解這個(gè)增長(zhǎng)率。
舉個(gè)例子，看下面3個(gè)代碼：1、{++x;}
2、for(i = 1; i <= n; i++) { ++x; }
3、for(j = 1; j <= n; j++)
for(j = 1; j <= n; j++)
{ ++x; }
上述含有 ++x 操作的語句的頻度分別為1 、n 、n^2，
假設(shè)問題的規(guī)模擴(kuò)大了n倍，3個(gè)代碼的增長(zhǎng)率分別是1 、n 、n^2
它們的時(shí)間復(fù)雜度分別為O(1)、O(n )、O(n^2)
空間復(fù)雜度
空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))。一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量。
二、查找算法
查找和排序是最基礎(chǔ)也是最重要的兩類算法，熟練地掌握這兩類算法，并能對(duì)這些算法的性能進(jìn)行分析很重要，這兩類算法中主要包括二分查找、快速排序、歸并排序等等。
順序查找
順序查找又稱線性查找。它的過程為：從查找表的最后一個(gè)元素開始逐個(gè)與給定關(guān)鍵字比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，否則，若直至第一個(gè)記錄，其關(guān)鍵字和給定值比較都不等，則表明表中沒有所查記錄查找不成功，它的缺點(diǎn)是效率低下。
二分查找
- 簡(jiǎn)介
二分查找又稱折半查找，對(duì)于有序表來說，它的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好。
二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x，算法中止；如果x<a[n/2]，則只要在數(shù)組a的左半部分繼續(xù)搜索x，如果x>a[n/2]，則只要在數(shù)組a的右半部搜索x。
二分查找的時(shí)間復(fù)雜度為O(logn)
- 實(shí)現(xiàn)
static int funBinSearch(int[] array, int data) {
<span class="hljs-keyword">int</span> low = <span class="hljs-number">0</span>; <span class="hljs-keyword">int</span> high = <span class="hljs-built_in">array</span>.length - <span class="hljs-number">1</span>;<span class="hljs-keyword">while</span> (low <= high) {<span class="hljs-keyword">int</span> mid = (low + high) / <span class="hljs-number">2</span>;<span class="hljs-keyword">if</span> (data == <span class="hljs-built_in">array</span>[mid]) {<span class="hljs-keyword">return</span> mid;} <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (data < <span class="hljs-built_in">array</span>[mid]) {high = mid - <span class="hljs-number">1</span>;} <span class="hljs-keyword">else</span> {low = mid + <span class="hljs-number">1</span>;} } <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>;}
三、排序算法
排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。下面主要對(duì)一些常見的排序算法做介紹，并分析它們的時(shí)空復(fù)雜度。
常見排序算法常見排序算法性能比較：
圖片來自網(wǎng)絡(luò)上面這張表中有穩(wěn)定性這一項(xiàng)，排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個(gè)元素的話，排序前和排序后他們的相對(duì)位置不發(fā)生變化。
下面從冒泡排序開始逐一介紹。
冒泡排序
- 簡(jiǎn)介
冒泡排序的基本思想是：設(shè)排序序列的記錄個(gè)數(shù)為n，進(jìn)行n-1次遍歷，每次遍歷從開始位置依次往后比較前后相鄰元素，這樣較大的元素往后移，n-1次遍歷結(jié)束后，序列有序。
例如，對(duì)序列(3,2,1,5)進(jìn)行排序的過程是：共進(jìn)行3次遍歷，第1次遍歷時(shí)先比較3和2，交換，繼續(xù)比較3和1,交換，再比較3和5，不交換，這樣第1次遍歷結(jié)束，最大值5在最后的位置，得到序列(2,1,3,5)。第2次遍歷時(shí)先比較2和1，交換，繼續(xù)比較2和3，不交換，第2次遍歷結(jié)束時(shí)次大值3在倒數(shù)第2的位置，得到序列(1,2,3,5)，第3次遍歷時(shí)，先比較1和2，不交換，得到最終有序序列(1,2,3,5)。
需要注意的是，如果在某次遍歷中沒有發(fā)生交換，那么就不必進(jìn)行下次遍歷，因?yàn)樾蛄幸呀?jīng)有序。
- 實(shí)現(xiàn)
}
- 分析
最佳情況下冒泡排序只需一次遍歷就能確定數(shù)組已經(jīng)排好序，不需要進(jìn)行下一次遍歷，所以最佳情況下，時(shí)間復(fù)雜度為** O(n) **。
最壞情況下冒泡排序需要n-1次遍歷，第一次遍歷需要比較n-1次，第二次遍歷需要n-2次，...，最后一次需要比較1次，最差情況下時(shí)間復(fù)雜度為** O(n^2) **。
簡(jiǎn)單選擇排序
- 簡(jiǎn)介
簡(jiǎn)單選擇排序的思想是：設(shè)排序序列的記錄個(gè)數(shù)為n，進(jìn)行n-1次選擇，每次在n-i+1(i = 1,2,...,n-1)個(gè)記錄中選擇關(guān)鍵字最小的記錄作為有效序列中的第i個(gè)記錄。
例如，排序序列(3,2,1,5)的過程是，進(jìn)行3次選擇，第1次選擇在4個(gè)記錄中選擇最小的值為1，放在第1個(gè)位置，得到序列(1,3,2,5)，第2次選擇從位置1開始的3個(gè)元素中選擇最小的值2放在第2個(gè)位置，得到有序序列(1,2,3,5)，第3次選擇因?yàn)樽钚〉闹?已經(jīng)在第3個(gè)位置不需要操作，最后得到有序序列（1,2,3,5）。
- 實(shí)現(xiàn)
}
- 分析
簡(jiǎn)單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況** 無關(guān)。當(dāng)i=1時(shí)，需進(jìn)行n-1次比較；當(dāng)i=2時(shí)，需進(jìn)行n-2次比較；依次類推，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進(jìn)行比較操作的時(shí)間復(fù)雜度為 O(n^2) ，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為 O(n) 。總的時(shí)間復(fù)雜度為 O(n^2) **。
最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄。最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。
簡(jiǎn)單選擇排序是不穩(wěn)定排序。
直接插入排序
- 簡(jiǎn)介
直接插入的思想是：是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。
例如，排序序列(3,2,1,5)的過程是，初始時(shí)有序序列為(3)，然后從位置1開始，先訪問到2，將2插入到3前面，得到有序序列(2,3)，之后訪問1,找到合適的插入位置后得到有序序列(1,2,3)，最后訪問5，得到最終有序序列(1,2,3,5).
- 實(shí)現(xiàn)
}
- 分析
最好情況下，當(dāng)待排序序列中記錄已經(jīng)有序時(shí)，則需要n-1次比較，不需要移動(dòng)，時(shí)間復(fù)雜度為** O(n) 。最差情況下，當(dāng)待排序序列中所有記錄正好逆序時(shí)，則比較次數(shù)和移動(dòng)次數(shù)都達(dá)到最大值，時(shí)間復(fù)雜度為 O(n^2) 。平均情況下，時(shí)間復(fù)雜度為 O(n^2) **。
希爾排序
希爾排序又稱“縮小增量排序”，它是基于直接插入排序的以下兩點(diǎn)性質(zhì)而提出的一種改進(jìn)：(1) 直接插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。(2) 直接插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。點(diǎn)擊查看更多關(guān)于希爾排序的內(nèi)容
歸并排序
- 簡(jiǎn)介
歸并排序是分治法的一個(gè)典型應(yīng)用，它的主要思想是：將待排序序列分為兩部分，對(duì)每部分遞歸地應(yīng)用歸并排序，在兩部分都排好序后進(jìn)行合并。
例如，排序序列(3,2,8,6,7,9,1,5)的過程是，先將序列分為兩部分，(3,2,8,6)和(7,9,1,5)，然后對(duì)兩部分分別應(yīng)用歸并排序，第1部分(3,2,8,6)，第2部分(7,9,1,5)，對(duì)兩個(gè)部分分別進(jìn)行歸并排序，第1部分繼續(xù)分為(3,2)和(8,6)，(3,2)繼續(xù)分為(3)和(2)，(8,6)繼續(xù)分為(8)和(6)，之后進(jìn)行合并得到(2,3)，(6,8)，再合并得到(2,3,6,8)，第2部分進(jìn)行歸并排序得到(1,5,7,9)，最后合并兩部分得到(1,2,3,5,6,7,8,9)。
- 實(shí)現(xiàn)
- 分析
歸并排序的時(shí)間復(fù)雜度為O(nlogn)，它是一種穩(wěn)定的排序，java.util.Arrays類中的sort方法就是使用歸并排序的變體來實(shí)現(xiàn)的。
快速排序
- 簡(jiǎn)介
快速排序的主要思想是：在待排序的序列中選擇一個(gè)稱為主元的元素，將數(shù)組分為兩部分，使得第一部分中的所有元素都小于或等于主元，而第二部分中的所有元素都大于主元，然后對(duì)兩部分遞歸地應(yīng)用快速排序算法。
- 實(shí)現(xiàn)
// 快速排序前的劃分
static int quickSortPartition(int[] list, int first, int last) {
}
- 分析
在快速排序算法中，比較關(guān)鍵的一個(gè)部分是主元的選擇。在最差情況下，劃分由n個(gè)元素構(gòu)成的數(shù)組需要進(jìn)行n次比較和n次移動(dòng)，因此劃分需要的時(shí)間是O(n)。在最差情況下，每次主元會(huì)將數(shù)組劃分為一個(gè)大的子數(shù)組和一個(gè)空數(shù)組，這個(gè)大的子數(shù)組的規(guī)模是在上次劃分的子數(shù)組的規(guī)模上減1，這樣在最差情況下算法需要(n-1)+(n-2)+...+1= ** O(n^2) **時(shí)間。
最佳情況下，每次主元將數(shù)組劃分為規(guī)模大致相等的兩部分，時(shí)間復(fù)雜度為** O(nlogn) **。
堆排序
- 簡(jiǎn)介
在介紹堆排序之前首先需要了解堆的定義，n個(gè)關(guān)鍵字序列K1，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)）：(1) ki <= k(2i）且 ki <= k(2i+1) (1 ≤ i≤ n/2），當(dāng)然，這是小根堆，大根堆則換成>=號(hào)。
如果將上面滿足堆性質(zhì)的序列看成是一個(gè)完全二叉樹，則堆的含義表明，完全二叉樹中所有的非終端節(jié)點(diǎn)的值均不大于（或不小于）其左右孩子節(jié)點(diǎn)的值。
堆排序的主要思想是：給定一個(gè)待排序序列，首先經(jīng)過一次調(diào)整，將序列構(gòu)建成一個(gè)大頂堆，此時(shí)第一個(gè)元素是最大的元素，將其和序列的最后一個(gè)元素交換，然后對(duì)前n-1個(gè)元素調(diào)整為大頂堆，再將其第一個(gè)元素和末尾元素交換，這樣最后即可得到有序序列。
- 實(shí)現(xiàn)
}
- 分析
由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序時(shí)間復(fù)雜度也為O(nlogn)，空間復(fù)雜度為O(1)。它是不穩(wěn)定的排序方法。與快排和歸并排序相比，堆排序在最差情況下的時(shí)間復(fù)雜度優(yōu)于快排，空間效率高于歸并排序。
四、其它算法
在上面的篇幅中，主要是對(duì)查找和常見的幾種排序算法作了介紹，這些內(nèi)容都是基礎(chǔ)的但是必須掌握的內(nèi)容，尤其是二分查找、快排、堆排、歸并排序這幾個(gè)更是面試高頻考察點(diǎn)。（這里不禁想起百度一面的時(shí)候讓我寫二分查找和堆排序，二分查找還行，然而堆排序當(dāng)時(shí)一臉懵逼...）下面主要是介紹一些常見的其它算法。
遞歸
- 簡(jiǎn)介
在平常解決一些編程或者做一些算法題的時(shí)候，經(jīng)常會(huì)用到遞歸。程序調(diào)用自身的編程技巧稱為遞歸。它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。上面介紹的快速排序和歸并排序都用到了遞歸的思想。
- 經(jīng)典例子
斐波那契數(shù)列，又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）。
//斐波那契數(shù)列 遞歸實(shí)現(xiàn) static long funFib(long index) { <span class="hljs-keyword">if</span> (index == <span class="hljs-number">0</span>) {<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (index == <span class="hljs-number">1</span>) {<span class="hljs-keyword">return</span> <span class="hljs-number">1</span>; } <span class="hljs-keyword">else</span> {<span class="hljs-keyword">return</span> funFib(index - <span class="hljs-number">1</span>) + funFib(index - <span class="hljs-number">2</span>); }}
上面代碼是斐波那契數(shù)列的遞歸實(shí)現(xiàn)，然而我們不難得到它的時(shí)間復(fù)雜度是O(2^n)，遞歸有時(shí)候可以很方便地解決一些問題，但是它也會(huì)帶來一些效率上的問題。下面的代碼是求斐波那契數(shù)列的另一種方式，效率比遞歸方法的效率高。
static long funFib2(long index) { <span class="hljs-keyword">long</span> f0 = <span class="hljs-number">0</span>; <span class="hljs-keyword">long</span> f1 = <span class="hljs-number">1</span>; <span class="hljs-keyword">long</span> f2 = <span class="hljs-number">1</span>;<span class="hljs-keyword">if</span> (index == <span class="hljs-number">0</span>) {<span class="hljs-keyword">return</span> f0; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (index == <span class="hljs-number">1</span>) {<span class="hljs-keyword">return</span> f1; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (index == <span class="hljs-number">2</span>) {<span class="hljs-keyword">return</span> f2; }<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">3</span>; i <= index; i++) {f0 = f1;f1 = f2;f2 = f0 + f1; }<span class="hljs-keyword">return</span> f2;}
分治算法
分治算法的思想是將待解決的問題分解為幾個(gè)規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后合并這些子問題的解來建立最終的解。分治算法中關(guān)鍵地一步其實(shí)就是遞歸地求解子問題。關(guān)于分治算法的一個(gè)典型例子就是上面介紹的歸并排序。查看更多關(guān)于分治算法的內(nèi)容
動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃與分治方法相似，都是通過組合子問題的解來求解待解決的問題。但是，分治算法將問題劃分為互不相交的子問題，遞歸地求解子問題，再將它們的解組合起來，而動(dòng)態(tài)規(guī)劃應(yīng)用于子問題重疊的情況，即不同的子問題具有公共的子子問題。動(dòng)態(tài)規(guī)劃方法通常用來求解最優(yōu)化問題。查看更多關(guān)于動(dòng)態(tài)規(guī)劃的內(nèi)容
動(dòng)態(tài)規(guī)劃典型的一個(gè)例子是最長(zhǎng)公共子序列問題。
常見的算法還有很多，比如貪心算法，回溯算法等等，這里都不再詳細(xì)介紹，想要熟練掌握，還是要靠刷題，刷題，刷題，然后總結(jié)。
五、常見算法題
下面是一些常見的算法題匯總。
不使用臨時(shí)變量交換兩個(gè)數(shù)
static void funSwapTwo(int a, int b) { a = a ^ b; b = b ^ a; a = a ^ b;System.out.println(a + <span class="hljs-string">" "</span> + b);}
判斷一個(gè)數(shù)是否為素?cái)?shù)
static boolean funIsPrime(int m) { <span class="hljs-keyword">boolean</span> flag = <span class="hljs-keyword">true</span>;<span class="hljs-keyword">if</span> (m == <span class="hljs-number">1</span>) {flag = <span class="hljs-keyword">false</span>; } <span class="hljs-keyword">else</span> {<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">2</span>; i <= Math.sqrt(m); i++) {<span class="hljs-keyword">if</span> (m % i == <span class="hljs-number">0</span>) {flag = <span class="hljs-keyword">false</span>;<span class="hljs-keyword">break</span>;}} }<span class="hljs-keyword">return</span> flag;}
其它算法題
1、15道使用頻率極高的基礎(chǔ)算法題
2、二叉樹相關(guān)算法題
3、鏈表相關(guān)算法題
4、字符串相關(guān)算法問題
六、總結(jié)
以上就是自己對(duì)常見的算法相關(guān)內(nèi)容的總結(jié)，算法虐我千百遍，我待算法如初戀，革命尚未成功，同志仍需刷題，加油。
總結(jié)
以上是生活随笔為你收集整理的常见数据结构与算法整理总结（下）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： requirements.txt一键安装
- 下一篇： 依存句法分析