亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

【TODO】【算法】快速排序

Flands / 629人閱讀

摘要：雙邊循環(huán)法快速排序的基本方法待排序的數(shù)組開(kāi)始的結(jié)束的循環(huán)次數(shù)找到基準(zhǔn)位置。需要加限制條件和指針重合點(diǎn)交換單邊循環(huán)法分治單循環(huán)法把小于基準(zhǔn)值的，交換和基準(zhǔn)值的到的左邊待交換的數(shù)組起始下標(biāo)結(jié)束下標(biāo)默認(rèn)起始位置為基準(zhǔn)值基準(zhǔn)值的位置，不斷移動(dòng)。

0. 索引 1. 簡(jiǎn)單介紹

關(guān)于原理，雖然很重要，但是在這里不做過(guò)多介紹。 因?yàn)殡S便搜索一下。就可以找到更好的答案。

本質(zhì)是回顧，記住核心的思想，然后通過(guò)code 深刻 已有概念的印象。

2. 雙邊循環(huán)法 
/**
 * 快速排序的基本方法
 *
 * @param intArr     待排序的數(shù)組
 * @param startIndex 開(kāi)始的 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 報(bào)錯(cuò)
    while (leftIndex != rightIndex) {

        // 之前自己的寫(xiě)法比較混亂
        // step 1 :控制 right 指針，左移
        // 錯(cuò)誤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和指針重合點(diǎn)交換
    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)值的位置，不斷移動(dòng)。左邊的代表交換過(guò)來(lái)的小于 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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/74881.html

相關(guān)文章

  • 【TODO】【算法】雞尾酒排序

    0. 索引 1. 基本介紹 2. 算法實(shí)現(xiàn)

    dinfer 評(píng)論0 收藏0

  • Java常用的八種排序算法與代碼實(shí)現(xiàn)精解

    摘要：直接插入排序的算法重點(diǎn)在于尋找插入位置。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。簡(jiǎn)單選擇排序常用于取序列中最大最小的幾個(gè)數(shù)時(shí)。將新構(gòu)成的所有的數(shù)的十位數(shù)取出，按照十位數(shù)進(jìn)行排序，構(gòu)成一個(gè)序列。 1.直接插入排序 直接插入排序算法是排序算法中最簡(jiǎn)單的，但在尋找插入位置時(shí)的效率不高。基本思想就是將一個(gè)待排序的數(shù)字在已經(jīng)排序的序列中尋找找到一個(gè)插...

    2501207950 評(píng)論0 收藏0

  • 利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)（小白系列文章六）

    摘要：回來(lái)更新一波，最近刷劍指，才又發(fā)現(xiàn)樹(shù)真是一個(gè)大頭，二叉樹(shù)的題目和變化運(yùn)用好多啊二叉樹(shù)算法引子很多人說(shuō)二叉樹(shù)沒(méi)什么卵用，我覺(jué)得是他的工資和公司讓他跨不過(guò)這個(gè)坎還有很多人學(xué)了一些樹(shù)的知識(shí)，發(fā)現(xiàn)也用不上，我想說(shuō)的是，讀一本書(shū)體現(xiàn)不了這本書(shū) 回來(lái)更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹(shù)真是一個(gè)大頭，二叉樹(shù)的題目和變化運(yùn)用好多啊～ /** * PHP二叉樹(shù)算法 * Create...

    Cympros 評(píng)論0 收藏0

  • 利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)（小白系列文章五）

    摘要：回來(lái)更新一波，最近刷劍指，才又發(fā)現(xiàn)樹(shù)真是一個(gè)大頭，二叉樹(shù)的題目和變化運(yùn)用好多啊二叉樹(shù)算法引子很多人說(shuō)二叉樹(shù)沒(méi)什么卵用，我覺(jué)得是他的工資和公司讓他跨不過(guò)這個(gè)坎還有很多人學(xué)了一些樹(shù)的知識(shí)，發(fā)現(xiàn)也用不上，我想說(shuō)的是，讀一本書(shū)體現(xiàn)不了這本書(shū) 回來(lái)更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹(shù)真是一個(gè)大頭，二叉樹(shù)的題目和變化運(yùn)用好多啊～ /** * PHP二叉樹(shù)算法 * Create...

    developerworks 評(píng)論0 收藏0

  • 【算法】冒泡排序

    摘要：簡(jiǎn)單實(shí)現(xiàn)左邊是大不是正常的排序順序的做交換考慮優(yōu)化優(yōu)化冒泡排序優(yōu)化版本，節(jié)約有序的第一輪，永遠(yuǎn)是找到最大的第二輪，找到的是第二大的，所以右邊個(gè)永遠(yuǎn)是有序的如果有一種特殊情況，右邊經(jīng)過(guò)對(duì)比，發(fā)現(xiàn)不需要交換了，那就是后面的都是最大的。 No bb . Show me the code 1. 簡(jiǎn)單實(shí)現(xiàn) public static long sort(int[] intArr) { ...

    kel 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<