Part 1.生產(chǎn)者-消費者問題
這絕對是屬于重點了，不管是考察對于該重要模型的理解還是考察代碼能力，這都是一道很好的考題，所以很有必要的，我們先來回顧一下什么是生產(chǎn)者-消費者問題；
問題簡單回顧
如果想學(xué)習(xí)Java工程化、高性能及分布式、深入淺出。微服務(wù)、Spring，MyBatis，Netty源碼分析的朋友可以加我的Java高級交流：854630135，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費分享給大家。
生產(chǎn)者消費者問題（英語：Producer-consumer problem），也稱有限緩沖問題（英語：Bounded-buffer problem），是一個多線程同步問題的經(jīng)典案例。該問題描述了共享固定大小緩沖區(qū)的兩個線程——即所謂的“生產(chǎn)者”和“消費者”——在實際運行時會發(fā)生的問題。生產(chǎn)者的主要作用是生成一定量的數(shù)據(jù)放到緩沖區(qū)中，然后重復(fù)此過程。與此同時，消費者也在緩沖區(qū)消耗這些數(shù)據(jù)。該問題的關(guān)鍵就是要保證生產(chǎn)者不會在緩沖區(qū)滿時加入數(shù)據(jù)，消費者也不會在緩沖區(qū)中空時消耗數(shù)據(jù)。(摘自維基百科：生產(chǎn)者消費者問題)
注意：?生產(chǎn)者-消費者模式中的內(nèi)存緩存區(qū)的主要功能是數(shù)據(jù)在多線程間的共享，此外，通過該緩沖區(qū)，可以緩解生產(chǎn)者和消費者的性能差；
幾種實現(xiàn)方式
上面說到該問題的關(guān)鍵是：如何保證生產(chǎn)者不會在緩沖區(qū)滿時加入數(shù)據(jù)，消費者也不會在緩沖區(qū)空時消耗數(shù)據(jù)；解決思路可以簡單概括為：
生產(chǎn)者持續(xù)生產(chǎn)，直到緩沖區(qū)滿，滿時阻塞；緩沖區(qū)不滿后，繼續(xù)生產(chǎn)；
消費者持續(xù)消費，直到緩沖區(qū)空，空時阻塞；緩沖區(qū)不空后，繼續(xù)消費；
生產(chǎn)者和消費者都可以有多個；
那么在 Java 語言中，能達到上述要求的，自然而然的就會有如下的幾種寫法，但是問題的核心都是能夠讓消費者和生產(chǎn)者在各自滿足條件需要阻塞時能夠起到正確的作用：
wait()/notify()方式；
await()/signal()方式；
BlockingQueue阻塞隊列方式；
PipedInputStream/PipedOutputStream方式；
手寫代碼，我們著重掌握上面對應(yīng)的第一種和第三種寫法就足夠了；
wait()/notify()方式實現(xiàn)
在手寫代碼之前，我們需要現(xiàn)在 IDE 上實現(xiàn)一遍，理解其中的過程并且找到一些重點/細節(jié)，我們先來代碼走一遍，然后我把我理解的重點給圈兒出來：
生產(chǎn)者代碼
publicclassProducerimplementsRunnable {privatevolatilebooleanisRunning =true;privatefinalVector sharedQueue;// 內(nèi)存緩沖區(qū)privatefinalintSIZE;// 緩沖區(qū)大小privatestaticAtomicIntegercount=newAtomicInteger();// 總數(shù)，原子操作privatestaticfinalintSLEEPTIME =1000;publicProducer(Vector sharedQueue,intSIZE) {this.sharedQueue = sharedQueue;this.SIZE=SIZE; } @Overridepublicvoidrun() {intdata; Random r =newRandom(); System.out.println("start producer id = "+ Thread.currentThread().getId());try{while(isRunning) {// 模擬延遲Thread.sleep(r.nextInt(SLEEPTIME));// 當(dāng)隊列滿時阻塞等待while(sharedQueue.size() ==SIZE) {synchronized(sharedQueue) { System.out.println("Queue is full, producer "+ Thread.currentThread().getId() +" is waiting, size："+ sharedQueue.size()); sharedQueue.wait(); } }// 隊列不滿時持續(xù)創(chuàng)造新元素synchronized(sharedQueue) { data =count.incrementAndGet();// 構(gòu)造任務(wù)數(shù)據(jù)sharedQueue.add(data); System.out.println("producer create data:"+ data +", size："+ sharedQueue.size()); sharedQueue.notifyAll(); } } }catch(InterruptedException e) { e.printStackTrace(); Thread.currentThread().interrupted(); } }publicvoidstop() { isRunning =false; }}
有了上面的提到的解決思路，應(yīng)該很容易實現(xiàn)，但是這里主要提一下一些細節(jié)和重點：
創(chuàng)造數(shù)據(jù)：生產(chǎn)者-消費者解決的問題就是數(shù)據(jù)在多線程間的共享，所以我們首要關(guān)心的問題就應(yīng)該是數(shù)據(jù)，我們這里采用的是使用一個AtomicInteger類來為我們創(chuàng)造數(shù)據(jù)，使用它的好處是該類是一個保證原子操作的類，我們使用其中的incrementAndGet()方法不僅能夠保證線程安全，還可以達到一個計數(shù)的效果，所以是一個既簡單又實用的選擇，當(dāng)然也可以使用其他的數(shù)據(jù)來代替，這里注意的是要保證該類在內(nèi)存中只存在一份，使用static修飾；
如果想學(xué)習(xí)Java工程化、高性能及分布式、深入淺出。微服務(wù)、Spring，MyBatis，Netty源碼分析的朋友可以加我的Java高級交流：854630135，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費分享給大家。
內(nèi)存緩沖區(qū)：要保證在多線程環(huán)境下內(nèi)存緩沖區(qū)的安全，所以我們考慮使用簡單的Vector類來作為我們的內(nèi)存緩沖區(qū)，并且使用final修飾保證內(nèi)存緩沖區(qū)的唯一，然后的話我們需要判斷隊列是否滿，需要手動添加一個標識緩沖區(qū)大小的變量SIZE，注意也是final修飾；
模擬延遲：這里主要模擬的是一個網(wǎng)絡(luò)延遲，我們首先定義了一個SLEEPTIME的延遲范圍，注意使用的是static final修飾，然后使用Random()類的nextInt()方法來隨機選取一個該范圍內(nèi)的值來模擬網(wǎng)絡(luò)環(huán)境中的延遲；
停止方法：首先需要知道在Thread類中有一個棄用的stop()方法，我們自己增加一個標志位isRunning來完成我們自己的stop()功能，需要注意的是使用volatile來修飾，保證該標志位的可見性；
錯誤處理：當(dāng)捕獲到錯誤時，我們應(yīng)該使用Thread類中的interrupted()方法來終止當(dāng)前的進程；
消息提示：我們主要是要在控制臺輸出該生產(chǎn)者的信息，包括當(dāng)前隊列的狀態(tài)，大小，當(dāng)前線程的生產(chǎn)者信息等，注意的是信息格式的統(tǒng)一(后面的消費者同樣的)；
消費者代碼
publicclassConsumerimplementsRunnable {privatefinalVector sharedQueue;// 內(nèi)存緩沖區(qū)privatefinalintSIZE;// 緩沖區(qū)大小privatestaticfinalintSLEEPTIME =1000;publicConsumer(Vector sharedQueue,intSIZE) {this.sharedQueue = sharedQueue;this.SIZE=SIZE; } @Overridepublicvoidrun() { Random r =newRandom(); System.out.println("start consumer id = "+ Thread.currentThread().getId());try{while(true) {// 模擬延遲Thread.sleep(r.nextInt(SLEEPTIME));// 當(dāng)隊列空時阻塞等待while(sharedQueue.isEmpty()) {synchronized(sharedQueue) { System.out.println("Queue is empty, consumer "+ Thread.currentThread().getId() +" is waiting, size："+ sharedQueue.size()); sharedQueue.wait(); } }// 隊列不空時持續(xù)消費元素synchronized(sharedQueue) { System.out.println("consumer consume data："+ sharedQueue.remove(0) +", size："+ sharedQueue.size()); sharedQueue.notifyAll(); } } }catch(InterruptedException e) { e.printStackTrace(); Thread.currentThread().interrupt(); } }}
跟生產(chǎn)者相同的，你需要注意內(nèi)存緩沖區(qū)/?模擬延遲/?錯誤處理/?消息提示這些方面的細節(jié)問題，總體來說消費者就是持續(xù)不斷的消費，也比較容易實現(xiàn)；
主線程代碼
有了我們的消費者和生產(chǎn)者代碼，我們需要來驗證一下它們的正確性，照常理來說我們直接創(chuàng)建一些消費者和生產(chǎn)者的線程讓它們執(zhí)行就可以了啊，但是為了“加分”考慮呢，我們還是使用線程池吧..也不是特別復(fù)雜：
publicstaticvoidmain(Stringargs[]) throws InterruptedException {// 1.構(gòu)建內(nèi)存緩沖區(qū)Vector sharedQueue =newVector();intsize=4;// 2.建立線程池和線程ExecutorService service = Executors.newCachedThreadPool(); Producer prodThread1 =newProducer(sharedQueue,size); Producer prodThread2 =newProducer(sharedQueue,size); Producer prodThread3 =newProducer(sharedQueue,size); Consumer consThread1 =newConsumer(sharedQueue,size); Consumer consThread2 =newConsumer(sharedQueue,size); Consumer consThread3 =newConsumer(sharedQueue,size); service.execute(prodThread1); service.execute(prodThread2); service.execute(prodThread3); service.execute(consThread1); service.execute(consThread2); service.execute(consThread3);// 3.睡一會兒然后嘗試停止生產(chǎn)者Thread.sleep(10*1000); prodThread1.stop(); prodThread2.stop(); prodThread3.stop();// 4.再睡一會兒關(guān)閉線程池Thread.sleep(3000); service.shutdown();}
大家可以自行去看看運行的結(jié)果，是沒有問題的，不會出現(xiàn)多生產(chǎn)或者多消費之類的多線程問題，運行一段時間等生產(chǎn)者都停止之后，我們可以觀察到控制臺三個消費者都在等待數(shù)據(jù)的情況：
Queue is empty, consumer 17 is waiting, size：0Queue is empty, consumer 15 is waiting, size：0Queue is empty, consumer 16 is waiting, size：0
BlockingQueue阻塞隊列方式實現(xiàn)
該方式對比起上面一種方式實現(xiàn)起來要簡單一些，因為不需要手動的去通知其他線程了，生產(chǎn)者直接往隊列中放數(shù)據(jù)直到隊列滿，消費者直接從隊列中獲取數(shù)據(jù)直到隊列空，BlockingQueue會自動幫我們完成阻塞這個動作，還是先來看看代碼
生產(chǎn)者代碼
publicclassProducerimplementsRunnable{privatevolatileboolean isRunning =true;privateBlockingQueuequeue;// 內(nèi)存緩沖區(qū)privatestaticAtomicInteger count =newAtomicInteger();// 總數(shù)，原子操作privatestaticfinalintSLEEPTIME =1000;publicProducer(BlockingQueuequeue){this.queue=queue; } @Overridepublicvoidrun(){intdata; Random r =newRandom(); System.out.println("start producer id = "+ Thread.currentThread().getId());try{while(isRunning) {// 模擬延遲Thread.sleep(r.nextInt(SLEEPTIME));// 往阻塞隊列中添加數(shù)據(jù)data = count.incrementAndGet();// 構(gòu)造任務(wù)數(shù)據(jù)System.out.println("producer "+ Thread.currentThread().getId() +" create data："+ data +", size："+queue.size());if(!queue.offer(data,2, TimeUnit.SECONDS)) { System.err.println("failed to put data："+ data); } } }catch(InterruptedException e) { e.printStackTrace(); Thread.currentThread().interrupted(); } }publicvoidstop(){ isRunning =false; }}
跟上面一種方式?jīng)]有很大的差別，倒是代碼更加簡單通透，不過需要注意的是對阻塞隊列添加失敗的錯誤處理；
消費者代碼
publicclass Consumer implements Runnable {privateBlockingQueuequeue;// 內(nèi)存緩沖區(qū)privatestatic final int SLEEPTIME =1000;publicConsumer(BlockingQueuequeue) { this.queue=queue; } @Overridepublicvoidrun() { intdata; Random r =newRandom(); System.out.println("start consumer id = "+Thread.currentThread().getId()); try {while(true) {// 模擬延遲Thread.sleep(r.nextInt(SLEEPTIME));// 從阻塞隊列中獲取數(shù)據(jù)if(!queue.isEmpty()) {data=queue.take(); System.out.println("consumer "+Thread.currentThread().getId() +" consume data："+data+", size："+queue.size()); }else{ System.out.println("Queue is empty, consumer "+Thread.currentThread().getId() +" is waiting, size："+queue.size()); } } } catch (InterruptedException e) { e.printStackTrace();Thread.currentThread().interrupt(); } }}
主線程代碼
public static void main(Stringargs[]) throwsInterruptedException{// 1.構(gòu)建內(nèi)存緩沖區(qū)BlockingQueue queue =newLinkedBlockingDeque<>();// 2.建立線程池和線程ExecutorServiceservice=Executors.newCachedThreadPool();ProducerprodThread1=newProducer(queue);ProducerprodThread2=newProducer(queue);ProducerprodThread3=newProducer(queue);ConsumerconsThread1=newConsumer(queue);ConsumerconsThread2=newConsumer(queue);ConsumerconsThread3=newConsumer(queue);service.execute(prodThread1);service.execute(prodThread2);service.execute(prodThread3);service.execute(consThread1);service.execute(consThread2);service.execute(consThread3);// 3.睡一會兒然后嘗試停止生產(chǎn)者Thread.sleep(10*1000);prodThread1.stop();prodThread2.stop();prodThread3.stop();// 4.再睡一會兒關(guān)閉線程池Thread.sleep(3000);service.shutdown();}
因為隊列中添加和刪除的操作比較頻繁，所以這里使用LinkedBlockingQueue來作為阻塞隊列，所以這里除了內(nèi)存緩沖區(qū)有所不同以外，其他的都差不多...當(dāng)然你也可以指定一個隊列的大?。?/p>
總結(jié)以及改進
如果想學(xué)習(xí)Java工程化、高性能及分布式、深入淺出。微服務(wù)、Spring，MyBatis，Netty源碼分析的朋友可以加我的Java高級交流：854630135，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費分享給大家。
生產(chǎn)者-消費者模式很好地對生產(chǎn)者線程和消費者線程進行解耦，優(yōu)化了系統(tǒng)整體的結(jié)構(gòu)，同時由于緩沖區(qū)的作用，允許生產(chǎn)者線程和消費者線程存在執(zhí)行上的性能差異，從一定程度上緩解了性能瓶頸對系統(tǒng)性能的影響；上面兩種寫法都是非常常規(guī)的寫法，只能說能起碼能在及格的基礎(chǔ)上加個那么點兒分數(shù)，如果想要得高分可以去搜索搜搜 Disruptor 來實現(xiàn)一個無鎖的生產(chǎn)者-消費者模型....這里就不提及了..
改進：上面的線程輸出可能會有點兒不友好（不直觀），因為我們這里是直接使用的線程的 ID 來作為輸出，我們也可以給線程弄一個名字來作為輸出，以上；
Part 2.排序算法
排序算法當(dāng)然也算是重點考察的對象之一了，畢竟基礎(chǔ)且偏算法，當(dāng)然我們有必要去了解常見的排序算法以及它們采取了怎樣的思想又是如何實現(xiàn)的還有復(fù)雜度的問題，但是這里的話，主要就提及兩種考的比較常見的排序算法：冒泡和快排，以及分別對它們進行的一些優(yōu)化；
冒泡排序
冒泡應(yīng)該是比較基礎(chǔ)的一種算法，我們以從小到大排序為例，它的基礎(chǔ)思想是：從第一個數(shù)開始直到數(shù)組倒數(shù)第二個數(shù)，每一輪都去比較數(shù)組中剩下的數(shù)，如果后面的數(shù)據(jù)更小則兩數(shù)交換，這樣一輪一輪的比較交換下來，最大的那個數(shù)也就“沉到”了數(shù)組的最后，最小的“冒”到了數(shù)組的最前面，這樣就完成了排序工作；
基礎(chǔ)算法代碼（未優(yōu)化）
很簡單，直接上代碼：
/** * 冒泡排序 * *@paramnums 待排序的數(shù)組 */publicvoidbubbleSort(int[] nums){// 正確性判斷if(null== nums || nums.length <=1) {return; }// 從小到大排序for(inti =0; i < nums.length -1; i++) {for(intj = i +1; j < nums.length; j++) {if(nums[i] > nums[j]) { nums[i] = nums[i] + nums[j]; nums[j] = nums[i] - nums[j]; nums[i] = nums[i] - nums[j]; } } }}
這里需要注意：加上正確性判斷；（討論：其實我看大多數(shù)地方都是沒有這個的，不知道有沒有加上的必要...求討論）
另外光寫完實現(xiàn)冒泡排序的算法是不算完的，還要養(yǎng)成良好的習(xí)慣去寫測試單元用例，而且盡可能要考慮到多的點，例如這里的負數(shù)、多個相同的數(shù)之類的特殊情況，我就大概寫一個吧，也歡迎指正：
@Testpublic void bubbleSortTester() {// 測試用例1：驗證負數(shù)是否滿足要求int[] nums = {1,4,2,-2,5,11,-7,0}; bubbleSort(nums);// 輸出測試結(jié)果for (int i =0; i < nums.length; i++) { System.out.print(nums[i] +", "); } System.out.println();// 測試用例2：驗證多個相同的數(shù)是否滿足要求nums = new int[]{1,1,5,7,7,3,1}; bubbleSort(nums);// 輸出測試結(jié)果for (int i =0; i < nums.length; i++) { System.out.print(nums[i] +", "); }}
冒泡排序優(yōu)化
想象一個這樣的場景：如果該數(shù)組基本有序，或者在數(shù)組的后半段基本有序，上面的算法就會浪費許多的時間開銷，所以我們不再使用雙重嵌套去比較每兩個元素的值，而只是不斷比較數(shù)組每前后兩個數(shù)值，讓大的那個數(shù)不斷“冒”到數(shù)組的最后，然后縮小尾邊界的范圍，并且增加一個標志位，表示這一趟是否發(fā)生了交換，如果沒有那么證明該數(shù)組已經(jīng)有序則完成了排序了：
/**
* 改進的冒泡排序
*
* @param nums 待排序的數(shù)組
*/publicvoidbubbleSort2(int[] nums) {// 正確性判斷if(null == nums || nums.length<=1) {return; }// 使用一個數(shù)來記錄尾邊界intlength= nums.length; boolean flag =true;// 發(fā)生了交換就為true, 沒發(fā)生就為false，第一次判斷時必須標志位true。while(flag) { flag =false;// 每次開始排序前，都設(shè)置flag為未排序過for(inti =1; i nums[i]) {// 前面的數(shù)字大于后面的數(shù)字就交換inttemp; temp = nums[i -1]; nums[i -1] = nums[i]; nums[i] = temp;// 表示交換過數(shù)據(jù);flag =true; } }length--;// 減小一次排序的尾邊界}}
同樣的記得寫單元測試函數(shù)；
冒泡排序進一步優(yōu)化
順著這個思路，我們進一步想象一個場景：現(xiàn)在有一個包含 1000 個數(shù)的數(shù)組，僅有前面 100 個數(shù)無序，后面的 900 個數(shù)都比前面的 100 個數(shù)更大并且已經(jīng)排好序，那么上面優(yōu)化的方法又會造成一定的時間浪費，所以我們進一步增加一個變量記錄最后發(fā)生交換的元素的位置，也就是排序的尾邊界了：
/**
* 冒泡算法最優(yōu)解
*
* @param nums 待排序的數(shù)組
*/publicstaticvoidbubbleSort3(int[] nums){intj, k;intflag = nums.length;// flag來記錄最后交換的位置，也就是排序的尾邊界while(flag >0) {// 排序未結(jié)束標志k = flag;// k 來記錄遍歷的尾邊界flag =0;for(j =1; j < k; j++) {if(nums[j -1] > nums[j]) {// 前面的數(shù)字大于后面的數(shù)字就交換// 交換a[j-1]和a[j]inttemp; temp = nums[j -1]; nums[j -1] = nums[j]; nums[j] = temp;// 表示交換過數(shù)據(jù);flag = j;// 記錄最新的尾邊界.} } }}
這應(yīng)該是最優(yōu)的冒泡排序了，同時也別忘記了最后要寫測試單元用例代碼；
快速排序
快排也是一種很經(jīng)典的算法，它使用了一種分治的思想，基本思想是：通過一趟排序?qū)⒋判虻臄?shù)組分成兩個部分，其中一部分記錄的是比關(guān)鍵字更小的，另一部分是比關(guān)鍵字更大的，然后再分別對著兩部分繼續(xù)進行排序，直到整個序列有序；
基礎(chǔ)實現(xiàn)
非常經(jīng)典的代碼，直接上吧：
publicstaticvoidquickSort(int[] arr){ qsort(arr,0, arr.length -1);}privatestaticvoidqsort(int[] arr,intlow,inthigh){if(low < high) {intpivot = partition(arr, low, high);// 將數(shù)組分為兩部分qsort(arr, low, pivot -1);// 遞歸排序左子數(shù)組qsort(arr, pivot +1, high);// 遞歸排序右子數(shù)組}}privatestaticintpartition(int[] arr,intlow,inthigh){intpivot = arr[low];// 樞軸記錄while(low < high) {while(low < high && arr[high] >= pivot) --high; arr[low] = arr[high];// 交換比樞軸小的記錄到左端while(low < high && arr[low] <= pivot) ++low; arr[high] = arr[low];// 交換比樞軸小的記錄到右端}// 掃描完成，樞軸到位arr[low] = pivot;// 返回的是樞軸的位置returnlow;}
當(dāng)然，在手撕的時候需要注意函數(shù)上的 Java Doc 格式的注釋，這里省略掉是為了節(jié)省篇幅，另外別忘了測試單元用例代碼；
上面的代碼也很容易理解，其實就是一個“填坑”的過程，第一個“坑”挖在每次排序的第一個位置arr[low]，從序列后面往前找第一個比pivot小的數(shù)來把這個“坑”填上，這時候的“坑”就變成了當(dāng)前的arr[high]，然后再從序列前面往后用第一個比pivot大的數(shù)把剛才的“坑”填上，如此往復(fù)，始終有一個“坑”需要我們填上，直到最后一個“坑”出現(xiàn)，這個“坑”使用一開始的pivot填上就可以了，而這個“坑”的位置也就是pivot該填上的正確位置，我們再把這個位置返回，就可以把當(dāng)前序列分成兩個部分再依次這樣操作最終就達到排序的目的了，不得不說這樣的思想挺神奇的；
算法優(yōu)化
上面這個快速排序算法可以說是最基本的快速排序，因為它并沒有考慮任何輸入數(shù)據(jù)。但是，我們很容易發(fā)現(xiàn)這個算法的缺陷：這就是在我們輸入數(shù)據(jù)基本有序甚至完全有序的時候，這算法退化為冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我們的代碼實現(xiàn)中，每次只從數(shù)組第一個開始取。如果我們采用“三者取中”，即 arr[low], arr[high], arr[(low+high)/2] 三者的中值作為樞軸記錄，則可以大大提高快速排序在最壞情況下的性能。但是，我們?nèi)匀粺o法將它在數(shù)組有序情形下的性能提高到O(n)。還有一些方法可以不同程度地提高快速排序在最壞情況下的時間性能。
此外，快速排序需要一個遞歸棧，通常情況下這個棧不會很深，為log(n)級別。但是，如果每次劃分的兩個數(shù)組長度嚴重失衡，則為最壞情況，棧的深度將增加到O(n)。此時，由棧空間帶來的空間復(fù)雜度不可忽略。如果加上額外變量的開銷，這里甚至可能達到恐怖的O(n^2)空間復(fù)雜度。所以，快速排序的最差空間復(fù)雜度不是一個定值，甚至可能不在一個級別。
為了解決這個問題，我們可以在每次劃分后比較兩端的長度，并先對短的序列進行排序（目的是先結(jié)束這些棧以釋放空間），可以將最大深度降回到O(㏒n)級別。
關(guān)于優(yōu)化的話，了解一個大概的思路就可以了，那在這里稍微總結(jié)一下：
①三數(shù)取中作為樞軸記錄；
②當(dāng)待排序序列的長度分割到一定大小之后，使用插入排序；
③在一次分割結(jié)束后，可以把與pivot相等的元素聚在一起，繼續(xù)下次分割時，不用再對與pivot相等的元素分割；
④優(yōu)化遞歸操作；
參考文章：http://blog.51cto.com/flyingcat2013/1281614
想要了解的更多的童鞋可以戳這里：https://blog.csdn.net/insistGoGo/article/details/7785038
Part 3.二叉樹相關(guān)算法
二叉樹也是一個容易提及的概念和寫算法的問題，特別是它的幾種遞歸遍歷和非遞歸遍歷，都是基礎(chǔ)且?？嫉狞c，那在這里就稍微整理整理吧...
二叉樹的幾種遞歸遍歷
前序、中序、后序遍歷都是非常基礎(chǔ)且容易的遍歷方法，重點還是在后面的中序和后續(xù)的非遞歸遍歷上，當(dāng)然還有層序遍歷，所以這里不多說，直接給代碼；
前序遍歷遞歸實現(xiàn)
publicvoidpreOrderTraverse1(TreeNode root){if(root !=null) { System.out.print(root.val +" "); preOrderTraverse1(root.left); preOrderTraverse1(root.right); }}
中序遍歷遞歸實現(xiàn)
publicvoidinOrderTraverse1(TreeNode root){if(root !=null) { preOrderTraverse1(root.left); System.out.print(root.val +" "); preOrderTraverse1(root.right); }}
后序遍歷遞歸實現(xiàn)
publicvoidpostOrderTraverse1(TreeNode root){if(root !=null) { preOrderTraverse1(root.left); preOrderTraverse1(root.right); System.out.print(root.val +" "); }}
前面三種遍歷，也就是輸出結(jié)點數(shù)據(jù)的位置不同而已，所以很容易，但是如果手寫，建議問清楚面試官要求，是在遍歷時直接輸出還是需要函數(shù)返回一個List集合，然后注意寫測試用例代碼！
二叉樹的幾種非遞歸遍歷
★★層序遍歷★★
層序遍歷我們只需要增加使用一個隊列即可，看代碼很容易理解：
public void levelTraverse(TreeNode root) { if (root == null) { return; } LinkedList<TreeNode>queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNodenode= queue.poll(); System.out.print(node.val+" "); if (node.left!= null) { queue.offer(node.left); } if (node.right!= null) { queue.offer(node.right); } }}
前序遍歷非遞歸實現(xiàn)
publicvoidpreOrderTraverse2(TreeNode root) {if(root ==null) {return; } LinkedListstack=newLinkedList<>(); TreeNode pNode = root;while(pNode !=null|| !stack.isEmpty()) {if(pNode !=null) { System.out.print(pNode.val +" ");stack.push(pNode); pNode = pNode.left; }else{//pNode == null && !stack.isEmpty()TreeNode node =stack.pop(); pNode = node.right; } }}
★★中序遍歷非遞歸實現(xiàn)★★
/**
* 非遞歸中序遍歷二叉樹
*
* @param root 二叉樹根節(jié)點
* @return 中序遍歷結(jié)果集
*/publicList inorderTraversal(TreeNode root) {Listlist=newArrayList<>(); ArrayDequestack=newArrayDeque<>();while(root !=null|| !stack.isEmpty()) {while(root !=null) {stack.addFirst(root); root = root.left; } root =stack.removeFirst();list.add(root.val); root = root.right; }returnlist;}
★★后續(xù)遍歷非遞歸實現(xiàn)★★
/**
* 二叉樹的后序遍歷
*
* @param root 二叉樹根節(jié)點
* @return 后序遍歷結(jié)果集
*/publicList postorderTraversal(TreeNode root) {Listlist=newArrayList<>(); Dequestack=newArrayDeque<>(); TreeNode pre =null;while(!stack.isEmpty() || root !=null) {while(root !=null) {stack.push(root); root = root.left; } root =stack.peek();// i ：判斷如果右子樹不為空且不為if(root.right !=null&& root.right != pre) { root = root.right; }else{ root =stack.pop();list.add(root.val); pre = root; root =null; } }returnlist;}
如果比較難以理解的話，可以自己嘗試著跟跟 Debug 然后看看過程；
二叉樹相關(guān)其他算法題
另外的話還有一些比較常見的關(guān)于樹的算法，在文章的末尾，這里就不再贅述了：
如果想學(xué)習(xí)Java工程化、高性能及分布式、深入淺出。微服務(wù)、Spring，MyBatis，Netty源碼分析的朋友可以加我的Java高級交流：854630135，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費分享給大家。
Part 4.其他重要算法
除了上面 3 Part 比較重要的點之外，還有一些其他的算法也是經(jīng)?？嫉降?，下面我們來說；
1.反轉(zhuǎn)鏈表
這是一道很經(jīng)典的題，不僅考你對鏈表的理解，而且還有一些細節(jié)（例如正確性判斷/ 測試用例）需要你從代碼層面去展現(xiàn)，下面我們給出兩段代碼，讀者可以自行去比較，我只是提供一個思路；
思路一：使用一個 Node 不斷鏈接
這是最經(jīng)典的算法，也是需要我們牢牢掌握的方法，最重要的還是理解 while() 循環(huán)中的過程：
publicListNode reverseList(ListNode head) {// 正確性判斷if(null== head ||null== head.next) {returnhead; } ListNode pre =null;while(null!= head) { ListNode temp = head; head = head.next; temp.next= pre; pre = temp; }returnpre;}
思路二：反轉(zhuǎn)元素值然后重新賦給 Node
這是一個很簡單的思路，比上個思路要多遍歷一遍鏈表，但是好處是簡單，思路清晰，實現(xiàn)起來容易，emm，像這一類問題我覺得另一個比較重要的就是舉一反三的能力吧，在這里我只提供兩個思路，其實還有很多種實現(xiàn)方法，當(dāng)然也別忘了細節(jié)的東西~
publicListNode reverseList(ListNode head) {// 1.正確性判斷if(null== head ||null== head.next) {returnhead; }// 2.遍歷鏈表head并將結(jié)果保存在List集合中Listlist=newLinkedList(); ListNode tempNode = head;while(null!= tempNode) {list.insert(tempNode.val); tempNode = tempNode.next; }// end while：遍歷完了鏈表并將結(jié)果保存在了List集合中// 3.反轉(zhuǎn)集合，并將值依次復(fù)制給鏈表Collections.reverse(list); tempNode = head;while(null!= tempNode) { tempNode.val =list.remove(0); tempNode = tempNode.next; }returnhead;}
2.合并兩個有序鏈表
問題描述：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的；
同樣的經(jīng)典算法，需要掌握：
publicListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 ==null) {returnl2; }if(l2 ==null) {returnl1; } ListNode head =null;if(l1.val< l2.val) { head = l1; head.next = mergeTwoLists(l1.next, l2); }else{ head = l2; head.next = mergeTwoLists(l1, l2.next); }returnhead;}
這道題也是 LeetCode 上的一道題，我當(dāng)時的做法是下面這樣的，雖然看起來代碼量多了不少而且看起來蠢蠢的..但是經(jīng)過 LeetCode 測試，甚至比上面的實現(xiàn)要快上那么 2ms，特別提醒：下面的代碼只是用作一個思路的參考，著重掌握上面的代碼：
publicListNode mergeTwoLists(ListNode l1, ListNode l2) {// 定義一個虛擬頭結(jié)點方便遍歷ListNode dummyHead =newListNode(-1); dummyHead.next= l1; ListNode pre = dummyHead;// 遍歷l1鏈表intlen1 =0;while(null!= pre.next) { len1++; pre = pre.next; }int[] nums1 =newint[len1];// 保存l1鏈表的數(shù)據(jù)pre = dummyHead;for(inti =0; i < len1; i++) { nums1[i] = pre.next.val; pre = pre.next; }// 遍歷l2鏈表intlen2 =0; dummyHead.next= l2; pre = dummyHead;while(null!= pre.next) { len2++; pre = pre.next; }int[] nums2 =newint[len2];// 保存l2鏈表的數(shù)據(jù)pre = dummyHead;for(inti =0; i < len2; i++) { nums2[i] = pre.next.val; pre = pre.next; }int[] nums =newint[len1 + len2];// 將兩個鏈表的數(shù)據(jù)整合并排序System.arraycopy(nums1,0, nums,0, len1); System.arraycopy(nums2,0, nums, len1, len2); Arrays.sort(nums);// 拼接一個鏈表ListNode dummy =newListNode(-1); pre = dummy;for(inti =0; i < nums.length; i++) { ListNode node =newListNode(nums[i]); pre.next= node; pre = pre.next; }returndummy.next;}
3.兩個鏈表的第一個公共結(jié)點
題目描述：找出兩個鏈表的第一個公共結(jié)點；
/** * 求兩個鏈表中第一個公共結(jié)點 * *@parampHead1 鏈表1頭結(jié)點 *@parampHead2 鏈表2頭結(jié)點 *@return鏈表第一個公共結(jié)點 */publicListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {// 1.正確性判斷if(null== pHead1 ||null== pHead2) {returnnull; }// 2.遍歷鏈表1把所有結(jié)點保存在列表中中Vector nodeList1 = new Vector<>();while(null!= pHead1) { nodeList1.add(pHead1); pHead1 = pHead1.next;// 判斷是否成環(huán)，成環(huán)則退出循環(huán)if(nodeList1.contains(pHead1)) {break; } }// end while：鏈表1中的所有結(jié)點都存入了nodeList1中// 3.遍歷鏈表2比較列表中的數(shù)據(jù)Vector nodeList2 = new Vector<>();while(null!= pHead2) {// 先判斷nodeList1中是否存在相同結(jié)點，存在則返回if(nodeList1.contains(pHead2)) {returnpHead2; }// 如果不存在則繼續(xù)遍歷，并判斷是否成環(huán)nodeList2.add(pHead2); pHead2 = pHead2.next;if(nodeList2.contains(pHead2)) {break; } }// end while：遍歷完了鏈表2并將所有結(jié)點保存在了nodeList2中// 如果遍歷完鏈表2則返回nullreturnnull;}
需要注意的細節(jié)是：①正確性判斷；②判斷鏈表是否自己成環(huán)；③注釋；④注意要自己寫測試用例啊...
另外還有一些類似的題目像是：①鏈表入環(huán)結(jié)點；②鏈表倒數(shù)第k個結(jié)點；之類的都是需要掌握的...
4.二分查找算法
二分查找也是一類比較常考的題目，其實代碼也比較容易理解，直接上吧，再再再提醒一下：注意正確性判斷還有測試用例...
普通實現(xiàn)
/** * 二分查找普通實現(xiàn)。 * * @param srcArray 有序數(shù)組 * @param key 查找元素 * @return 不存在返回-1*/publicstaticintbinSearch(intsrcArray[],intkey) {intmid;intstart =0;intend= srcArray.length -1;while(start <=end) {mid= (end- start) /2+ start;if(key < srcArray[mid]) {end=mid-1; }elseif(key > srcArray[mid]) { start =mid+1; }else{ returnmid; } } return-1;}
遞歸實現(xiàn)
/** * 二分查找遞歸實現(xiàn)。 * *@paramsrcArray 有序數(shù)組 *@paramstart 數(shù)組低地址下標 *@paramend 數(shù)組高地址下標 *@paramkey 查找元素 *@return查找元素不存在返回-1 */publicstaticintbinSearch(intsrcArray[],intstart,intend,intkey){intmid = (end - start) /2+ start;if(srcArray[mid] == key) {returnmid; }if(start >= end) {return-1; }elseif(key > srcArray[mid]){returnbinSearch(srcArray, mid +1, end, key); }elseif(key < srcArray[mid]){returnbinSearch(srcArray, start, mid -1, key); }return-1;}
5.斐波那契數(shù)列
這也是一道很經(jīng)典的題，通常是要要求 N 值的范圍的，常規(guī)寫法應(yīng)該很簡單，所以需要掌握的是優(yōu)化之后的算法：
publicintFibonacci(intn){// 正確性判斷if(0== n ||1== n) {returnn; }intnums1 =0, nums2 =1;intres =0;for(inti =2; i <= n; i++) { res = nums1 + nums2; nums1 = nums2; nums2 = res; }returnres;}
還是注意正確性判斷然后寫測試用例...
手撕代碼總結(jié)
如果用手寫代碼的話，確實是個挺麻煩的事兒，首先需要對代碼有相當(dāng)?shù)氖煜こ潭龋缓笃浯蔚脑捒疾斓亩际且恍┘毠?jié)的東西，例如：
編碼規(guī)范：包括一些命名的規(guī)范/ 注釋的規(guī)范等等；
縮進：這個我自己倒是挺在意的..關(guān)于這個可以去參考參考阿里出的那個規(guī)范手冊；
注釋：如果命名規(guī)范做得好的話其實是可以達到代碼即注釋的，但是仍然有一些需要標注的地方例如函數(shù)頭之類的，最好還是做好注釋；
代碼的完整性：我覺得這個包括對于錯誤的處理/ 正確性判斷這樣一類的東西；
測試用例：每個函數(shù)都需要一定的測試來保證其正確性，所以這個還是挺有必要的，特別是一些邊界情況，null 值判斷之類的；
想好再下筆：這一點其實也蠻重要的，不管是在紙上還是在我們平時的編程中，思路永遠都是更重要的；
如果想學(xué)習(xí)Java工程化、高性能及分布式、深入淺出。微服務(wù)、Spring，MyBatis，Netty源碼分析的朋友可以加我的Java高級交流：854630135，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費分享給大家。
說來說去還是關(guān)于代碼的事，我覺得還是理清思路最重要，所以我們需要在一遍一遍熟悉代碼的過程中，熟知這些代碼的思路，只有搞清楚這些代碼背后的原理了，我們才能正確且快速的寫出我們心中想要的代碼，而不是簡單的去背誦，這樣是沒有很大效果的，以上...
