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

資訊專欄INFORMATION COLUMN

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

Yang_River / 923人閱讀

摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實(shí)現(xiàn)細(xì)節(jié)，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩(wěn)定性一個穩(wěn)定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩(wěn)定。

1. 導(dǎo)言

因?yàn)檫@是排序算法系列的第一篇文章，所以多啰嗦幾句。

排序是很常見的算法之一，現(xiàn)在很多編程語言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可以不在乎內(nèi)部實(shí)現(xiàn)細(xì)節(jié)而直接調(diào)用，在實(shí)際的軟件開發(fā)當(dāng)中也會經(jīng)常使用到。但是站在開發(fā)者的角度而言，知其然必須知其所以然。多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實(shí)現(xiàn)細(xì)節(jié)，更能夠鍛煉我們的思維，提升編程能力。現(xiàn)在很多技術(shù)面試也會涉及到基本的排序算法，所以多練習(xí)是有好處的。

文中涉及到的代碼都是Java實(shí)現(xiàn)的，但是不會涉及到太多的Java語言特性，并且我會加上詳細(xì)的注釋，幫助你理解代碼并且轉(zhuǎn)換成你熟悉的編程語言。

常見的排序算法有以下10種：

冒泡排序、選擇排序、插入排序，平均時間復(fù)雜度都是O(n2)

希爾排序、歸并排序、快速排序、堆排序，平均時間復(fù)雜度都是O(nlogn)

計數(shù)排序、基數(shù)排序、桶排序，平均時間復(fù)雜度都是O(n + k)

在開始具體的排序算法講解之前，先得明白兩個概念：

原地排序：指的是在排序的過程當(dāng)中不會占用額外的存儲空間，空間復(fù)雜度為O(1)。

排序算法的穩(wěn)定性：一個穩(wěn)定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩(wěn)定。舉個例子：一個數(shù)組 [3，5，1，4，9，6，6，12] 有兩個6（為了區(qū)分，我把其中一個 6 加粗），如果排序之后是這樣的：[1，3，4，5，6，6，9，12]（加粗的 6 仍然在前面），就說明這是一個穩(wěn)定的排序算法。

2. 言歸正傳

冒泡排序的思路其實(shí)很簡單，一個數(shù)據(jù)跟它相鄰的數(shù)據(jù)進(jìn)行大小的比較，如果滿足大小關(guān)系，就將這兩個數(shù)據(jù)交換位置。一直重復(fù)這個操作，就能將數(shù)據(jù)排序。

舉個例子，假如有數(shù)組 a[3,5,1,4,9,6]，第一次冒泡的操作如下圖所示：

重復(fù)進(jìn)行這個操作，6次冒泡之后，數(shù)據(jù)排序完成。

根據(jù)這個思路，應(yīng)該能很容易能夠?qū)懗鱿旅娴拇a實(shí)現(xiàn)冒泡排序：

public class BubbleSort {

    //data表示整型數(shù)組，n表示數(shù)組大小
    public static void bubbleSort(int[] data, int n){
        //數(shù)組大小小于等于1，無須排序
        if (n <= 1) return;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1]，交換兩個數(shù)據(jù)的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

但是這個排序算法還可以進(jìn)行優(yōu)化，當(dāng)冒泡操作已經(jīng)沒有數(shù)據(jù)交換的時候，說明排序已經(jīng)完成，就不用在進(jìn)行冒泡操作了。例如上面的例子，第一次冒泡之后，數(shù)據(jù)為 [3,1,4,5,6,9]，再進(jìn)行一次冒泡，數(shù)據(jù)變?yōu)?[1,3,4,5,6,9]，此時已經(jīng)完成了排序，就可以結(jié)束循環(huán)了。

所以針對這個數(shù)組的排序，上面的代碼需要6次冒泡才能完成，其中有4次都是不需要的。所以可以對代碼進(jìn)行優(yōu)化：

public class BubbleSort {

    //優(yōu)化后的冒泡排序
    //data表示整型數(shù)組，n表示數(shù)組大小
    public static void bubbleSort(int[] data, int n){
        //數(shù)組大小小于等于1，無須排序，返回空
        if (n <= 1) return;
        for (int i = 0; i < n; i++) {
            boolean flag = false;//判斷是否有數(shù)據(jù)交換

            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1]，交換兩個數(shù)據(jù)的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有數(shù)據(jù)交換
                }
            }
            //如果沒有數(shù)據(jù)交換，則直接退出循環(huán)
            if (!flag) break;
        }
    }
}

好了，冒泡排序的基本思路和代碼都已經(jīng)實(shí)現(xiàn)，最后總結(jié)一下：

冒泡排序是基于數(shù)據(jù)比較的

最好情況時間復(fù)雜度是O(n)，最壞情況時間復(fù)雜度是O(n2)，平均時間復(fù)雜度是O(n2)

冒泡排序是原地排序算法，并且是穩(wěn)定的。

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

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

相關(guān)文章

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

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r間復(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 評論0 收藏0

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

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

    chuyao 評論0 收藏0

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

    摘要：冒泡排序一種運(yùn)行效率很低的排序算法，然而雖然排序效率低，確實(shí)排序入門很重的算法，因?yàn)槊芭菖判虻乃悸肥亲詈唵巫钊菀桌斫獾呐判蛩惴?。二冒泡排序定義冒泡排序是一種通過兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止的交換排序。 一、前言 相信大部分同學(xué)都已經(jīng)學(xué)過數(shù)據(jù)結(jié)構(gòu)與算法這門課了，并且我們可能都會發(fā)現(xiàn)一個現(xiàn)象就是我們所學(xué)過的數(shù)據(jù)結(jié)構(gòu)與算法類的書籍基本都是使用 C 語言來...

    1treeS 評論0 收藏0

  • 你知道和你不知道的冒泡排序

    摘要：用來標(biāo)示該輪冒泡排序中，數(shù)組是否是有序的。適用情況當(dāng)冒泡算法運(yùn)行到后半段的時候，如果此時數(shù)組已經(jīng)有序了，需要提前結(jié)束冒泡排序。當(dāng)?shù)谝惠喢芭菖判蚪Y(jié)束后，元素會被移動到下標(biāo)的位置。 這篇文章包含了你一定知道的，和你不一定知道的冒泡排序。 gif看不了可以點(diǎn)擊【原文】查看gif。 源碼: 【地址】 1. 什么是冒泡排序 可能對于大多數(shù)的人來說比如我，接觸的第一個算法就是冒泡排序。 我看過的很...

    Worktile 評論0 收藏0

  • Github標(biāo)星2w+，熱榜第一，如何用Python實(shí)現(xiàn)所有算法

    摘要：歸并排序歸并排序，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚 學(xué)會了Python基礎(chǔ)知識，想進(jìn)階一下，那就來點(diǎn)算法吧！畢竟編程語言只...

    zxhaaa 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<