資訊專欄INFORMATION COLUMN
摘要：分治快速排序以下簡稱快排的核心思想是分治法。第二個元素大于，放于右側第三個元素小于，放于左側以此類推，最后一個元素放置完畢后是這樣的重復。此時從左到右讀出圖中曾作為基準值的元素菱形，我們發現已經排序好了。
分治
快速排序（以下簡稱“快排”）的核心思想是分治法。可以說，分治提供了另一種解決問題的思路。舉個例子來進行說明，抓穩扶好，直接開車了……
舉例現有一個集合{4,8,2,5,7,-1,3}，我們將對它進行從小到大排序：
1.選取第一個元素4作為基準值，后面的元素逐個和這個基準值比較大小
顯然，要么大于，要么小于（ 暫不考慮相等的情況）。
2.按比較大小結果進行安置：大于基準值的元素，置于它的左側；小于基準值的元素，置于它的右側（如果有相等情況，左右隨意）
為好理解，畫出了數軸，將"基準值4"作為中軸線。第二個元素8大于4，放于右側；第三個元素2小于4，放于左側……以此類推，最后一個元素放置完畢后是這樣的
3.“重復”。先拋開右側的big集合，專注于左側集合{2,-1,3}。此時，我們把它當作source，重復第一步的操作。
如此重復下去，直到只剩下一個元素的情況。
此時從左到右讀出圖中曾作為基準值的元素（菱形）——-1,2,3,4，我們發現已經排序好了。最后給出完整的操作示意圖：
每次根據條件劃分成兩部分，劃分后每部分分別治理，即分治。
遞歸上面的例子中，第三步叫“重復”其實并不準確，真正的名字是遞歸。
每個遞歸函數都有兩部分：
基線條件：函數不再調用自己，即退出無限循環調用的條件
遞歸條件：調用自己，且通過一次次調用會逐步靠攏基線條件
拿上一篇文章（【算】選擇排序和二分查找）里聊過的二分查找舉例：
/** * 二分查找，遞歸版 * @param target * @param source * @return */ public static int doFind(int target,List快排source){ if(CollectionUtils.isEmpty(source)){ throw new RuntimeException("集合為空"); } int halfIndex = source.size()/2; int halfElement = source.get(halfIndex).getVal(); if(target==halfElement){ //基線條件：如果目標target和中間數相等，bingo！找到了，返回索引 return source.get(halfIndex).getIndex(); }else if(source.size()==1){ //另一個基線條件：就剩下最后一個元素了，仍然與目標target不符，則返回“目標不存在” throw new RuntimeException("目標不存在"); }else{ //遞歸條件：選取符合條件的那一半集合，遞歸調用自己 if (target < halfElement) { List tempSource = source.subList(0, halfIndex); return doFind(target, tempSource); } else { List tempSource = source.subList(halfIndex, source.size()); return doFind(target, tempSource); } } }
掌握了遞歸和分治思想后，快速排序就只剩下編碼部分了：
