演算法分析員面試題

1. 互聯網公司最常見的演算法面試題有哪些

很多人都搞不清辭職的流程方法，所以才會遇到這種尷尬的局面。

提出離職之前，應當先提出加薪申請。如果加薪通過，你繼續安心幹活，如果加薪申請被駁回，直接辭職信奉上，再也不要相信任何挽留的條件。

當然，你提出加薪申請的時候，千萬不要流露出老子早找好下家了，不給加薪老子就炒你魷魚這樣的表情，這對於談判沒什麼幫助。多談談自己對公司的貢獻，不要說公司之外的事情。 來自職Q用戶：蘿卜三人行
幾乎必問排序，排序演算法不下十種，不一定非要用快排，這種問題答的越多越好。 來自職Q用戶：兔小灰

2. 大公司筆試面試有哪些經典演算法題目

1、二維數組中的查找

具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？

3. 演算法面試

我在《再談「我是怎麼招程序員」》中比較保守地說過，「問難的演算法題並沒有錯，錯的很多面試官只是在膚淺甚至錯誤地理解著面試演算法題的目的。」，今天，我想加強一下這個觀點——我反對純演算法題面試！（注意，我說的是純演算法題）圖片源Wikipedia（點擊圖片查看詞條）我再次引用我以前的一個觀點——能解演算法題並不意味著這個人就有能力就能在工作中解決問題，你可以想想，小學奧數題可能比這些題更難，但並不意味著那些奧數能手就能解決實際問題。好了，讓我們來看一個示例（這個示例是昨天在微博上的一個討論），這個題是——「找出無序數組中第2大的數」，幾乎所有的人都用了O(n)的演算法，我相信對於我們這些應試教育出來的人來說，不用排序用O(n)演算法是很正常的事，連我都不由自主地認為O(n)演算法是這個題的標准答案。我們太習慣於標准答案了，這是我國教育最悲哀的地方。（廣義的洗腦就是讓你的意識依賴於某個標准答案，然後通過給你標准答案讓你不會思考而控制你）功能性需求分析試想，如果我們在實際工作中得到這樣一個題 我們會怎麼做？我一定會分析這個需求，因為我害怕需求未來會改變，今天你叫我找一個第2大的數，明天你找我找一個第4大的數，後天叫我找一個第100大的數，我不搞死了。需求變化是很正常的事。分析完這個需求後，我會很自然地去寫找第K大數的演算法——難度一下子就增大了。很多人會以為找第K大的需求是一種「過早擴展」的思路，不是這樣的，我相信我們在實際編碼中寫過太多這樣的程序了，你一定不會設計出這樣的函數介面 —— Find2ndMaxNum(int* array, int len)，就好像你不會設計出 DestroyBaghdad(); 這樣的介面，而是設計一個DestoryCity( City& ); 的介面，而把Baghdad當成參數傳進去！所以，你應該是聲明一個叫FindKthMaxNum(int* array, int len, int kth)，把2當成參數傳進去。這是最基本的編程方法，用數學的話來說，叫代數！最簡單的需求分析方法就是把需求翻譯成函數名，然後看看是這個介面不是很二？！（註：不要糾結於FindMaxNum()或FindMinNum()，因為這兩個函數名的業務意義很清楚了，不像Find2ndMaxNum()那麼二）非功能性需求分析性能之類的東西從來都是非功能性需求，對於演算法題，我們太喜歡研究演算法題的空間和時間復雜度了。我們希望做到空間和時間雙豐收，這是演算法學術界的風格。所以，習慣於標准答案的我們已經失去思考的能力，只會機械地思考演算法之內的性能，而忽略了演算法之外的性能。如果題目是——「從無序數組中找到第K個最大的數」，那麼，我們一定會去思考用O(n)的線性演算法找出第K個數。事實上，也有線性演算法——STL中可以用nth_element求得類似的第n大的數，其利用快速排序的思想，從數組S中隨機找出一個元素X，把數組分為兩部分Sa和Sb。Sa中的元素大於等於X，Sb中元素小於X。這時有兩種情況：1）Sa中元素的個數小於k，則Sb中的第 k-|Sa|個元素即為第k大數；2） Sa中元素的個數大於等於k，則返回Sa中的第k大數。時間復雜度近似為O(n)。搞學術的nuts們到了這一步一定會歡呼勝利！但是他們哪裡能想得到性能的需求分析也是來源自業務的！我們一說性能，基本上是個人都會問，請求量有多大？如果我們的FindKthMaxNum()的請求量是m次，那麼你的這個每次都要O(n)復雜度的演算法得到的效果就是O(n*m)，這一點，是書獃子式的學院派人永遠想不到的。因為應試教育讓我們不會從實際思考了。工程式的解法根據上面的需求分析，有軟體工程經驗的人的解法通常會這樣：1）把數組排序，從大到小。2）於是你要第k大的數，就直接訪問 array[k]。排序只需要一次，O(n*log(n))，然後，接下來的m次對FindKthMaxNum()的調用全是O(1)的，整體復雜度反而成了線性的。其實，上述的還不是工程式的最好的解法，因為，在業務中，那數組中的數據可能會是會變化的，所以，如果是用數組排序的話，有數據的改動會讓我重新排序，這個太耗性能了，如果實際情況中會有很多的插入或刪除操作，那麼可以考慮使用B+樹。工程式的解法有以下特點：1）很方便擴展，因為數據排好序了，你還可以方便地支持各種需求，如從第k1大到k2大的數據（那些學院派寫出來的代碼在拿到這個需求時又開始撓頭苦想了）2）規整的數據會簡化整體的演算法復雜度，從而整體性能會更好。（公欲善其事，必先利其器）3）代碼變得清晰，易懂，易維護！（學院派的和STL一樣的近似O(n)復雜度的演算法沒人敢動）爭論你可能會和我有以下爭論，如果程序員做這個演算法題用排序的方式，他一定不會像你想那麼多。是的，你說得對。但是我想說，很多時候，我們直覺地思考，恰恰是正確的路。因為「排序」這個思路符合人類大腦處理問題的方式，而使用學院派的方式是反大腦直覺的。反大腦直覺的，通常意味著晦澀難懂，維護成本上升。就是一道面試題，我就是想測試一下你的演算法技能，這也扯太多了。沒問題，不過，我們要清楚我們是在招什麼人？是一個只會寫演算法的人，還是一個會做軟體的人？這個只有你自己最清楚。這個演算法題太容易誘導到學院派的思路了。是的這道「找出第K大的數」，其實可以變換為更為業務一點的題目——「我要和別的商戶競價，我想排在所有競爭對手報價的第K名，請寫一個程序，我輸入K，和一個商品名，系統告訴我應該訂多少價？（商家的所有商品的報價在一數組中）」——業務分析，整體性能，演算法，數據結構，增加需求讓應聘者重構，這一個問題就全考了。你是不是在說演算法不重要，不用學？千萬別這樣理解我，搞得好像如果面試不面，我就可以不學。演算法很重要，演算法題能鍛煉我們的思維，而且也有很多實際用處。我這篇文章不是讓大家不要去學演算法，這是完全錯誤的，我是讓大家帶著業務問題去使用演算法。問你業務問題，一樣會問到演算法題上來。小結看過這上面的分析，我相信你明白我為什麼反對純演算法面試題了。原因就是純演算法的面試題根本不能反應一個程序的綜合素質！那麼，在面試中，我們應該要考量程序員的那些綜合素質呢？我以為有下面這些東西：會不會做需求分析？怎麼理解問題的？解決問題的思路是什麼？想法如何？會不會對基礎的演算法和數據結構靈活運用？另外，我們知道，對於軟體開發來說，在工程上，難是的下面是這些挑戰：軟體的維護成本遠遠大於軟體的開發成本。軟體的質量變得越來越重要，所以，測試工作也變得越來越重要。軟體的需求總是在變的，軟體的需求總是一點一點往上加的。程序中大量的代碼都是在處理一些錯誤的或是不正常的流程。所以，對於編程能力上，我們應該主要考量程序員的如下能力：設計是否滿足對需求的理解，並可以應對可能出現的需求變化。

