最近想系統整理一下資料庫的索引系列，然後就牽扯到了二分查找，二分查找的前提需要排序。
排序工作中我們用的很多，不過很少去關心實現；面試中，排序的出場率非常高，以此來驗證大家是否懂得「算法」。
無論如何，排序算法都值得每一位極客去學習和掌握。
快速排序 Quicksort快速排序（有時稱為分區交換排序）是一種有效的排序算法。
由英國計算機科學家Tony Hoare於1959年開發[1]，並於1961年發表[2]，它仍然是一種常用的排序算法。如果實施得當，它可以比主要競爭者（合併排序和堆排序）快兩倍或三倍。
Quicksort是一種分而治之的算法。它通過從數組中選擇一個「pivot」元素並將其他元素劃分為兩個子數組（根據它們是否小於或大於基準數）來工作。然後將子數組遞歸排序。這可以就地完成，需要少量額外的內存來執行排序。
快速排序是一種比較排序，這意味著它可以對定義了「小於」關係的任何類型的項目進行排序。
快速排序的有效實現不是穩定的排序，這意味著不會保留相等排序項的相對順序。
快速排序的數學分析表明，平均而言，該算法採用O（n log n）比較來對n個項目進行排序。
在最壞的情況下，它會進行O（n^2）比較，儘管這種行為很少見。
算法流程Quicksort是一種分而治之的算法。
首先將輸入數組分為兩個較小的子數組：低元素和高元素。
然後，它將對子數組進行遞歸排序。就地Quicksort的步驟是：
從數組中選擇一個稱為基準數的元素。
分區：對數組重新排序，以使所有值小於基準數的元素都位於基準數之前，而所有值大於基準數的元素都位於基準數之後（相等的值可以任意選擇）。分割之後，基準數處於其最終位置。這稱為分區操作。
將上述步驟遞歸地應用於值較小的元素子數組，並分別應用於值較大的元素的子數組。
遞歸的基本情況是大小為零或一的數組，這些數組按定義順序排列，因此它們不需要排序。
基準數選擇和分區步驟可以通過幾種不同的方式完成。具體實施方案的選擇會極大地影響算法的性能。
例子上面的算法直接說，不免有些抽象。
我們舉一個例子，假如排序 {6 1 2 7 9 3 4 5 10 8}。
這個例子的圖片是參考網上的一篇文章的，畫的生動有趣，便於大家理解。
基準數我們第一步，需要選擇一個基準數，為了簡單，直接選擇第一個數 6 作為比較的基準。
分區這裡實際上是「雙指針」的思想，從兩邊開始比較。
第一次交換先從右往左找一個小於6的數，再從左往右找一個大於6的數，然後交換他們。
輸入圖片說明滿足條件的左邊是 7， 右邊 是 5，執行交換：
輸入圖片說明第二次交換接下來，繼續走。
輸入圖片說明滿足條件的左邊的是 9，右邊的是 4,執行交換：
輸入圖片說明第三次交換然後右邊的右邊的哨兵向左，找到了滿足條件的元素 3（比 6 小）；左邊的向右移動。
發現兩個人已經碰到一起了，說明本次的探測已經結束了。
我們需要把基準數放在交換到這個位置上。
輸入圖片說明交換之後：
輸入圖片說明遞歸然後我們將上面三步的策略，應用於左右兩個數組。
你問我哪兩個數組？
實際上就是根據基準數分割的 2 個 數組：
{3 1 2 5 4 6 9 7 10 8}
根據 6 拆分為：
{3 1 2 5 4} 和 {9 7 10 8}
輸入圖片說明java 代碼實現我們一起來看一下 java 的代碼實現。
核心代碼實現package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/**
* 快速排序
* @author binbin.hou
* @since 0.0.2
*/
public class QuickSort extends AbstractSort {
private static final Log log = LogFactory.getLog(QuickSort.class);
@Override
protected void doSort(List<?> original) {
this.quickSort(original, 0, original.size()-1);
}
/**
* 快速排序
* @param original 原始列表
* @param left 左邊
* @param right 右邊
* @since 0.0.2
*/
@SuppressWarnings("all")
private void quickSort(final List<?> original,
final int left,
final int right) {
if(left > right) {
return;
}
// 左右兩邊的哨兵指針
int leftIx = left;
int rightIx = right;
// 比較基準，直接取最左邊的元素
Comparable basic = (Comparable) original.get(leftIx);
while (leftIx < rightIx) {
// 右邊，從右向左移動找到第一個小於基準的數
while (leftIx < rightIx && InnerSortUtil.gte(original, rightIx, basic)) {
rightIx--;
}
// 左邊，從左向右移動找到第一個大於基準的數
while (leftIx < rightIx && InnerSortUtil.lte(original, leftIx, basic)) {
leftIx++;
}
// 判斷是否滿足交換的條件
if(leftIx < rightIx) {
InnerSortUtil.swap(original, leftIx, rightIx);
}
}
// 更新基準的信息（i == j）
// 將最左邊位置的元素，和此時的哨兵位置交換
InnerSortUtil.swap(original, left, leftIx);
// 執行遞歸調用
quickSort(original, left, leftIx-1);
quickSort(original, leftIx+1, right);
}
}
為了便於後期復用，我們把交換和比較做了抽成單獨的方法：
package com.github.houbb.sort.core.util;
import java.util.List;
/**
* 內部比較輔助類，可能會變更。
* 外部不要使用
* @author binbin.hou
* @since 0.0.2
*/
public final class InnerSortUtil {
/**
* 執行數據的交換
* @param original 原始
* @param i 第一個
* @param j 第二個
* @since 0.0.1
*/
@SuppressWarnings("unchecked")
public static void swap(List original,
int i, int j) {
Object temp = original.get(i);
original.set(i, original.get(j));
original.set(j, temp);
}
/**
* 是否大於等於元素
* @param original 原始
* @param i 索引
* @param target 指定元素
* @since 0.0.2
*/
@SuppressWarnings("all")
public static boolean gte(List original, int i, Comparable target) {
Comparable comparable = (Comparable) original.get(i);
return comparable.compareTo(target) >= 0;
}
/**
* 是否小於等於元素
* @param original 原始
* @param i 索引
* @param target 指定元素
* @since 0.0.2
*/
@SuppressWarnings("all")
public static boolean lte(List original, int i, Comparable target) {
Comparable comparable = (Comparable) original.get(i);
return comparable.compareTo(target) <= 0;
}
}
為了快速排序便於使用，我們將其封裝為工具類：
/**
* 快速排序
* @param <T> 泛型
* @param list 列表
* @since 0.0.2
*/
public static <T extends Comparable<? super T>> void quick(List<T> list) {
Instances.singleton(QuickSort.class).sort(list);
}
我們就以開始的例子作為測試案例。
List<Integer> list = Arrays.asList(6,1,2,7,9,3,4,5,10,8);
System.out.println("開始排序：" + list);
SortHelper.quick(list);
System.out.println("完成排序：" + list);
為了便於大家閱讀和理解過程，我們在核心的實現代碼中加了一點兒魔法，不，一點兒日誌。
數據交換時// 判斷是否滿足交換的條件
if(leftIx < rightIx) {
InnerSortUtil.swap(original, leftIx, rightIx);
if(log.isDebugEnabled()) {
String info = String.format("l=%s, r=%s, lx=%s, rx=%s, 交換後：%s",
left, right, leftIx, rightIx, original);
log.debug(info);
}
} else {
if(log.isDebugEnabled()) {
String info = String.format("l=%s, r=%s, lx=%s, rx=%s, 無交換",
left, right, leftIx, rightIx);
log.debug(info);
}
}
// 更新基準的信息（i == j）
// 將最左邊位置的元素，和此時的哨兵位置交換
InnerSortUtil.swap(original, left, leftIx);
if(log.isDebugEnabled()) {
String info = String.format("l=%s, lx=%s, 基準數歸位：%s",
left, leftIx, original);
log.debug(info);
}
測試日誌如下：
開始排序：[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
l=0, r=9, lx=3, rx=7, 交換後：[6, 1, 2, 5, 9, 3, 4, 7, 10, 8]
l=0, r=9, lx=4, rx=6, 交換後：[6, 1, 2, 5, 4, 3, 9, 7, 10, 8]
l=0, r=9, lx=5, rx=5, 無交換
l=0, lx=5, 基準數歸位：[3, 1, 2, 5, 4, 6, 9, 7, 10, 8]
l=0, r=4, lx=2, rx=2, 無交換
l=0, lx=2, 基準數歸位：[2, 1, 3, 5, 4, 6, 9, 7, 10, 8]
l=0, r=1, lx=1, rx=1, 無交換
l=0, lx=1, 基準數歸位：[1, 2, 3, 5, 4, 6, 9, 7, 10, 8]
l=0, lx=0, 基準數歸位：[1, 2, 3, 5, 4, 6, 9, 7, 10, 8]
l=3, r=4, lx=4, rx=4, 無交換
l=3, lx=4, 基準數歸位：[1, 2, 3, 4, 5, 6, 9, 7, 10, 8]
l=3, lx=3, 基準數歸位：[1, 2, 3, 4, 5, 6, 9, 7, 10, 8]
l=6, r=9, lx=8, rx=9, 交換後：[1, 2, 3, 4, 5, 6, 9, 7, 8, 10]
l=6, r=9, lx=8, rx=8, 無交換
l=6, lx=8, 基準數歸位：[1, 2, 3, 4, 5, 6, 8, 7, 9, 10]
l=6, r=7, lx=7, rx=7, 無交換
l=6, lx=7, 基準數歸位：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
l=6, lx=6, 基準數歸位：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
l=9, lx=9, 基準數歸位：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
完成排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
這個日誌，再對照一下開始的解釋，聰明的你一定可以理解地更加深入！
開源地址為了便於大家學習，上面的排序已經開源，開源地址：
https://github.com/houbb/sort
歡迎大家 fork/star，鼓勵一下作者~~
小結快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。
每次排序的時候設置一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了。
只能說，分治算法，永遠滴神！
希望本文對你有幫助，如果有其他想法的話，也可以評論區和大家分享哦。
各位極客的點讚收藏轉發，是老馬持續寫作的最大動力！