快速排序（一）荷蘭旗問題 快速排序（二）随機快排 學習了随機快排的遞歸實現，遞歸方法需要不斷地壓棧，有沒有不需要壓棧的方式實現呢？這裡就學習了使用循環來實現遞歸實現。

  遞歸操作時一個先遞進再出來的概念，但是我循環是從頭到尾，沒有這個概念啊，這裡就想到了和這個概念非常相似的數據結構，棧。

  棧，也是一個先進後出的結構，那是不是我隻要模拟遞歸，将數據不斷的壓入棧不斷的彈出棧循環操作是不是就可以實現呢？先畫個草圖理一下思路

  理論上我隻要有個邏輯可以完成，輸入數組，以及兩個下标值，完成荷蘭旗問題，同時生成等于劃分值的下标範圍，然後返回兩組要處理的下标，繼續壓入棧，循環這個出棧、處理、壓棧的操作，一直到棧為空，就可以完成整個快速排序了吧。

  因為我壓入棧的是成組的數據，包含兩個下标值，那我就創建一個輔助類，就存兩個下标。

static class 範圍{ int 左; int 右; 範圍(int 左,int 右){ this.左 = 左; this.右 = 右; } }

  接下來我就不寫解析了，具體每行代碼代表啥意思我都寫上去了

static class 範圍{ int 左; int 右; 範圍(int 左,int 右){ this.左 = 左; this.右 = 右; } } /** * 随機快排3 * @param arr * @param L * @param R */ public static void kspxrk3(int[] arr) { if (arr == null || arr.length < 2) { return; } // 先随機row一個值作為劃分值 int rowValue = (int) (Math.random() * arr.length); // 劃分值 和 最右值交換 swap(arr, rowValue, arr.length - 1); // 算出第一次劃分出來的下标 int[] 邊界 = hlqcz(arr, 0, arr.length - 1); // 創建一個棧 Stack<範圍> stack = new Stack<>(); // 往棧裡壓入數據 stack.push(new 範圍(0, 邊界[0] - 1));// 左組，是0到左邊界-1 stack.push(new 範圍(邊界[1] 1, arr.length - 1));// 右組，是右邊界 1到數組結束 // 處理棧中的數據,結束條件為棧為空 while (!stack.isEmpty()) { // 彈出要處理的數 範圍 f = stack.pop(); // 考慮邊界 if (f.左 < f.右) { // 繼續劃分的邏輯 // 先随機一個row作為劃分值，然後和最右值交換 swap(arr, (int) (Math.random() * (f.右 - f.左 1)), f.右); // 算出這次劃分出來的下标 邊界 = hlqcz(arr, f.左, f.右); // 再次将邊界下标壓入棧 stack.push(new 範圍(f.左, 邊界[0] - 1));// 左組，是0到左邊界-1 stack.push(new 範圍(邊界[1] 1, f.右));// 右組，是右邊界 1到數組結束 } } } public static int[] hlqcz(int[] arr , int L ,int R ) { // L大于R 的時候，越界了 if(L>R) { return new int[] {-1,-1}; } //L == R 的時候，左邊結束，右邊也結束了 if(L==R) { return new int[] {L,R}; } //左邊界 int less = L - 1; //右邊界 int more = R; //當前下标,從左開始 int index = L; //當前下标，碰觸右邊界結束 while (index<more) { if(arr[index]==arr[R]) { //如果當前值 和 最右位置值相等，最右位置值作為劃分值，當前下标 1，數據不動 index ; }else if(arr[index]<arr[R]) { //如果當前值 小于 劃分值，當前值和左邊界 1的值交換，然後左邊界 1，當前下标 1 swap(arr, index , less); }else { //如果當前值 大于 劃分值，當前值和右邊界-1的值交換，然後有邊界-1，當前下标不動 swap(arr, index, --more); } } //當前下标碰到右邊界了 //當前位置的值和R位置的值進行交換，R位置的值是劃分值，也就是說它一定在中間 swap(arr, more, R); //返回中間的值的下标 return new int[] {less 1,more}; }

既然棧都可以，那我用隊列是不是也可以，用鍊表實現棧然後應該也可以吧還沒想到其他的實現方式，如果大家有更好的方式歡迎評論留言，如果文中有哪些描述錯誤的地方，也歡迎大家斧正✨

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!