以前不管自己還是朋友在面試java工程師崗位的時候，都會被問到這樣的問題，下面就讓匯智動力學院來為大家介紹下java中的數(shù)據(jù)結構和算法，很多朋友被問到的時候發(fā)現(xiàn)無從下口，甚至特別是一些初級java工程師更是一臉懵逼！那么本篇文章就針對數(shù)據(jù)結構和算法給大家簡單介紹下；

首先要知道我們?yōu)槭裁匆獙W習數(shù)據(jù)結構和算法？這里舉個簡單的例子。

　　編程好比是一輛汽車，而數(shù)據(jù)結構和算法是汽車內部的變速箱。一個開車的人不懂變速箱的原理也是能開車的，同理一個不懂數(shù)據(jù)結構和算法的人也能編程。但是如果一個開車的人懂變速箱的原理，比如降低速度來獲得更大的牽引力，或者通過降低牽引力來獲得更快的行駛速度。那么爬坡時使用1檔，便可以獲得更大的牽引力；下坡時便使用低檔限制車的行駛速度?；氐骄幊潭裕热鐚⒁粋€班級的學生名字要臨時存儲在內存中，你會選擇什么數(shù)據(jù)結構來存儲，數(shù)組還是ArrayList，或者HashSet，或者別的數(shù)據(jù)結構。如果不懂數(shù)據(jù)結構的，可能隨便選擇一個容器來存儲，也能完成所有的功能，但是后期如果隨著學生數(shù)據(jù)量的增多，隨便選擇的數(shù)據(jù)結構肯定會存在性能問題，而一個懂數(shù)據(jù)結構和算法的人，在實際編程中會選擇適當?shù)臄?shù)據(jù)結構來解決相應的問題，會極大的提高程序的性能。

1、數(shù)據(jù)結構

　　數(shù)據(jù)結構是計算機存儲、組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。

　　通常情況下，精心選擇的數(shù)據(jù)結構可以帶來更高的運行或者存儲效率。數(shù)據(jù)結構往往同高效的檢索算法和索引技術有關。

　　一、數(shù)據(jù)結構的基本功能

　　①、如何插入一條新的數(shù)據(jù)項

　　②、如何尋找某一特定的數(shù)據(jù)項

　?、邸⑷绾蝿h除某一特定的數(shù)據(jù)項

　?、堋⑷绾蔚脑L問各個數(shù)據(jù)項，以便進行顯示或其他操作

　　二、常用的數(shù)據(jù)結構

 　　

　　這幾種結構優(yōu)缺點如下：先有個大概印象，后面會詳細講解?。。?/span>

　　

2、算法

　　算法簡單來說就是解決問題的方案步驟。

　　在Java中，算法通常都是由類的方法來實現(xiàn)的。前面的數(shù)據(jù)結構，比如鏈表為啥插入、刪除快，而查找慢，平衡的二叉樹插入、刪除、查找都快，這都是實現(xiàn)這些數(shù)據(jù)結構的算法所造成的。后面我們講的各種排序實現(xiàn)也是算法范疇的重要領域。

　一、算法的五個特征

　?、?、有窮性（Finiteness）

算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止；

②、確切性(Definiteness)

算法的每一步驟必須有確切的定義；

③、輸入項(Input)

一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；

④、輸出項(Output)

一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法是毫無意義的；

⑤、可行性(Effectiveness)

算法中執(zhí)行的任何計算步驟都是可以被分解為基本的可執(zhí)行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

二、算法的設計原則

　　①、正確性：首先，算法應當滿足以特定的“規(guī)則說明”方式給出的需求。其次，對算法是否“正確”的理解可以有以下四個層次：

　　　　　一、程序語法錯誤。

　　　　　二、程序對于幾組輸入數(shù)據(jù)能夠得出滿足需要的結果。

　　　　　三、程序對于精心選擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結果。

　　　　　四、程序對于一切合法的輸入數(shù)據(jù)都能得到滿足要求的結果。

　　　　　PS：通常以第 三 層意義的正確性作為衡量一個算法是否合格的標準。

