快速排序又稱為分區交換排序（partition-exchange sort），簡稱快排，一種排序演算法。
（推薦教學：java學習網站）
在平均狀況下，排序n個項目要O(nlog n)（大O符號）次比較。在最壞狀況下則需要 O(n^2)次比較，但這種狀況並不常見。事實上，快速排序O(nlog n)通常明顯比其他演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地達成。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分成較小和較大的2個子序列，然後遞歸地排序兩個子序列。
步驟為：
挑選基準值：從數列中挑出一個元素，稱為「基準」（pivot）。
分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成。
遞歸排序子序列：遞歸地將小於基準值元素的子序列和大於基準值元素的子序列排序。
遞歸到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序。
（影片教學推薦：java學習）
選取基準有數種具體方法，此選取方法對排序的時間效能有決定性影響。
程式碼實作：
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，时间复杂度O（n²），找出以arr[right]为界的中间位置，小于等于的放左边，大于等于的放右边 * 分为左右2个区域，每个区域重复上面的步骤，直到最后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]作为中间值，最差情况时间复杂度O（n²），平均时间复杂度为 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,当前位置小于等于标记值，当前位置不动，标记右移 if (arr[index] <= arr[right]) { lessEqual++; // 扩大小于等于区域 SortUtil.swap(arr, index, lessEqual); } index++; } // 右边界位置和大于区域的起始位置交换 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 (iarr[right],i位置与大于区域左一个位置交换，i不动 else if(arr[i]>arr[right]){ SortUtil.swap(arr,i,--more); } } SortUtil.swap(arr,right,more); return new int[]{lessEqual+1,more}; } }
以上是java實作快速排序（程式碼實例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
