我覺得面試中最刺激、最有壓力或者說最有挑戰的一個環節就是手撕算法了。面試中大部分算法題目都是來自於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架構資料！！