4. java演算法面試題

三個for循環，第一個和第二個有啥區別?去掉一個吧
可以用迭代器remove方法，在移除的同時添加。

不知道是你記錯了還是題本身就這樣，我只想說：
寫這代碼的是二貨么？
1、每個循環的索引都是從0開始，這是什麼遍歷方式？
2、看這題的目的是想把用戶添加到相應的組里，這我就不明白了，新建一個用戶的時候就沒分配組么？那用戶的GroupId哪來的？

3、這是一個操作，難道就不會根據GroupId直接查出用戶或者組么？

這哪是優化代碼？分明是挖坑。

5. 面試數據分析師的常見問題

面試數據分析師的常見問題。數據分析師指的是不同行業中，專門從事行業數據搜集、整理、分析，並依據數據做出行業研究、評估和預測的專業人員。那麼在應聘數據分析師這一職位的求職者會面臨哪些面試問題呢？

1、告訴我二個分析或者計算機科學相關項目？你是如何對其結果進行衡量的？
2、如何讓一個網路爬蟲速度更快、抽取更好的信息以及更好總結數據從而得到一干凈的資料庫？
3、什麼是：提升值、關鍵績效指標、強壯性、模型按合度、實驗設計、2/8原則？
4、什麼是：協同過濾、n-grams, map rece、餘弦距離？
5、點擊流數據應該是實時處理？為什麼？哪部分應該實時處理？
6、如何設計一個解決抄襲的方案？
7、如何檢驗一個個人支付賬戶都多個人使用？
8、什麼是概率合並(AKA模糊融合)？使用SQL處理還是其它語言方便？對於處理半結構化的數據你會選擇使用哪種語言？
9、你認為哪個更好：是好的數據還是好模型？同時你是如何定義「好」？存在所有情況下通用的模型嗎？有你沒有知道一些模型的定義並不是那麼好？
10、你最喜歡的編程語言是什麼？為什麼？
11、你是如何處理缺少數據的？你推薦使用什麼樣的處理技術？
12、什麼是大數據的詛咒？
13、對於你喜歡的統計軟體告訴你喜歡的與不喜歡的3個理由。
14、SAS, R, Python, Perl語言的區別是？
15、你喜歡TD資料庫的什麼特徵？
16、你參與過資料庫與數據模型的設計嗎？
17、你是否參與過儀表盤的設計及指標選擇？你對於商業智能和報表工具有什麼想法？
18、請舉例說明maprece是如何工作的？在什麼應用場景下工作的很好？雲的安全問題有哪些？
19、如何你打算發100萬的營銷活動郵件。你怎麼去優化發送？你怎麼優化反應率？能把這二個優化份開嗎？
20、如果有幾個客戶查詢ORACLE資料庫的效率很低。為什麼？你做什麼可以提高速度10倍以上，同時可以更好處理大數量輸出？
21、如何把非結構化的數據轉換成結構化的數據？這是否真的有必要做這樣的轉換？把數據存成平面文本文件是否比存成關系資料庫更好？
22、什麼是哈希表碰撞攻擊？怎麼避免？發生的頻率是多少？
23、如何判別maprece過程有好的負載均衡？什麼是負載均衡？
24、你處理過白名單嗎？主要的規則？(在欺詐或者爬行檢驗的情況下)
25、(在內存滿足的情況下)你認為是100個小的哈希表好還是一個大的哈希表，對於內在或者運行速度來說？對於資料庫分析的評價？
26、為什麼樸素貝葉斯差？你如何使用樸素貝葉斯來改進爬蟲檢驗演算法？
27、普通線性回歸模型的缺陷是什麼？你知道的其它回歸模型嗎？
28、什麼是星型模型？什麼是查詢表？
29、你可以使用excel建立邏輯回歸模型嗎？如何可以，說明一下建立過程？
30、在SQL, Perl, C++, Python等編程過程上，待為了提升速度優化過相關代碼或者演算法嗎？如何及提升多少？
31、使用5天完成90%的精度的解決方案還是花10天完成100%的精度的解決方案？取決於什麼內容？
32、定義：QA(質量保障)、六西格瑪、實驗設計。好的與壞的實驗設計能否舉個案例？
33、什麼是敏感性分析？擁有更低的敏感性(也就是說更好的強壯性)和低的預測能力還是正好相反好？你如何使用交叉驗證？你對於在數據集中插入雜訊數據從而來檢驗模型的敏感性的想法如何看？
34、你認為葉數小於50的決策樹是否比大的好？為什麼？
35、保險精算是否是統計學的一個分支？如果不是，為何如何？
36、給出一個不符合高斯分布與不符合對數正態分布的數據案例。給出一個分布非常混亂的數案例。
37、你如何建議一個非參數置信區間？
38、你如何證明你帶來的演算法改進是真的有效的與不做任何改變相比？你對A/B測試熟嗎？
39、為什麼說均方誤差不是一個衡量模型的好指標？你建議用哪個指標替代？
40、對於一下邏輯回歸、決策樹、神經網路。在過去15年中這些技術做了哪些大的改進？
41、除了主成分分析外你還使用其它數據降維技術嗎？你怎麼想逐步回歸？你熟悉的逐步回歸技術有哪些？什麼時候完整的數據要比降維的數據或者樣本好？
42、如何創建一個關鍵字分類？
43、你熟悉極值理論、蒙特卡羅邏輯或者其它數理統計方法以正確的評估一個稀疏事件的發生概率？
44、什麼是歸因分析？如何識別歸因與相關系數？舉例。
45、如何定義與衡量一個指標的預測能力？
46、如何為欺詐檢驗得分技術發現最好的規則集？你如何處理規則冗餘、規則發現和二者的本質問題？一個規則集的近似解決方案是否可行？如何尋找一個可行的近似方案？你如何決定這個解決方案足夠好從而可以停止尋找另一個更好的？
47、什麼是概念驗證？
48、什麼是僵屍網路？如何進行檢測？
49、你有使用過API介面的經驗嗎？什麼樣的API？是谷歌還是亞馬遜還是軟體即時服務？
50、什麼時候自己編號代碼比使用數據科學者開發好的軟體包更好？
51、可視化使用什麼工具？在作圖方面，你如何評價Tableau？R？SAS？在一個圖中有效展現五個維度？
52、是假陽性好還是假陰性好？
53、你主要與什麼樣的客戶共事：內部、外部、銷售部門/財務部門/市場部門/IT部門的人？有咨詢經驗嗎？與供應商打過交道，包括供應商選擇與測試。
54、你熟悉軟體生命周期嗎？及IT項目的生命周期，從收入需求到項目維護？
55、什麼是cron任務？
56、你是一個獨身的編碼人員？還是一個開發人員？或者是一個設計人員？
57、什麼讓一個圖形使人產生誤解、很難去讀懂或者解釋？一個有用的圖形的特徵？
58、你熟悉價格優化、價格彈性、存貨管理、競爭智能嗎？分別給案例。
59、Zillow』s演算法是如何工作的？
60、如何檢驗為了不好的目的還進行的虛假評論或者虛假的FB帳戶？
61、你如何創建一個新的匿名數字帳戶？
62、你有沒有想過自己創業？是什麼樣的想法？
63、你認為帳號與密碼輸入的登錄框會消失嗎？它將會被什麼替代？
64、你用過時間序列模型嗎？時滯的相關性？相關圖？光譜分析？信號處理與過濾技術？在什麼樣的場景下？
65、哪位數據科學有你最佩服？從哪開始？
66、你是怎麼開始對數據科學感興趣的？
67、你覺得下一個20年最好的5個預測方法是？
68、什麼是推薦引擎？它是如何工作的？
69、什麼是精密測試？如何及什麼時候模擬可以幫忙我們不使用精密測試？
70、你認為怎麼才能成為一個好的數據科學家？
71、你認為數據科學家是一個藝術家還是科學家？
72、你怎麼馬上就知道在一篇文章中(比如報紙)發表的統計數字是錯誤，或者是用作支撐作者的論點，而不是僅僅在羅列某個事物的信息？例如，對於每月官方定期在媒體公開發布的失業統計數據，你有什麼感想？怎樣可以讓這些數據更加准確？
73、給出一些在數據科學中「最佳實踐的案例」。
74、什麼是效率曲線？他們的缺陷是什麼，你如何克服這些缺陷？
75、你處理過的最大的數據量？你是如何處理他們的？處理的結果。
76、什麼是一個好的、快速的聚類演算法的的計算復雜度？什麼好的聚類演算法？你怎麼決定一個聚類的聚數？
77、你知道使用在統計或者計算科學中的「經驗法則」嗎？或者在商業分析中。
上述的這些問題在面試數據分析師的求職者中非常容易遇到的，有些的涉及到專業性的問題，因此在面試之前一定要做好充足的准備！

