資訊專欄INFORMATION COLUMN
摘要：雙邊循環(huán)法快速排序的基本方法待排序的數(shù)組開始的結(jié)束的循環(huán)次數(shù)找到基準(zhǔn)位置。需要加限制條件和指針重合點交換單邊循環(huán)法分治單循環(huán)法把小于基準(zhǔn)值的，交換和基準(zhǔn)值的到的左邊待交換的數(shù)組起始下標(biāo)結(jié)束下標(biāo)默認(rèn)起始位置為基準(zhǔn)值基準(zhǔn)值的位置，不斷移動。
0. 索引 1. 簡單介紹
關(guān)于原理，雖然很重要，但是在這里不做過多介紹。 因為隨便搜索一下。就可以找到更好的答案。
本質(zhì)是回顧，記住核心的思想，然后通過code 深刻 已有概念的印象。
2. 雙邊循環(huán)法
/**
* 快速排序的基本方法
*
* @param intArr 待排序的數(shù)組
* @param startIndex 開始的 index
* @param endIndex 結(jié)束的 index
* @return 循環(huán)次數(shù)
*/
public static long sort(int[] intArr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return 0;
}
// 找到基準(zhǔn)位置。 位置左邊的的都是小于的，位置右邊的都是大于的。 + 同事做好了排序
int pivotIndex = doubleSideSortFindPivot(intArr, startIndex, endIndex);
sort(intArr, startIndex, pivotIndex - 1);
sort(intArr, pivotIndex + 1, endIndex);
return 1;
}
/**
* 分治（雙邊循環(huán)法）
*
* @param intArr 待交換的數(shù)組
* @param startIndex 起始下標(biāo)
* @param endIndex 結(jié)束下標(biāo)
*/
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. 單邊循環(huán)法
/**
* 分治（單循環(huán)法） 把 小于基準(zhǔn)值的，交換(和基準(zhǔn)值的index )到 pivot 的左邊
*
* @param intArr 待交換的數(shù)組
* @param startIndex 起始下標(biāo)
* @param endIndex 結(jié)束下標(biāo)
*/
public static int oneSideSort(int[] intArr, int startIndex, int endIndex) {
// 默認(rèn)起始位置為基準(zhǔn)值
int pivotVal = intArr[startIndex];
// 基準(zhǔn)值的位置，不斷移動。左邊的代表交換過來的小于 pivotVal 的
int mark = startIndex;
// 如果小于基準(zhǔn)值的，交換，mark 右移
for (int i = startIndex + 1; i <= endIndex; i++) {
// 小于的做交換
if (intArr[i] < pivotVal) {
mark++; // 基準(zhǔn)位右移
int temp = intArr[mark];
intArr[mark] = intArr[i];
intArr[i] = temp;
}
}
// 交換
intArr[startIndex] = intArr[mark];
intArr[mark] = pivotVal;
return mark;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/74881.html
摘要：直接插入排序的算法重點在于尋找插入位置。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。簡單選擇排序常用于取序列中最大最小的幾個數(shù)時。將新構(gòu)成的所有的數(shù)的十位數(shù)取出，按照十位數(shù)進(jìn)行排序，構(gòu)成一個序列。 1.直接插入排序 直接插入排序算法是排序算法中最簡單的，但在尋找插入位置時的效率不高。基本思想就是將一個待排序的數(shù)字在已經(jīng)排序的序列中尋找找到一個插...
摘要：回來更新一波，最近刷劍指，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學(xué)了一些樹的知識，發(fā)現(xiàn)也用不上，我想說的是，讀一本書體現(xiàn)不了這本書 回來更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...
摘要：回來更新一波，最近刷劍指，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學(xué)了一些樹的知識，發(fā)現(xiàn)也用不上，我想說的是，讀一本書體現(xiàn)不了這本書 回來更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...
閱讀 2570·2021-11-23 09:51
閱讀 3365·2021-11-22 15:22
閱讀 1878·2021-11-18 13:22
閱讀 2273·2021-09-24 09:48
閱讀 1318·2019-08-29 13:58
閱讀 1309·2019-08-26 13:39
閱讀 2453·2019-08-26 10:48
閱讀 3040·2019-08-26 10:21
