前言
工作已經有一段時間了，有的時候會跟同事們打趣：“
如果你讓我現在去手寫一個快速排序，我怕是真的寫不出來”。如果不接觸一段時間的算法，真的很容易就忘了。不信？你現在想想你自己能不能手寫一個堆排序。
經歷過校招的人都知道，算法和數據結構都是不可避免的。
在筆試的時候，最主要的就是靠算法題。像拼多多、頭條這種大公司，上來就來幾道算法題，如果你沒AC出來，面試機會都沒有。
在面試（現場面或者視頻面）的時候也會問算法題，難度肯定是沒有筆試的時候那麼難的。我們可以想象一個場景，一面面試面到一半，面試官讓你反轉二叉樹，問問現在的自己，你還會嗎。
不扯遠了，如果還在上大學的同學可以先以排序和各種的基本數據結構開始入門。我花了一個星期將八大基礎排序和鏈表/二叉樹/棧/隊列製作成一份精美的PDF。
這份PDF閱讀體驗肯定是要比公眾號和各大的博客平臺的文章要好的。PDF內容純手打，有不懂的可以來問我。
下面來簡單介紹一下八大基礎排序和基礎的數據結構，每種排序的思想和基礎的講解和源碼在PDF裡邊有。
冒泡排序
思路：倆倆交換，大的放在後面，第一次排序後最大值已在數組末尾。因為倆倆交換，需要n-1趟排序（比如10個數，需要9趟排序）
代碼實現要點：兩個for循環，外層循環控制排序的趟數，內層循環控制比較的次數。每趟過後，比較的次數都應該要減1
選擇排序
思路：找到數組中最大的元素，與數組最後一位元素交換。當只有一個數時，則不需要選擇了，因此需要n-1趟排序
代碼實現要點：兩個for循環，外層循環控制排序的趟數，內層循環找到當前趟數的最大值，隨後與當前趟數組最後的一位元素交換
插入排序
思路：將一個元素插入到已有序的數組中，在初始時未知是否存在有序的數據，因此將元素第一個元素看成是有序的。與有序的數組進行比較，比它大則直接放入，比它小則移動數組元素的位置，找到個合適的位置插入。當只有一個數時，則不需要插入了，因此需要n-1趟排序
代碼實現：一個for循環內嵌一個while循環實現，外層for循環控制需要排序的趟數，while循環找到合適的插入位置(並且插入的位置不能小於0)
快速排序
學習快速排序的前提：需要了解遞歸
思路：在數組中找一個元素(節點)，比它小的放在節點的左邊，比它大的放在節點右邊。一趟下來，比節點小的在左邊，比節點大的在右邊。不斷執行這個操作….
代碼實現：支點取中間，使用L和R表示數組的最小和最大位置。不斷進行比較，直到找到比支點小(大)的數，隨後交換，不斷減小範圍。遞歸L到支點前一個元素(j)。遞歸支點後一個元素(i)到R元素
歸併排序
學習歸併排序的前提：需要了解遞歸
思路：將兩個已排好序的數組合併成一個有序的數組。將元素分隔開來，看成是有序的數組，進行比較合併。不斷拆分和合並，直到只有一個元素
代碼實現：在第一趟排序時實質是兩個元素(看成是兩個已有序的數組)來進行合併，不斷執行這樣的操作，最終數組有序，拆分左邊，右邊，合併…
堆排序
學習堆排序的前提：需要了解二叉樹
思路：堆排序使用到了完全二叉樹的一個特性，根節點比左孩子和右孩子都要大，完成一次建堆的操作實質上是比較根節點和左孩子、右孩子的大小，大的交換到根節點上，直至最大的節點在樹頂。隨後與數組最後一位元素進行交換
代碼實現：只要左子樹或右子樹大於當前根節點，則替換。替換後會導致下面的子樹發生了變化，因此同樣需要進行比較，直至各個節點實現父>子這麼一個條件
希爾排序
思路：希爾排序實質上就是插入排序的增強版，希爾排序將數組分隔成n組來進行插入排序，直至該數組宏觀上有序，最後再進行插入排序時就不用移動那麼多次位置了～
代碼思路：希爾增量一般是gap = gap / 2，只是比普通版插入排序多了這麼一個for循環而已。
基數排序(桶排序)
思路：基數排序(桶排序)：將數字切割成個、十、百、千位放入到不同的桶子裡，放一次就按桶子順序回收一次，直至最大位數的數字放完～那麼該數組就有序了
代碼實現：先找到數組的最大值，然後根據最大值/10來作為循環的條件(只要>0，那麼就說明還有位數)。將個位、十位、…分配到桶子上，每分配一次就回收一次
遞歸
遞歸在算法裡邊用得非常非常多，排序算法的快速排序和歸併排序就需要用到遞歸（至少用遞歸來實現是最方便的）。
想要用遞歸必須知道兩個條件：遞歸出口(終止遞歸的條件)和遞歸表達式(規律)
技巧：在遞歸中常常是將問題切割成兩個部分(1和整體的思想)，這能夠讓我們快速找到遞歸表達式(規律)
漢羅塔實現：
基本數據結構
鏈表、隊列、二叉樹、棧都是些非常基本的數據結構。針對每種的數據結構都會有對應的算法題，比如說：
- LeetCode No206：反轉鏈表
- LeetCode No20：檢驗字符串[]{]}{]{}(這樣的字符串是否有效(對齊)
- LeetCode No104：樹的最大深度
- LeetCode No102：層序遍歷樹
- ...
在校招不求字典樹、紅黑樹、圖這種數據結構要會，但鏈表、隊列、二叉樹、棧這些數據結構的題（LeetCode簡單） 還是應該要能做出來。
最後
最後想要說明的是，排序算法/數據結構的代碼可能不是最優解，代碼的實現都是以比較容易理解的方式去寫的。幾乎每句代碼都有對應的註釋，應該是能看懂的。
閱讀更多 Java高級架構 的文章
