一、快速排序：

在待排元素中找出一個(gè)基準(zhǔn)元素,然后比較基準(zhǔn)元素和其他元素，以基準(zhǔn)元素為基準(zhǔn)，將大于準(zhǔn)的元素的放后邊，小于
基準(zhǔn)的元素放前邊。然后再對(duì)分好的左右兩個(gè)小區(qū)間進(jìn)行快速排序
以基準(zhǔn)元素劃分區(qū)間的方式有以下2種：
第一種：設(shè)兩個(gè)參考變量less,great，less先從第一個(gè)元素開始往后遍歷，直到找到的當(dāng)前元素大于基準(zhǔn)元素。
然后讓great從最后一個(gè)元素開始往前遍歷，直到找到當(dāng)前元素小于基準(zhǔn)元素，交換當(dāng)前l(fā)ess和great指向的值。
再接著從less開始，重復(fù)上述動(dòng)作，遍歷結(jié)束的條件是less>=great;
遍歷結(jié)束后，交換當(dāng)前l(fā)ess(或great)指向的值與基準(zhǔn)元素的值。再進(jìn)行下一次的小區(qū)間內(nèi)的查找

創(chuàng)新互聯(lián)從2013年創(chuàng)立，先為武陟等服務(wù)建站，武陟等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為武陟企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

二、圖示

注意：新劃分的兩個(gè)區(qū)間的范圍是：
第一段：原本的left到上一輪基準(zhǔn)元素最終位置的前一位；即[left,pivotIndex-1]
第二段：上一輪基準(zhǔn)元素最終位置的后一位到原本的right;即[pivotIndex+1,right]

最終結(jié)果:

三、代碼實(shí)現(xiàn)

public static void quickSort ( int[] array){
int left = 0;
int right = array.length - 1;
quickSortInternal1(array, left, right);
}
public static void quickSortInternal ( int[] array, int left, int right){
if (left >= right) {
return;
}
int pivotIndex = partion1(array, left, right);//找基準(zhǔn)值的函數(shù)
// int[] indice=partion4(array,left,right);
// quickSortInternal(array,left,indice[0]-1);
// quickSortInternal(array,indice[1]+1,right);
quickSortInternal(array, left, pivotIndex - 1);//注意區(qū)間范圍
quickSortInternal(array, pivotIndex + 1, right);

}
private static int partion1 ( int[] array, int left, int right){
int pivot = array[right];
int less = left;
int great = right;
while (less < great) {
while (less < great && array[less] <= pivot) {
less++;
}
while (less < great && array[great] >= pivot) {
great--;
}
swap(array, less, great);
}
swap(array, less, right);
return less;
}

第二種：挖坑法
找到基準(zhǔn)元素pivot,設(shè)兩個(gè)變量less和great,less從第一個(gè)數(shù)開始向后遍歷,直到找到大于pivot的數(shù)，停下，將array[less]的值放到array[great]處。（即array[great]=array[less]）
然后讓right從當(dāng)前區(qū)間最后一個(gè)數(shù)開始往前遍歷，直到找到小于pivot的數(shù)，停下，進(jìn)行array[less]=array[great]的操作。再接著less++向后遍歷，重復(fù)以上操作，結(jié)束條件為left>=right;
結(jié)束后將pivot的值賦給當(dāng)前l(fā)ess(great)的數(shù)組元素
圖示：





注意：pivot基準(zhǔn)元素可以任意選，但這里為了講述方便，每次選擇區(qū)間的最后一個(gè)元素
最終結(jié)果

代碼實(shí)現(xiàn)

private static int partion1 ( int[] array, int left, int right){
int pivot = array[right];//基準(zhǔn)值
int less = left;
int great = right;
while (less < great) {
while (less < great && array[less] <= pivot) {
less++;
}
array[great] = array[less];
while (less < great && array[great] >= pivot) {
great--;
}
array[less] = array[great];
}
array[less] = pivot;
return less;
}

網(wǎng)站名稱：java七大排序——6_快速排序
本文URL：http://www.chinadenli.net/article8/jcodop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、電子商務(wù)、定制網(wǎng)站、品牌網(wǎng)站建設(shè)、搜索引擎優(yōu)化、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)