6. JAVA演算法面試題：哪位高人會做

就把演算法給你寫一下：
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
for(int k = 1;k<=n;k++)
{
if(i==j || i==k || j==k)
continue;
else
System.out.println(i*100+j*10+k);

}

7. 數據分析師面試題目和答案:動手題

【導讀】眾所周知，隨著社會的發展，數據分析師成為了炙手可熱的熱門執業，一方面是其高薪待遇另一方面就是其未來廣闊的發展前景。一般情況下用人單位會給問答題和動手題來檢測應聘者的真實實力，可以說面試筆試是非常重要的一個環節。它可以直接測驗你對數據分析具體理論的掌握程度和動手操作的能力。為此小編就以此為例和大家說說2020年數據分析面試解答技巧:動手題，希望對大家有所幫助。

動手題

1. 我給你一組數據，如果要你做數據清洗，你會怎麼做?

實際上，這一道題中，面試官考核的是基本的數據清洗的准則，數據清洗是數據分析必不可少的重要環節。你可能看到這個數據存在 2 個問題：典韋出現了 2
次，張飛的數學成績缺失。

針對重復行，你需要刪掉其中的一行。針對數據缺失，你可以將張飛的數學成績補足。

2. 豆瓣電影數據集關聯規則挖掘

在數據分析領域，有一個很經典的案例，那就是「啤酒 +
尿布」的故事。它實際上體現的就是數據分析中的關聯規則挖掘。不少公司會對這一演算法進行不同花樣的考察，但萬變不離其宗。

