常見的加密算法、排序算法都需要自己提前瞭解一下，排序算法最好自己能夠獨立手寫出來。
我覺得面試中最刺激、最有壓力或者說最有挑戰的一個環節就是手撕算法了。面試中大部分算法題目都是來自於Leetcode、劍指offer上面，建議大家可以每天擠出一點時間刷一下算法題。
推薦兩個刷題必備網站：
LeetCode：
- LeetCode（中國）官網
- 如何高效地使用 LeetCode
牛客網：
- 牛客網首頁
8.1 舉個栗子（手寫快排）
面試官可能會問你，瞭解哪些排序方法啊？除了冒泡排序和選擇排序能不能給我手寫一個其他的排序算法。或者面試官可能會直接問你：“能不能給我手寫一個快排出來？”。
快排的基本思想： 通過選擇的參考值將待排序記錄分割成獨立的兩部分，一部分全小於選取的參考值，另一部分全大於選取的參考值。對分割之後的部分再進行同樣的操作直到無法再進行該操作位置(可以使用遞歸)。
下面是我寫的一個簡單的快排算法，我選擇的參考值是數組的第一個元素。
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num = { 1, 3, 4, 8, 5, 10, 22, 15, 16 };
QuickSort.quickSort(num, 0, num.length - 1);
System.out.println(Arrays.toString(num));
}
public static void quickSort(int[] a, int start, int end) {
// 該值定義了從哪個位置開始分割數組
int ref;
if (start < end) {
// 調用partition方法對數組進行排序
ref = partition(a, start, end);
// 對分割之後的兩個數組繼續進行排序
quickSort(a, start, ref - 1);
quickSort(a, ref + 1, end);
}
}
/**
* 選定參考值對給定數組進行一趟快速排序
*
* @param a
* 數組
* @param start
* （切分）每個數組的第一個的元素的位置
* @param end
* （切分）每個數組的最後一個的元素位置
* @return 下一次要切割數組的位置
*/
public static int partition(int[] a, int start, int end) {
// 取數組的第一個值作為參考值（關鍵數據）
int refvalue = a[start];
// 從數組的右邊開始往左遍歷，直到找到小於參考值的元素
while (start < end) {
while (end > start && a[end] >= refvalue) {
end--;
}
// 將元素直接賦予給左邊第一個元素，即pivotkey所在的位置
a[start] = a[end];
// 從序列的左邊邊開始往右遍歷，直到找到大於基準值的元素
while (end > start && a[start] <= refvalue) {
start++;
}
a[end] = a[start];
return end;
}
// 最後的start是基準值所在的位置
a[start] = refvalue;
return start;
}
}
複製代碼時間複雜度分析：
- 在最優的情況下，Partition每次都劃分得很均勻，快速排序算法的時間複雜度為O(nlogn)。
- 最糟糕情況下的快排，當待排序的序列為正序或逆序排列時，時間複雜度為O(n^2)。
空間複雜度分析：
- 最好情況，遞歸樹的深度為log2n，其空間複雜度也就為O(logn)
- 最壞情況，需要進行n‐1遞歸調用，其空間複雜度為O(n)，平均情況，空間複雜度也為O(logn)。
一種簡單優化的方式：
三向切分快速排序 ：核心思想就是將待排序的數據分為三部分,左邊都小於比較值,右邊都大於比較值,中間的數和比較值相等.三向切分快速排序的特性就是遇到和比較值相同時,不進行數據交換, 這樣對於有大量重複數據的排序時,三向切分快速排序算法就會優於普通快速排序算法,但由於它整體判斷代碼比普通快速排序多一點,所以對於常見的大量非重複數據,它並不能比普通快速排序多大多的優勢 。
關注我，私信回覆“資料”，即可領取更多java架構資料！！
分享到:
