快速排序

??快速排序通過一個(gè)切分元素將數(shù)組分成兩個(gè)子數(shù)組，左子數(shù)組小于等于切分元素，右子數(shù)組大于切分元素，將這兩個(gè)子數(shù)組排序，也就是將整個(gè)數(shù)組排序了。

代碼如下：

public class Sort{public static void quickSort(int []arr){if(arr=null||arr.length<2)return;quickSort(arr,0,arr.length-1);}public static void quickSort(int[]arr,int l,int r){if(l<r){swap(arr, l + (int) (Math.random() * (r - l + 1)), r); //隨機(jī)選取切分值，然后交換到數(shù)組最后一位int []p=partition(arr,l,r);//返回于切分值相等的左右界quickSort(arr,l,p[0]-1);quickSort(arr,p[1]+1,r);}}public static int[]partition(int[]arr,int l,int r){int less=l-1; //小于區(qū)域的右邊界int more=r; //大于區(qū)域的左邊界，初始包含最右端元素，即切分值。while(l<more){if(arr[l]<arr[r]){ //arr[r]作為切分值swap(arr,++less,l++); //如果當(dāng)前元素小于切分值，那么將當(dāng)前元素和小于區(qū)域的右邊第一個(gè)元素和當(dāng)前元素交換，小于區(qū)域向右擴(kuò)大一位，訪問下一個(gè)元素，繼續(xù)進(jìn)行比較。}else if(arr[l]>arr[r]){swap(arr,--more,l);//如果當(dāng)前元素大于切分值，那么將當(dāng)前元素和大于區(qū)域的左邊第一個(gè)元素和當(dāng)前元素交換，大于區(qū)域向左擴(kuò)大一位，繼續(xù)訪問當(dāng)前元素，進(jìn)行比較。}else{ //和切分值相等l++;}}swap(arr,more,r); //將切分值換到中間return new int[]{less+1，more}; //與切分值相等的區(qū)間}public static void swap(int[]arr,int more,int r){arr[more]=arr[more]^arr[r];arr[r]=arr[more]^arr[r];arr[more]=arr[more]^arr[r];} }

??快速排序是原地排序，不需要輔助數(shù)組，但是遞歸調(diào)用需要輔助棧。快速排序最好的情況下是每次都正好將數(shù)組對半分，這樣遞歸調(diào)用次數(shù)才是最小的。這種情況下比較次數(shù)為Cn=2Cn/2+n，復(fù)雜度為O(NlogN)。

??最壞的情況是，第一次從最大的元素或最小的元素切分，第二次從第二大或者第二小的元素切分，如此這般，最壞情況下的比較次數(shù)為N * N /2。為了防止數(shù)組一開始就是有序的，我們在選擇切分值是，進(jìn)行隨機(jī)選取。

??切分函數(shù)partition的應(yīng)用，荷蘭國旗問題，將數(shù)組分成三部分，分別對應(yīng)于小于，等于，大于 切分元素。時(shí)間復(fù)雜度為O(n)。

public int[]partition(int []arr,int l,int r){int less=l-1; //小于區(qū)域的右邊界int more=r; //大于區(qū)域的左邊界，初始包含最右端元素，即切分值。while(l<more){if(arr[l]<arr[r]){ //arr[r]作為切分值swap(arr,++less,l++); //如果當(dāng)前元素小于切分值，那么將當(dāng)前元素和小于區(qū)域的右邊第一個(gè)元素和當(dāng)前元素交換，小于區(qū)域向右擴(kuò)大一位，訪問下一個(gè)元素，繼續(xù)進(jìn)行比較。}else if(arr[l]>arr[r]){swap(arr,--more,l);//如果當(dāng)前元素大于切分值，那么將當(dāng)前元素和大于區(qū)域的左邊第一個(gè)元素和當(dāng)前元素交換，大于區(qū)域向左擴(kuò)大一位，繼續(xù)訪問當(dāng)前元素，進(jìn)行比較。}else{ //和切分值相等l++;}}swap(arr,more,r); //將切分值換到中間return new int[]{less+1，more}; //與切分值相等的區(qū)間 }

轉(zhuǎn)載于:https://www.cnblogs.com/yjxyy/p/11103372.html

總結(jié)

以上是生活随笔為你收集整理的排序---快速排序及其切分函数Partition应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。