基本思路
選擇一個基準值，將數(shù)組劃分三個區(qū)域，小于基準值的區(qū)域位于左側(cè)，等于基準值的區(qū)域位于中間，大于基準值的區(qū)域位于右側(cè)。將大于和小于區(qū)域繼續(xù)進行分區(qū)，周而復始，不斷進行分區(qū)和交換，直到排序完成
遞歸
思路：
步驟1:
在當前分區(qū)范圍[l,r]中隨機選中一個數(shù)作為基準值，交換到分區(qū)范圍的最右側(cè)，即r位置
步驟2:
以r位置基準值進行分區(qū)
步驟3:
對所以小于區(qū)域和大于區(qū)域繼續(xù)進行步驟1操作，直到范圍為1結(jié)束
單次分區(qū)過程：
less 代表小于基準值分區(qū)范圍，more代表大于分區(qū)值范圍，index代表當前待比較位置，r為當前分區(qū)范圍最右位置
比較當前index位置和基準位置
如果 arr[index] == arr[r] ，則index向右移動
如果大于，則 more向左移動，并將index位置的數(shù)與more位置的數(shù)進行交換
如果小于，則將 less右側(cè)位置的數(shù)與index數(shù)交換；即less范圍擴大 less++，交換less和index位置數(shù)，index右移
code：
//遞歸
public static void quickSortRecursive(int [] arr){
if(arr == null || arr.length < 2)return;
progress(arr,0,arr.length-1);
}
//讓arr在[l,r]上有序
public static void progress(int [] arr,int l,int r){
if(l >= r){
return;
}
//swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
//指定一個[l,r]范圍隨機位置放到最右側(cè)作為基準值
// math.random: [0,1)
// math.random * x : [0,x)
// Math.random() * (r -l + 1) : l到r長度范圍內(nèi)的一個隨機數(shù)， + l則定位到數(shù)組的索引上
swap(arr,l + (int)(Math.random() * (r -l + 1)),r);
int [] equalArea = partition(arr,l,r);
progress(arr,l,equalArea[0] -1);
progress(arr,equalArea[1] + 1,r);
}
//讓arr以r位置數(shù)為基準，<arr[r]位置的數(shù)放左邊，>arr[r]位置的數(shù)放右邊 ==arr[r]位置的數(shù)位于中間
//返回==arr[r]位置的數(shù)最左和最右位置
public static int[] partition(int [] arr,int l,int r){
//如果l > r，則數(shù)組不合規(guī)，返回一個無效值索引
if(l > r) return new int[] { -1, -1 };
//如果l == r，則說明只有一個值,那么等于分區(qū)也就是當前一個位置的索引
if(l == r) return new int[] {l,r};
//l < r
//基準位置 r
//less代表 <分區(qū) 的最右一個位置索引
int less = l -1;
//more代表 >分區(qū) 的最左一個位置的索引
int more = r;
//index代表待分區(qū)數(shù)最左位置索引
int index = l;
//進行分區(qū)，越界條件是待分區(qū)索引來到以分區(qū)區(qū)域[大于分區(qū)]
while (index < more){
//System.out.println("less,index,more:"+less+","+index + ","+more);
//如果待分區(qū)數(shù) == 基準值，那么說明該數(shù)不是大于分區(qū)的數(shù)，index向右移動
if(arr[index] == arr[r]){
index++;
}
//如果待分區(qū)數(shù) < 基準值，那么說明該位置數(shù)是屬于小于分區(qū)的數(shù)，則將該數(shù)交換到小于分區(qū)去
if(arr[index] < arr[r]){
//小于分區(qū)范圍擴大
less++;
//將當前位置交換到小于分區(qū)
//此時當前位置是等于或者小于分區(qū)的數(shù)
swap(arr,index,less);
//索引index需要向右移動
index++;
//等價于
//swap(arr,index++,++less);
}
//如果待分區(qū)數(shù) > 基準值，那么說明該位置數(shù)是屬于大于分區(qū)的數(shù),則將該數(shù)交換到大于分區(qū)去
//此時index不移動，因為將位置的數(shù)交換到index位置上了
if(arr[index] > arr[r]){
//大于范圍向左擴張
more--;
//當前數(shù)交換到大于區(qū)域中，交換來的數(shù)是一個未知大小的數(shù)，所以index不移動
swap(arr,index,more);
//等價于
//swap(arr,index,--more);
}
}
//遍歷完成后，此時r位置為等于區(qū)域的數(shù)，需要交換到等于分區(qū)中
swap(arr,more,r);
//交換完成后，less為小于分區(qū)最右索引，more為等于分區(qū)最右索引
//more原本為大于分區(qū)最左位置索引，但是將r交換到該位置后，大于分區(qū)向右縮減了一個位置，此時more位置為等于分區(qū)最右索引
return new int[]{less+1,more};
}
public static void swap(int [] arr,int l,int r){
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}非遞歸
思路與遞歸一致，僅是將系統(tǒng)棧替換為自己控制的棧
使用棧記錄每次分區(qū)得到的左右位置
然后出棧頂元素，繼續(xù)分區(qū)，將新的分區(qū)如棧，直到棧為空文章來源：http://www.zghlxwxcb.cn/news/detail-700857.html
使用一個輔助對象用于入棧時保存分區(qū)位置 op文章來源地址http://www.zghlxwxcb.cn/news/detail-700857.html
code：
//非遞歸版
//使用棧記錄每次分區(qū)得到的左右位置
//然后出棧頂元素，繼續(xù)分區(qū)，將新的分區(qū)如棧，直到棧為空
//使用一個輔助對象用于入棧時保存分區(qū)位置 op
public static void quickSortUnRecursive(int [] arr){
if(arr == null || arr.length < 2) return;
int N = arr.length;
Stack<Op> stack = new Stack<>();
//隨機得到基準值，放到最右位置
swap(arr, (int)(Math.random() * N),N-1);
//分區(qū)
int [] equalArea = partition(arr,0,N-1);
//將分區(qū)后的范圍入棧
stack.push(new Op(0,equalArea[0] -1));
stack.push(new Op(equalArea[1]+1,N-1));
//臨時變量，保存出棧的范圍值
Op temp = new Op(0,0);
while (!stack.isEmpty()){
//出棧
temp = stack.pop();
//繼續(xù)對當前范圍進行分區(qū)
//如果分區(qū)得到的范圍錯誤，說明該區(qū)域已經(jīng)排好序了
if(temp.l >= temp.r)continue;
//隨機基準值
swap(arr,temp.l + (int) (Math.random() * (temp.r - temp.l + 1)), temp.r);
//分區(qū)
equalArea = partition(arr,temp.l, temp.r);
//入棧
stack.push(new Op(temp.l, equalArea[0] -1));
stack.push(new Op(equalArea[1]+ 1, temp.r));
}
}
public static class Op{
public int l;
public int r;
public Op(int l,int r){
this.l = l;this.r = r;
}
}
//讓arr以r位置數(shù)為基準，<arr[r]位置的數(shù)放左邊，>arr[r]位置的數(shù)放右邊 ==arr[r]位置的數(shù)位于中間
//返回==arr[r]位置的數(shù)最左和最右位置
public static int[] partition(int [] arr,int l,int r){
//如果l > r，則數(shù)組不合規(guī)，返回一個無效值索引
if(l > r) return new int[] { -1, -1 };
//如果l == r，則說明只有一個值,那么等于分區(qū)也就是當前一個位置的索引
if(l == r) return new int[] {l,r};
//l < r
//基準位置 r
//less代表 <分區(qū) 的最右一個位置索引
int less = l -1;
//more代表 >分區(qū) 的最左一個位置的索引
int more = r;
//index代表待分區(qū)數(shù)最左位置索引
int index = l;
//進行分區(qū)，越界條件是待分區(qū)索引來到以分區(qū)區(qū)域[大于分區(qū)]
while (index < more){
//System.out.println("less,index,more:"+less+","+index + ","+more);
//如果待分區(qū)數(shù) == 基準值，那么說明該數(shù)不是大于分區(qū)的數(shù)，index向右移動
if(arr[index] == arr[r]){
index++;
}
//如果待分區(qū)數(shù) < 基準值，那么說明該位置數(shù)是屬于小于分區(qū)的數(shù)，則將該數(shù)交換到小于分區(qū)去
if(arr[index] < arr[r]){
//小于分區(qū)范圍擴大
less++;
//將當前位置交換到小于分區(qū)
//此時當前位置是等于或者小于分區(qū)的數(shù)
swap(arr,index,less);
//索引index需要向右移動
index++;
//等價于
//swap(arr,index++,++less);
}
//如果待分區(qū)數(shù) > 基準值，那么說明該位置數(shù)是屬于大于分區(qū)的數(shù),則將該數(shù)交換到大于分區(qū)去
//此時index不移動，因為將位置的數(shù)交換到index位置上了
if(arr[index] > arr[r]){
//大于范圍向左擴張
more--;
//當前數(shù)交換到大于區(qū)域中，交換來的數(shù)是一個未知大小的數(shù)，所以index不移動
swap(arr,index,more);
//等價于
//swap(arr,index,--more);
}
}
//遍歷完成后，此時r位置為等于區(qū)域的數(shù)，需要交換到等于分區(qū)中
swap(arr,more,r);
//交換完成后，less為小于分區(qū)最右索引，more為等于分區(qū)最右索引
//more原本為大于分區(qū)最左位置索引，但是將r交換到該位置后，大于分區(qū)向右縮減了一個位置，此時more位置為等于分區(qū)最右索引
return new int[]{less+1,more};
}
public static void swap(int [] arr,int l,int r){
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}到了這里，關(guān)于快速排序算法的遞歸和非遞歸的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第六篇] 遞歸實現(xiàn)快速排序（集霍爾版本，挖坑法，前后指針法為一篇的實現(xiàn)方法，很能打）](https://imgs.yssmx.com/Uploads/2024/02/589845-1.png)
