快速排序遞歸代碼（不用遞歸你還能實現隨機快速排序嗎）

2023-05-29 10:10:13

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

思考

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

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

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

❤️代碼

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

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.左 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}; }

總結

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