　　②、可讀性：算法為了人的閱讀與交流，其次才是計算機執(zhí)行。因此算法應該易于人的理解；另一方面，晦澀難懂的程序易于隱藏較多的錯誤而難以調試。

　　③、健壯性：當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)淖龀龇磻蜻M行相應處理，而不是產生莫名其妙的輸出結果。并且，處理出錯的方法不應是中斷程序執(zhí)行，而是應當返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。

　　④、高效率與低存儲量需求：通常算法效率值得是算法執(zhí)行時間；存儲量是指算法執(zhí)行過程中所需要的最大存儲空間，兩者都與問題的規(guī)模有關。

　　前面三點 正確性，可讀性和健壯性相信都好理解。對于第四點算法的執(zhí)行效率和存儲量，我們知道比較算法的時候，可能會說“A算法比B算法快兩倍”之類的話，但實際上這種說法沒有任何意義。因為當數(shù)據(jù)項個數(shù)發(fā)生變化時，A算法和B算法的效率比例也會發(fā)生變化，比如數(shù)據(jù)項增加了50%，可能A算法比B算法快三倍，但是如果數(shù)據(jù)項減少了50%，可能A算法和B算法速度一樣。所以描述算法的速度必須要和數(shù)據(jù)項的個數(shù)聯(lián)系起來。也就是“大O”表示法，它是一種算法復雜度的相對表示方式，這里我簡單介紹一下，后面會根據(jù)具體的算法來描述。

　　相對(relative)：你只能比較相同的事物。你不能把一個做算數(shù)乘法的算法和排序整數(shù)列表的算法進行比較。但是，比較2個算法所做的算術操作（一個做乘法，一個做加法）將會告訴你一些有意義的東西；

　　表示(representation)：大O(用它最簡單的形式)把算法間的比較簡化為了一個單一變量。這個變量的選擇基于觀察或假設。例如，排序算法之間的對比通常是基于比較操作(比較2個結點來決定這2個結點的相對順序)。這里面就假設了比較操作的計算開銷很大。但是，如果比較操作的計算開銷不大，而交換操作的計算開銷很大，又會怎么樣呢？這就改變了先前的比較方式；

　　復雜度(complexity)：如果排序10,000個元素花費了我1秒，那么排序1百萬個元素會花多少時間？在這個例子里，復雜度就是相對其他東西的度量結果。

　　然后我們再說說算法的存儲量，包括：

　　       程序本身所占空間；

　　       輸入數(shù)據(jù)所占空間；

　　       輔助變量所占空間；

　　一個算法的效率越高越好，而存儲量是越低越好。

三、算法的分類

算法可以宏泛的分為三類：

一，有限的，確定性算法 這類算法在有限的一段時間內終止。他們可能要花很長時間來執(zhí)行指定的任務，但仍將在一定的時間內終止。這類算法得出的結果常取決于輸入值。

二，有限的，非確定算法 這類算法在有限的時間內終止。然而，對于一個（或一些）給定的數(shù)值，算法的結果并不是唯一的或確定的。

三，無限的算法 是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數(shù)據(jù)滿足而不終止運行的算法。通常，無限算法的產生是由于未能確定的定義終止條件。

 

 

Java中常見的算法有：

 

①、排序

排序就是對一組數(shù)據(jù)按照一定的順序（從大到小或者從小到大）進行排序；

常見排序如下：

 

簡單排序：冒泡排序、選擇排序、插入排序；

高級排序：快速排序、希爾排序、歸并排序、基數(shù)排序、雞尾酒排序等等；

②、遞歸

遞歸是一種直接或者間接調用自身的一種算法，遞歸的目的是簡化程序設計使程序更加易讀；

③、查找

在一些（有序的/無序的）數(shù)據(jù)元素中，通過一定的方法找出與給定關鍵字相同的數(shù)據(jù)元素就叫做查找；

④、統(tǒng)計

指對有關數(shù)據(jù)的搜集、整理、計算、分析、解釋、表述等的活動。

 

3、總結

　　本章主要簡單介紹了下數(shù)據(jù)結構和算法的概念，后面會繼續(xù)帶大家講解下它們的一些實現(xiàn)過程，敬請期待吧騷年！