/**
* 測(cè)試隨機(jī)快速排序
*/
public class TestRandomQuickSort {
? ?public static int partition(int[] arr,int low,int high){
? ? ? ?//partition擋板 在low到high范圍內(nèi)設(shè)置一個(gè)擋板/支點(diǎn) 小于支點(diǎn)元素的數(shù)放在s1區(qū) 大于支點(diǎn)元素的數(shù)放在s2區(qū)
? ? ? ?int ranCho = (int)((high-low+1)*Math.random()+low);
? ? ? ?//隨機(jī)選low到high之間一位作為支點(diǎn)
? ? ? ?int swap ;
? ? ? ?swap = arr[low];
? ? ? ?arr[low] = arr[ranCho];
? ? ? ?arr[ranCho] = swap;
? ? ? ?//把支點(diǎn)元素置于首位
? ? ? ?int pivot =arr[low];
? ? ? ?//pivot支點(diǎn) 小于支點(diǎn)放在s1區(qū) 大于支點(diǎn)放在s2區(qū)
? ? ? ?int s1r = low;
? ? ? ?//初期s1區(qū)s2區(qū)內(nèi)為空 要將支點(diǎn)右側(cè)所有元素逐個(gè)和支點(diǎn)比較 分裝進(jìn)s1 s2內(nèi)
? ? ? ?for (int s2r = low+1;s2r<=high;s2r++){
? ? ? ? ? ?//先將s2的右端擴(kuò)張1位 比較這一位和支點(diǎn) 如果比支點(diǎn)大則屬于s2不用動(dòng) 因?yàn)橐呀?jīng)被s2r包住了
? ? ? ? ? ?if(arr[s2r]<pivot){
? ? ? ? ? ? ? ?// 比支點(diǎn)小則屬于s1 s1右端擴(kuò)張1位(原屬于s2)和正在比的那一位(應(yīng)屬于s1)交換
? ? ? ? ? ? ? ?s1r++;
? ? ? ? ? ? ? ?swap = arr[s1r];
? ? ? ? ? ? ? ?arr[s1r] = arr[s2r];
? ? ? ? ? ? ? ?arr[s2r] = swap;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?//循環(huán)結(jié)束后 low至high內(nèi)從左開始依次為 支點(diǎn)pivot s1區(qū)（low+1至s1r） s2區(qū)（s1r+1至high）
? ? ? ?arr[low] = arr[s1r];
? ? ? ?arr[s1r] = pivot;
? ? ? ?//交換 將支點(diǎn)從low換到s1r位置 這樣支點(diǎn)左側(cè)為s1都比支點(diǎn)小 右側(cè)為s2都比支點(diǎn)大
? ? ? ?return s1r;
? ? ? ?//把支點(diǎn)位置返回
? ?}

? ?public static void rqs(int[] array,int low,int high){
? ? ? ?if (low<high){
? ? ? ? ? ?int pivot = partition(array,low,high);
? ? ? ? ? ?//用支點(diǎn)分出s1 s2 兩個(gè)區(qū)域再往下分
? ? ? ? ? ?rqs(array,low,pivot-1);
? ? ? ? ? ?//s1 這里如果s1區(qū)為空 pivot=low 即rqs(array,low,low-1) 如果上面的if(low!=high)就會(huì)出問題 low-1!=low執(zhí)行語句然后報(bào)錯(cuò) 錯(cuò)誤總結(jié)：!=容易遺漏一些例外情況 少用
? ? ? ? ? ?rqs(array,pivot+1,high);
? ? ? ? ? ?//s2
? ? ? ?}
? ? ? ?//low==high 即此區(qū)域內(nèi)只有一個(gè)元素時(shí) void此區(qū)域排序完成
? ?}


? ?public static void rqs(int[] array){
? ? ? ?//重載rqs 用于對(duì)整個(gè)數(shù)組進(jìn)行排序 調(diào)用時(shí)不需要輸入low=0和high=.length-1
? ? ? ?if (array.length>1){
? ? ? ? ? ?int pivot = partition(array,0,array.length-1);
? ? ? ? ? ?rqs(array,0,pivot-1);
? ? ? ? ? ?rqs(array,pivot+1,array.length-1);
? ? ? ?}
? ?}

? ?public static void main(String[] args) {
? ? ? ?int[] arr = {87,45,32,1,65,98,45,321,5,1,3,5,84,15};
? ? ? ?rqs(arr);
? ? ? ?System.out.println(Arrays.toString(arr));
????????//結(jié)果[1, 1, 3, 5, 5, 15, 32, 45, 45, 65, 84, 87, 98, 321]

? ?}
}