快速排序又稱分區(qū)交換排序（partition-exchange sort），簡稱快排，一種排序算法。

（推薦教程：java學(xué)習(xí)網(wǎng)站）

在平均狀況下，排序n個項(xiàng)目要O(nlog n)（大O符號）次比較。在最壞狀況下則需要 O(n^2)次比較，但這種狀況并不常見。事實(shí)上，快速排序O(nlog n)通常明顯比其他算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地達(dá)成。

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然后遞歸地排序兩個子序列。

步驟為：

• 挑選基準(zhǔn)值：從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”（pivot）。

• 分割：重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（與基準(zhǔn)值相等的數(shù)可以到任何一邊）。在這個分割結(jié)束之后，對基準(zhǔn)值的排序就已經(jīng)完成。

• 遞歸排序子序列：遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序。

遞歸到最底部的判斷條件是數(shù)列的大小是零或一，此時該數(shù)列顯然已經(jīng)有序。

（視頻教程推薦：java學(xué)習(xí)）

選取基準(zhǔn)值有數(shù)種具體方法，此選取方法對排序的時間性能有決定性影響。

代碼實(shí)現(xiàn)：

 public class QuickSort {     public static void main(String[] args) {         int[] arr = SortUtil.randomArr(6);         SortUtil.printArr(arr); //        sort(arr,0,arr.length-1);         sort1(arr,0,arr.length-1); //        int[] arr1= netherlands(arr,0,arr.length-1); //        SortUtil.printArr(arr1);         SortUtil.printArr(arr);     }       /**      * 快排1.0，時間復(fù)雜度O（n2），找出以arr[right]為界的中間位置，小于等于的放左邊，大于等于的放右邊      * 分為左右2個區(qū)域，每個區(qū)域重復(fù)上面的步驟，直到最后left=right      * @param arr      * @param left      * @param right      */     public static void sort(int[] arr,int left,int right){         if(left>=right){return;}         int mid = partition(arr,left,right);         sort(arr,left,mid-1);         sort(arr,mid+1,right);     }       /**      * 快排2.0 以arr[right]作為中間值，最差情況時間復(fù)雜度O（n2），平均時間復(fù)雜度為 O(n logn)       * @param arr      * @param left      * @param right      */     public static void sort1(int[] arr,int left,int right){         if(left>=right){return;}         int[] mid = netherlands(arr,left,right);         sort1(arr,left,mid[0]-1);         sort1(arr,mid[1]+1,right);     }       private static int partition(int[] arr, int left, int right) {         if (left > right) {             return -1;         }         if (left == right) {             return left;         }         int lessEqual = left - 1;         int index = left;           while (index < right) {             // 情況1,當(dāng)前位置小于等于標(biāo)記值，當(dāng)前位置不動，標(biāo)記右移             if (arr[index] <= arr[right]) {                 lessEqual++;                 // 擴(kuò)大小于等于區(qū)域                 SortUtil.swap(arr, index, lessEqual);             }             index++;         }         // 右邊界位置和大于區(qū)域的起始位置交換         SortUtil.swap(arr, ++lessEqual, right);         return lessEqual;     }       /**      * 荷蘭國旗問題      * @param arr      * @param left      * @param right      * @return      */     private static int[]  netherlands(int[] arr,int left,int right){         if(left>right){             return new int[]{-1,-1};         }         if(left==right){             return new int[]{left,right};         }         int lessEqual = left-1;         int i = left;         int more = right;         while (i<more){             // 1.i位置==arr[right],i++             if (arr[i]==arr[right]){                 i ++;             }             // 2.i位置<arr[right],i位置與小于區(qū)域右一個位置交換             else if (arr[i]<arr[right]){                 SortUtil.swap(arr,++lessEqual,i++);             }             // 3.i位置>arr[right],i位置與大于區(qū)域左一個位置交換，i不動             else if(arr[i]>arr[right]){                 SortUtil.swap(arr,i,--more);             }         }         SortUtil.swap(arr,right,more);         return new int[]{lessEqual+1,more};     }   }