java实现快速排序（代码实例）

快速排序又称分区交换排序（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 (i<more){             // 1.i位置==arr[right],i++             if (arr[i]==arr[right]){                 i ++;             }             // 2.i位置<arr[right],i位置与小于区域右一个位置交换             else if (arr[i]<arr[right]){                 SortUtil.swap(arr,++lessEqual,i++);             }             // 3.i位置>arr[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};     }   }