摘要:雙邊循環法快速排序的基本方法待排序的數組開始的結束的循環次數找到基準位置。需要加限制條件和指針重合點交換單邊循環法分治單循環法把小于基準值的,交換和基準值的到的左邊待交換的數組起始下標結束下標默認起始位置為基準值基準值的位置,不斷移動。
0. 索引 1. 簡單介紹
關于原理,雖然很重要,但是在這里不做過多介紹。 因為隨便搜索一下。就可以找到更好的答案。
本質是回顧,記住核心的思想,然后通過code 深刻 已有概念的印象。
2. 雙邊循環法/** * 快速排序的基本方法 * * @param intArr 待排序的數組 * @param startIndex 開始的 index * @param endIndex 結束的 index * @return 循環次數 */ public static long sort(int[] intArr, int startIndex, int endIndex) { if (startIndex >= endIndex) { return 0; } // 找到基準位置。 位置左邊的的都是小于的,位置右邊的都是大于的。 + 同事做好了排序 int pivotIndex = doubleSideSortFindPivot(intArr, startIndex, endIndex); sort(intArr, startIndex, pivotIndex - 1); sort(intArr, pivotIndex + 1, endIndex); return 1; } /** * 分治(雙邊循環法) * * @param intArr 待交換的數組 * @param startIndex 起始下標 * @param endIndex 結束下標 */ public static int doubleSideSortFindPivot(int[] intArr, int startIndex, int endIndex) { int pivotVal = intArr[startIndex]; int leftIndex = startIndex; int rightIndex = endIndex; // MARK : 之前用if leftIndex < rightIndex 報錯 while (leftIndex != rightIndex) { // 之前自己的寫法比較混亂 // step 1 :控制 right 指針,左移 // 錯誤1 : 使用了 if ,畢竟可以一直左移。 邏輯判斷 MARK while (leftIndex < rightIndex && intArr[rightIndex] > pivotVal) { rightIndex--; } // step 2 : 控制 left 指針 右移 while (leftIndex < rightIndex && intArr[leftIndex] <= pivotVal) { leftIndex++; } // step 3 :交換 left 和 right。 需要加限制條件 if (leftIndex < rightIndex) { int temp = intArr[leftIndex]; intArr[leftIndex] = intArr[rightIndex]; intArr[rightIndex] = temp; } } // 【replace】pivot和指針重合點交換 intArr[startIndex] = intArr[leftIndex]; intArr[leftIndex] = pivotVal; return leftIndex; }3. 單邊循環法
/** * 分治(單循環法) 把 小于基準值的,交換(和基準值的index )到 pivot 的左邊 * * @param intArr 待交換的數組 * @param startIndex 起始下標 * @param endIndex 結束下標 */ public static int oneSideSort(int[] intArr, int startIndex, int endIndex) { // 默認起始位置為基準值 int pivotVal = intArr[startIndex]; // 基準值的位置,不斷移動。左邊的代表交換過來的小于 pivotVal 的 int mark = startIndex; // 如果小于基準值的,交換,mark 右移 for (int i = startIndex + 1; i <= endIndex; i++) { // 小于的做交換 if (intArr[i] < pivotVal) { mark++; // 基準位右移 int temp = intArr[mark]; intArr[mark] = intArr[i]; intArr[i] = temp; } } // 交換 intArr[startIndex] = intArr[mark]; intArr[mark] = pivotVal; return mark; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74881.html
摘要:直接插入排序的算法重點在于尋找插入位置。也稱縮小增量排序,是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。簡單選擇排序常用于取序列中最大最小的幾個數時。將新構成的所有的數的十位數取出,按照十位數進行排序,構成一個序列。 1.直接插入排序 直接插入排序算法是排序算法中最簡單的,但在尋找插入位置時的效率不高。基本思想就是將一個待排序的數字在已經排序的序列中尋找找到一個插...
摘要:回來更新一波,最近刷劍指,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用,我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識,發現也用不上,我想說的是,讀一本書體現不了這本書 回來更新一波,最近刷《劍指offer》,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊~ /** * PHP二叉樹算法 * Create...
摘要:回來更新一波,最近刷劍指,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用,我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識,發現也用不上,我想說的是,讀一本書體現不了這本書 回來更新一波,最近刷《劍指offer》,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊~ /** * PHP二叉樹算法 * Create...
閱讀 2553·2021-11-23 09:51
閱讀 3355·2021-11-22 15:22
閱讀 1868·2021-11-18 13:22
閱讀 2236·2021-09-24 09:48
閱讀 1308·2019-08-29 13:58
閱讀 1297·2019-08-26 13:39
閱讀 2445·2019-08-26 10:48
閱讀 3031·2019-08-26 10:21