本文小編為大家詳細(xì)介紹“java怎么實(shí)現(xiàn)隨機(jī)快速排序”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“java怎么實(shí)現(xiàn)隨機(jī)快速排序”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。
專業(yè)成都網(wǎng)站建設(shè)公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來(lái)客戶和效益!創(chuàng)新互聯(lián)建站為您提供成都網(wǎng)站建設(shè)，五站合一網(wǎng)站設(shè)計(jì)制作，服務(wù)好的網(wǎng)站設(shè)計(jì)公司，網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)負(fù)責(zé)任的成都網(wǎng)站制作公司!
快速排序也采用的是分而制之的思想。那么快速排序和歸并排序的區(qū)別在什么地方呢？
歸并排序是將所有的元素拆分成一個(gè)個(gè)排好序的數(shù)組，然后將這些數(shù)組再進(jìn)行合并。
而快速排序雖然也是拆分，但是拆分之后的操作是從數(shù)組中選出一個(gè)中間節(jié)點(diǎn)，然后將數(shù)組分成兩部分。
左邊的部分小于中間節(jié)點(diǎn)，右邊的部分大于中間節(jié)點(diǎn)。
然后再分別處理左邊的數(shù)組合右邊的數(shù)組。
假如我們有一個(gè)數(shù)組：29,10,14,37,20,25,44,15，怎么對(duì)它進(jìn)行快速排序呢？
先看一個(gè)動(dòng)畫：
我們?cè)俜治鲆幌驴焖倥判虻牟襟E。
我們選擇的是最左邊的元素29作為中間點(diǎn)元素，然后將數(shù)組分成三部分：[0, 14, 15, 20, 25],[29],[44, 37]。
中間節(jié)點(diǎn)29已經(jīng)排好序了，不需要處理。
接下來(lái)我們?cè)賹?duì)左右分別進(jìn)行快速排序。最后就得到了一個(gè)所有元素都排序的數(shù)組。
我們先來(lái)看最核心的部分partition，如何將數(shù)組以中間節(jié)點(diǎn)為界，分成左右兩部分呢？
我們的最終結(jié)果，是要將array分割成為三部分。
首先我們選擇最左側(cè)的元素作為中間節(jié)點(diǎn)的值。然后遍歷數(shù)組中的其他元素。
假如m=middleIndex，k=要遍歷的元素index
考慮兩種情況，第一種情況是數(shù)組中的元素比中間節(jié)點(diǎn)的值要大。
這種情況下，m不需要移動(dòng)，k+1繼續(xù)遍歷即可。
第二種情況下，數(shù)組中的元素比中間節(jié)點(diǎn)的值要小。
因?yàn)閙左邊的元素都要比中間節(jié)點(diǎn)的值要小，所以這種情況下m需要+1，即右移一位。
現(xiàn)在m+1位置的元素要么還沒(méi)有進(jìn)行比較，要么就是比中間節(jié)點(diǎn)的值要大，我們可以巧妙的將m+1位置的元素和k位置的元素互換位置，這樣仍然能夠保證m左側(cè)的元素要比中間節(jié)點(diǎn)的值要小。
將上面的分析總結(jié)成java代碼如下：
重慶分公司
重慶分公司
private int partition(int[] array, int i, int j) {
//選擇最左側(cè)的元素作為中心點(diǎn),middleValue就是中心點(diǎn)的值
int middleValue = array[i];
int middleIndex = i;
//從i+1遍歷整個(gè)數(shù)組
for (int k = i+1; k <= j; k++) {
//如果數(shù)組元素小于middleValue，表示middleIndex需要右移一位
//右移之后，我們需要將小于middleValue的array[k]移動(dòng)到middleIndex的左邊，
// 最簡(jiǎn)單的辦法就是交換k和middleIndex的值
if (array[k] < middleValue) {
middleIndex++;
//交換數(shù)組的兩個(gè)元素
swap(array, k , middleIndex);
} //如果數(shù)組元素大于等于middleValue,則繼續(xù)向后遍歷,middleIndex值不變
}
// 最后將中心點(diǎn)放入middleIndex位置
swap(array, i, middleIndex);
return middleIndex;
}最后我們需要將最左側(cè)的元素和中間節(jié)點(diǎn)應(yīng)該在的index的元素互換下位置，這樣就將中間節(jié)點(diǎn)移動(dòng)到了中間位置，并返回中間位置。
再來(lái)看下divide的代碼：
public void doQuickSort(int[] array, int low, int high) {
//遞歸的結(jié)束條件
if (low < high) {
//找出中心節(jié)點(diǎn)的值
int middleIndex = partition(array, low, high);
//數(shù)組分成了三部分：
// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
//遞歸遍歷左側(cè)部分
doQuickSort(array, low, middleIndex-1);
// a[m] 是中心節(jié)點(diǎn)，已經(jīng)排好序了，不需要繼續(xù)遍歷
//遞歸遍歷右側(cè)部分
doQuickSort(array, middleIndex+1, high);
log.info("QuickSort之后的數(shù)組:{}",array);
}
}divide的代碼就很簡(jiǎn)單了，找到中間節(jié)點(diǎn)的位置之后，我們?cè)俜謩e遍歷數(shù)組的左右兩邊即可。最后得到排好序的數(shù)組。
上面的例子中，我們的中間節(jié)點(diǎn)的選擇是數(shù)組的最左元素，為了保證排序的效率，我們可以從數(shù)組中隨機(jī)選擇一個(gè)元素來(lái)作為中間節(jié)點(diǎn)。
private int partition(int[] array, int i, int j) {
//隨機(jī)選擇一個(gè)元素作為中心點(diǎn),middleValue就是中心點(diǎn)的值
int randomIndex=i+new Random().nextInt(j-i);
log.info("randomIndex:{}",randomIndex);
//首先將randomIndex的值和i互換位置,就可以復(fù)用QuickSort的邏輯
swap(array, i , randomIndex);
int middleValue = array[i];
int middleIndex = i;
//從i遍歷整個(gè)數(shù)組
for (int k = i+1; k <= j; k++) {
//如果數(shù)組元素小于middleValue，表示middleIndex需要右移一位
//右移之后，我們需要將小于middleValue的array[k]移動(dòng)到middleIndex的左邊，
// 最簡(jiǎn)單的辦法就是交換k和middleIndex的值
if (array[k] < middleValue) {
middleIndex++;
//交換數(shù)組的兩個(gè)元素
swap(array, k , middleIndex);
} //如果數(shù)組元素大于等于middleValue,則繼續(xù)向后遍歷,middleIndex值不變
}
// 最后將中心點(diǎn)放入middleIndex位置
swap(array, i, middleIndex);
return middleIndex;
}上面的代碼，我們?cè)诜謪^(qū)的時(shí)候，先選擇出一個(gè)隨機(jī)的節(jié)點(diǎn)，然后將這個(gè)隨機(jī)的節(jié)點(diǎn)和最左側(cè)的元素交換位置，后面的代碼就可以重用上面的QuickSort的代碼邏輯了。
讀到這里，這篇“java怎么實(shí)現(xiàn)隨機(jī)快速排序”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
