又是新的一年,去年“金九銀十”沒趕上,問到算法一臉懵逼,吞吞吐吐。今年重振旗鼓,記住下面這些算法,手撕面試官!趕上“金三銀四”的首班車!
二分查找
又叫折半查找,要求待查找的序列有序。每次取中間位置的值與待查關鍵字比較,如果中間位置
的值比待查關鍵字大,則在前半部分循環這個查找的過程,如果中間位置的值比待查關鍵字小,
則在後半部分循環這個查找的過程。直到查找到了為止,否則序列中沒有待查的關鍵字。
冒泡排序算法
(1)比較前後相鄰的二個數據,如果前面數據大於後面的數據,就將這二個數據交換。
(2)這樣對數組的第 0 個數據到 N-1 個數據進行一次遍歷後,最大的一個數據就“沉”到數組第
N-1 個位置。
(3)N=N-1,如果 N 不為 0 就重複前面二步,否則排序完成。
public static void bubbleSort1(int [] a, int n){
int i, j;
for(i=0; i
for(j=1; j
if(a[j-1] > a[j]){//前面的數字大於後面的數字就交換
//交換 a[j-1]和 a[j]
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j]=temp;
}
}
} }
插入排序算法
通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應的位置並插入。
插入排序非常類似於整撲克牌。在開始摸牌時,左手是空的,牌面朝下放在桌上。接著,一次從
桌上摸起一張牌,並將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置,要將
它與手中已有的牌從右到左地進行比較。無論什麼時候,左手中的牌都是排好序的。
如果輸入數組已經是排好序的話,插入排序出現最佳情況,其運行時間是輸入規模的一個線性函
數。如果輸入數組是逆序排列的,將出現最壞情況。平均情況與最壞情況一樣,其時間代價是(n2)。
public void sort(int arr[])
{
for(int i =1; i
{
//插入的數
int insertVal = arr[i];
//被插入的位置(準備和前一個數比較)
int index = i-1;
//如果插入的數比被插入的數小
while(index>=0&&insertVal
{
//將把 arr[index] 向後移動
arr[index+1]=arr[index];
//讓 index 向前移動
index--;
}
//把插入的數放入合適位置
arr[index+1]=insertVal;
}
}
快速排序算法
快速排序的原理:選擇一個關鍵值作為基準值。比基準值小的都在左邊序列(一般是無序的),
比基準值大的都在右邊(一般是無序的)。一般選擇序列的第一個元素。
一次循環:從後往前比較,用基準值和最後一個值比較,如果比基準值小的交換位置,如果沒有
繼續比較下一個,直到找到第一個比基準值小的值才交換。找到這個值之後,又從前往後開始比
較,如果有比基準值大的,交換位置,如果沒有繼續比較下一個,直到找到第一個比基準值大的
值才交換。直到從前往後的比較索引>從後往前比較的索引,結束第一次循環,此時,對於基準值
來說,左右兩邊就是有序的了。
public void sort(int[] a,int low,int high){
int start = low;
int end = high;
int key = a[low];
while(end>start){
//從後往前比較
while(end>start&&a[end]>=key)
//如果沒有比關鍵值小的,比較下一個,直到有比關鍵值小的交換位置,然後又從前往後比較
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//從前往後比較
while(end>start&&a[start]<=key)
//如果沒有比關鍵值大的,比較下一個,直到有比關鍵值大的交換位置
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此時第一次循環比較結束,關鍵值的位置已經確定了。左邊的值都比關鍵值小,右邊的
值都比關鍵值大,但是兩邊的順序還有可能是不一樣的,進行下面的遞歸調用
}
//遞歸
if(start>low) sort(a,low,start-1);//左邊序列。第一個索引位置到關鍵值索引-1
if(end
}
}
希爾排序算法
基本思想:先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,待整個序列
中的記錄“基本有序”時,再對全體記錄進行依次直接插入排序。
1. 操作方法:
選擇一個增量序列 t1,t2,…,tk,其中 ti>tj,tk=1;
2. 按增量序列個數 k,對序列進行 k 趟排序;
3. 每趟排序,根據對應的增量 ti,將待排序列分割成若干長度為 m 的子序列,分別對各子表進
行直接插入排序。僅增量因子為1 時,整個序列作為一個表來處理,表長度即為整個序列的長
度。
總結
由於文章篇幅原因,還有幾個算法就不一一寫出來了,小編專門整理了一篇面試集錦,裡面有全面的算法解析,和其他面試經常問到的知識點的總結,希望能對即將在2020年求職的碼友們有所幫助,需要這篇面試集錦的朋友可以,關注加私信回覆小編“面試資料”即可免費領取。
微服務:
Java集合和線程: