概述
快速排序是由東尼・霍爾所發展的一種排序算法。在平均狀況下，排序n 個項目要Ο(nlogn)次比較。事實上，快速排序通常明顯比其他Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來，並且在大部分真實世界的數據，可以決定設計的選擇，減少所需時間的二次方項之可能性。
快速排序，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然後分別對這兩部分記錄繼續進行排序,以達到整個序列有序的目的。
形像圖示：
步驟
選擇一個基準元素，通常選擇第一個元素或者最後一個元素通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值均比基準值大此時基準元素在其排好序後的正確位置然後分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。
實例
原始數據：
3 5 2 6 2
選擇3 作為基準
第一輪
從右往左找比3小的，2符合，將2和3對調2 5 2 6 3對調一次，查找的方向反向，從左向右找比3大的，5符合，對調2 3 2 6 5再從右往左找比3小的，2符合，對調2 2 3 6 5一輪結束
第二輪
對[2 2] 採用同上的方式進行，得到2 2 3 6 5
第三輪
對[6 5] 採用同上的方式進行，得到2 2 3 5 6
最終結果
2 2 3 5 6
代碼實現(Java)
package com.coder4j.main.arithmetic.sorting;public class Quick { private static int mark = 0; /** * 輔助交換方法* * @param array * @param a * @param b */ private static void swap(int[] array, int a, int b) { if (a != b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; // 找到符合的，對調System.out.println("對調" + array[a] + "與" + array[b] + ",得到"); for (int i : array) { System.out.print(i + " "); } System.out.println(); } } /** * 新一輪分隔* * @param array * @param low * @param high * @return */ private static int partition(int array[], int low, int high) { int base = array[low]; mark++; System.out.println("正在進行第" + mark + "輪分隔，區域：" + low + "-" + high); while (low < high) { while (low < high && array[high] >= base) { high--; System.out.println("從右往左找比" + base + "小的，指針變動：" + low + "-" + high); } swap(array, low, high); while (low < high && array[low] <= base) { low++; System.out.println("從左往右找比" + base + "大的，指針變動：" + low + "-" + high); } swap(array, low, high); } return low; } /** * 對數組進行快速排序，遞歸調用* * @param array * @param low * @param heigh * @return */ private static int[] quickSort(int[] array, int low, int heigh) { if (low < heigh) { int division = partition(array, low, heigh); quickSort(array, low, division - 1); quickSort(array, division + 1, heigh); } return array; } /** * 快排序* * @param array * @return */ public static int[] sort(int[] array) { return quickSort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("最終結果"); for (int i : sorted) { System.out.print(i + " "); } }}測試輸出結果：
全選複製放進筆記正在進行第1輪分隔，區域：0-4對調2與3,得到2 5 2 6 3 從左往右找比3大的，指針變動：1-4對調3與5,得到2 3 2 6 5 從右往左找比3小的，指針變動：1-3從右往左找比3小的，指針變動：1-2對調2與3,得到2 2 3 6 5 從左往右找比3大的，指針變動：2-2正在進行第2輪分隔，區域：0-1從右往左找比2小的，指針變動：0-0正在進行第3輪分隔，區域：3-4對調5與6,得到2 2 3 5 6 從左往右找比6大的，指針變動：4-4最終結果2 2 3 5 6
經測試，與實例中結果一致。