如果讓你用 Apriori 演算法，分析電影數據集中的導演和演員信息，從而發現兩者之間的頻繁項集及關聯規則，你會怎麼做?

以上就是小編今天給大家整理發送的關於「數據分析師面試題目和答案:動手題」的相關內容，希望對大家有所幫助。想了解更多關於數據分析及人工智慧就業崗位分析，關注小編持續更新。

8. 演算法面試題 無序數組判斷是否有重復數 面試題 時間on 空間o1

//100萬不是很大
import java.util.*;
public class Test{

public static void main(String[] args){

int[] a = new int[1000000];

for(int i = 0; i<1000000;i++){
a[i] = i+1; //從1--1000000沒有重復的
}

a[355] = 100;//將第356個數改成100，這樣就只有兩個重復的數100

List list = new ArrayList();

for(int i = 0 ; i < 1000000;i++){
Integer temp = new Integer(a[i]);
if(!list.contains(temp)){
list.add(temp);
}else{
int j = list.indexOf(temp) ;//第一次出現
System.out.println("第"+(j+1)+"個數和第"+(i+1)+"個數重復為："+temp);
break; //找到即退出
}
}

}
}

9. java演算法面試題：排序都有哪幾種方法

一、冒泡排序
[java] view plain
package sort.bubble;
import java.util.Random;
/**
* 依次比較相鄰的兩個數，將小數放在前面，大數放在後面
* 冒泡排序，具有穩定性
* 時間復雜度為O（n^2）
* 不及堆排序，快速排序O（nlogn，底數為2）
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for(int i = 0 ; i < 10 ; i++){
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for(int i : sort){
System.out.print(i+" ");
}
buddleSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for(int i : sort){
System.out.print(i+" ");
}
}
/**
* 冒泡排序
* @param sort
*/
private static void buddleSort(int[] sort){
for(int i=1;i<sort.length;i++){
for(int j=0;j<sort.length-i;j++){
if(sort[j]>sort[j+1]){
int temp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = temp;
}
}
}
}
}
二、選擇排序
[java] view plain
package sort.select;
import java.util.Random;
/**
* 選擇排序
* 每一趟從待排序的數據元素中選出最小（或最大）的一個元素，
* 順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
* 選擇排序是不穩定的排序方法。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
selectSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 選擇排序
* @param sort
*/
private static void selectSort(int[] sort){
for(int i =0;i<sort.length-1;i++){
for(int j = i+1;j<sort.length;j++){
if(sort[j]<sort[i]){
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}
}
三、快速排序
[java] view plain
package sort.quick;
/**
* 快速排序 通過一趟排序將要排序的數據分割成獨立的兩部分， 其中一部分的所有數據都比另外一部分的所有數據都要小，
* 然後再按此方法對這兩部分數據分別進行快速排序， 整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
System.out.print("排序前的數組為：");
for (int data : sort) {
System.out.print(data + " ");
}
System.out.println();
quickSort(sort, 0, sort.length - 1);
System.out.print("排序後的數組為：");
for (int data : sort) {
System.out.print(data + " ");
}
}
/**
* 快速排序
* @param sort 要排序的數組
* @param start 排序的開始座標
* @param end 排序的結束座標
*/
public static void quickSort(int[] sort, int start, int end) {
// 設置關鍵數據key為要排序數組的第一個元素，
// 即第一趟排序後，key右邊的數全部比key大，key左邊的數全部比key小
int key = sort[start];
// 設置數組左邊的索引，往右移動判斷比key大的數
int i = start;
// 設置數組右邊的索引，往左移動判斷比key小的數
int j = end;
// 如果左邊索引比右邊索引小，則還有數據沒有排序
while (i < j) {
while (sort[j] > key && j > start) {
j--;
}
while (sort[i] < key && i < end) {
i++;
}
if (i < j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
// 如果左邊索引比右邊索引要大，說明第一次排序完成，將sort[j]與key對換，
// 即保持了key左邊的數比key小，key右邊的數比key大
if (i > j) {
int temp = sort[j];
sort[j] = sort[start];
sort[start] = temp;
}
//遞歸調用
if (j > start && j < end) {
quickSort(sort, start, j - 1);
quickSort(sort, j + 1, end);
}
}
}
[java] view plain
/**
* 快速排序
*
* @param a
* @param low
* @param high
* voidTest
*/
public static void kuaisuSort(int[] a, int low, int high)
{
if (low >= high)
{
return;
}
if ((high - low) == 1)
{
if (a[low] > a[high])
{
swap(a, low, high);
return;
}
}
int key = a[low];
int left = low + 1;
int right = high;
while (left < right)
{
while (left < right && left <= high)// 左邊向右
{
if (a[left] >= key)
{
break;
}
left++;
}
while (right >= left && right > low)
{
if (a[right] <= key)
{
break;
}
right--;
}
if (left < right)
{
swap(a, left, right);
}
}
swap(a, low, right);
kuaisuSort(a, low, right);
kuaisuSort(a, right + 1, high);
}
四、插入排序
[java] view plain
package sort.insert;
/**
* 直接插入排序
* 將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據
* 演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。
*/
import java.util.Random;
public class DirectMain {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
directInsertSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*
* @param sort
*/
private static void directInsertSort(int[] sort) {
for (int i = 1; i < sort.length; i++) {
int index = i - 1;
int temp = sort[i];
while (index >= 0 && sort[index] > temp) {
sort[index + 1] = sort[index];
index--;
}
sort[index + 1] = temp;
}
}
}
順便添加一份，差不多的
[java] view plain
public static void charuSort(int[] a)
{
int len = a.length;
for (int i = 1; i < len; i++)
{
int j;
int temp = a[i];
for (j = i; j > 0; j--)//遍歷i之前的數字
{
//如果之前的數字大於後面的數字，則把大的值賦到後面
if (a[j - 1] > temp)
{
a[j] = a[j - 1];
} else
{
break;
}
}
a[j] = temp;
}
}
把上面整合起來的一份寫法：
[java] view plain
/**
* 插入排序:
*
*/
public class InsertSort {
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}
private void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
五、順便貼個二分搜索法
[java] view plain
package search.binary;
public class Main {
public static void main(String[] args) {
int[] sort = {1,2,3,4,5,6,7,8,9,10};
int mask = binarySearch(sort,6);
System.out.println(mask);
}
/**
* 二分搜索法，返回座標，不存在返回-1
* @param sort
* @return
*/
private static int binarySearch(int[] sort,int data){
if(data<sort[0] || data>sort[sort.length-1]){
return -1;
}
int begin = 0;
int end = sort.length;
int mid = (begin+end)/2;
while(begin <= end){
mid = (begin+end)/2;
if(data > sort[mid]){
begin = mid + 1;
}else if(data < sort[mid]){
end = mid - 1;
}else{
return mid;
}
}
return -1;
}
}