成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【算法】冒泡排序

kel / 785人閱讀

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

No bb . Show me the code
1. 簡(jiǎn)單實(shí)現(xiàn) 
public static long sort(int[] intArr) {
        int  arrLen     = intArr.length;
        long recycleNum = 0;
        if (0 == arrLen) {
            return recycleNum;
        }
        for (int i = 0; i < arrLen; i++) {
            for (int j = 0; j < arrLen - 1; j++) {
                recycleNum++;
                // 左邊是大（不是正常的排序順序）的做交換
                if (intArr[j] > intArr[j + 1]) {
                    int temp = intArr[j];
                    intArr[j] = intArr[j + 1];
                    intArr[j + 1] = temp;
                }
            }
        }

        return recycleNum;
    }

考慮優(yōu)化

2. 優(yōu)化 
/**
     * 冒泡排序-優(yōu)化版本，節(jié)約有序的
     *
     * @param intArr
     */
    public static long sortPlus(int[] intArr) {
        // 第一輪，永遠(yuǎn)是找到最大的
        // 第二輪，找到的是第二大的，所以右邊 n 個(gè)永遠(yuǎn)是有序的
        // 如果有一種特殊情況，右邊經(jīng)過對(duì)比，發(fā)現(xiàn)不需要交換了，那就是后面的都是最大的。 有一個(gè)不是前面對(duì)比最大的，就會(huì)發(fā)生交換

        // 加一個(gè)標(biāo)記位，不發(fā)生交換的位置，就是比較的end
        // 這樣 原則上 1，2，3，4，5，6，7，8 只需要比較一輪
        int  arrLen     = intArr.length;
        long recycleNum = 0;
        if (0 == arrLen) {
            return recycleNum;
        }
        boolean isSorted = true;
        for (int i = 0; i < arrLen; i++) {
            for (int j = 0; j < arrLen - 1; j++) {
                recycleNum++;
                // 左邊是大（不是正常的排序順序）的做交換
                if (intArr[j] > intArr[j + 1]) {
                    int temp = intArr[j];
                    intArr[j] = intArr[j + 1];
                    intArr[j + 1] = temp;
                    // 發(fā)生了交換
                    isSorted = false;
                }
            }
            // TODO mark 是不是 j 都遍歷一遍 只是增加了 判斷。 反而增加了邏輯判斷
            if (isSorted) {
                break;
            }
        }
        return recycleNum;
    }
3. 有序區(qū) 
/**
     * 冒泡排序-有序區(qū)
     *
     * @param intArr
     */
    public static long sortOrdered(int[] intArr) {
        int  arrLen            = intArr.length;
        int  lastExchangeIndex = arrLen;
        int  sortLen           = arrLen - 1;
        long recycleNum        = 0;
        if (0 == arrLen) {
            return recycleNum;
        }

        boolean isSorted = true;
        for (int i = 0; i < arrLen; i++) {
            for (int j = 0; j < sortLen; j++) {
                recycleNum++;
                // 左邊是大（不是正常的排序順序）的做交換
                if (intArr[j] > intArr[j + 1]) {
                    int temp = intArr[j];
                    intArr[j] = intArr[j + 1];
                    intArr[j + 1] = temp;
                    // 發(fā)生了交換
                    isSorted = false;

                    // 排序后的位置一定是有序的期間
                    lastExchangeIndex = j;
                }
            }

            // 節(jié)約空間，如果已經(jīng)有序，不對(duì)比那么多，縮短長(zhǎng)度
            // 為了不影響 j 循環(huán)，循環(huán)結(jié)束后引入新的變量
            sortLen = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
        return recycleNum;
    }
4. 測(cè)試代碼 
/**
 * 循環(huán)次數(shù)，測(cè)試性能
 */
private static final int NUM = 1;

public static void main(String[] args) {
    //獲取開始時(shí)間
    long startTime = System.currentTimeMillis();

    for (int i = 0; i < NUM; i++) {
        int[] intArr = new int[]{3, 4, 2, 1, 5, 6, 7, 8, 11};
        // 72
        //            long recycleNum = sort(intArr);
        // 72
        long recycleNum = sortPlus(intArr);
        // 11
        //            long recycleNum = sortOrdered(intArr);
        System.out.println("循環(huán)次數(shù):" + recycleNum);
        //  System.out.println(Arrays.toString(intArr));
    }
    // 獲取結(jié)束時(shí)間
    long endTime = System.currentTimeMillis();
    System.out.println("程序運(yùn)行時(shí)間： " + (endTime - startTime) + "ms");
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

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

相關(guān)文章

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...

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

  • 數(shù)據(jù)結(jié)構(gòu)與算法——冒泡排序

    摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實(shí)現(xiàn)細(xì)節(jié)，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩(wěn)定性一個(gè)穩(wěn)定的排序，指的是在排序之后，相同元素的前后順序不會(huì)被改變，反之就稱為不穩(wěn)定。 1. 導(dǎo)言 因?yàn)檫@是排序算法系列的第一篇文章，所以多啰嗦幾句。 排序是很常見的算法之一，現(xiàn)在很多編程語(yǔ)言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...

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

  • 排序算法分析總結(jié)（附j(luò)s實(shí)現(xiàn)）

    摘要：本文對(duì)一些排序算法進(jìn)行了簡(jiǎn)單分析，并給出了的代碼實(shí)現(xiàn)。平均時(shí)間復(fù)雜度不好分析，它是冒泡排序是穩(wěn)定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復(fù)雜度是的排序算法。歸并排序，會(huì)將數(shù)組從中間分成左右兩部分。 本文對(duì)一些排序算法進(jìn)行了簡(jiǎn)單分析，并給出了 javascript 的代碼實(shí)現(xiàn)。因?yàn)楸疚陌舜罅康呐判蛩惴?，所以分析不?huì)非常詳細(xì)，適合有對(duì)排序算法有一定了解的同學(xué)。本文內(nèi)容其實(shí)不...

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

  • 數(shù)據(jù)結(jié)構(gòu)與算法（二）：帶你讀懂冒泡排序（Bubble Sorting）

    摘要：經(jīng)過一次冒泡排序，最終在無(wú)序表中找到一個(gè)最大值，第一次冒泡結(jié)束。也是我們后面要說(shuō)的冒泡排序的優(yōu)化。冒泡排序只執(zhí)行第一層循環(huán)，而不會(huì)執(zhí)行第二層循環(huán)。因此冒泡排序的時(shí)間復(fù)雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

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

  • 算法之旅 | 冒泡排序法

    摘要：學(xué)堂碼匠本期繼續(xù)走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優(yōu)化假如序列的數(shù)據(jù)為使用上面的冒泡排序法進(jìn)行排序，得到的結(jié)果肯定沒有問題，但是，待排序的序列是有序的，理論上是無(wú)需遍歷排序。 HTML5學(xué)堂-碼匠：本期繼續(xù)走入算法 —— 冒泡排序法。冒泡排序算法相對(duì)簡(jiǎn)單，容易上手，穩(wěn)定性也比較高,算是一種較好理解的算法，也是面試官高頻提問的算法之一。 Tips：關(guān)于算法及排序的基礎(chǔ)知識(shí)...

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

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

0條評(píng)論

kel

男|高級(jí)講師

TA的文章

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