国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

冒泡排序及優(yōu)化詳解

evin2016 / 1415人閱讀

摘要:算法思想冒泡排序?qū)儆谝环N典型的交換排序。冒泡排序常規(guī)版代碼實(shí)現(xiàn)下面詳細(xì)分析一下常規(guī)版的冒泡排序,整個(gè)算法流程其實(shí)就是上面實(shí)例所分析的過(guò)程。

算法思想

  冒泡排序?qū)儆谝环N典型的交換排序。

  交換排序顧名思義就是通過(guò)元素的兩兩比較,判斷是否符合要求,如過(guò)不符合就交換位置來(lái)達(dá)到排序的目的。冒泡排序名字的由來(lái)就是因?yàn)樵诮粨Q過(guò)程中,類(lèi)似水冒泡,小(大)的元素經(jīng)過(guò)不斷的交換由水底慢慢的浮到水的頂端。

  冒泡排序的思想就是利用的比較交換,利用循環(huán)將第 i 小或者大的元素歸位,歸位操作利用的是對(duì) n 個(gè)元素中相鄰的兩個(gè)進(jìn)行比較,如果順序正確就不交換,如果順序錯(cuò)誤就進(jìn)行位置的交換。通過(guò)重復(fù)的循環(huán)訪問(wèn)數(shù)組,直到?jīng)]有可以交換的元素,那么整個(gè)排序就已經(jīng)完成了。

示例

  我們通過(guò)一個(gè)示例來(lái)理解一下基本的冒泡排序,假設(shè)當(dāng)前我們有一個(gè)數(shù)組 a,內(nèi)部元素為 3,4,1,5,2,即初始狀態(tài),如下圖所示。我們的目的就是通過(guò) n 趟比較來(lái)實(shí)現(xiàn)有底向上從大到小的的順序。

第一遍排序

  我們首先進(jìn)行第一遍排序,如下圖所示,紅色代表當(dāng)前比較的元素,綠色代表已經(jīng)歸位的元素。

  (1)比較第一個(gè)和第二個(gè)元素,4>3,交換。

  (2)比較第二個(gè)和第三個(gè)元素,1<3,不交換。

  (3)比較第三個(gè)和第四個(gè)元素,5>1,交換。

  (4)比較第四個(gè)和第五個(gè)元素,2>1,交換。

  最后,我們可以看到 1 已經(jīng)位于最頂部。第一遍需要盡心四次比較才能把五個(gè)數(shù)比較完。

第二遍排序

  第二遍排序的初始狀態(tài)是第一遍排序的最終狀態(tài),即4,3,5,2,1。

  (1)比較第一個(gè)和第二個(gè)元素,3<4,不交換。

  (2)比較第二個(gè)和第三個(gè)元素,5>3,交換。

  (3)比較第三個(gè)和第四個(gè)元素,2<3,不交換。

  第二遍排序,會(huì)讓 2 歸位,并且這一遍只用進(jìn)行三次比較就可以了。

第三遍排序

  第三遍排序的初始狀態(tài)是第二遍排序的最終狀態(tài),即4,5,3,2,1。

  (1)比較第一個(gè)和第二個(gè)元素,5>4,交換。

  (2)比較第二個(gè)和第三個(gè)元素,3<4,不交換。

  第三遍排序,會(huì)讓 3 歸位,并且這一遍只用進(jìn)行兩次比較就可以了。

  然而我們可以看到這一次五個(gè)數(shù)已經(jīng)全部完成了歸位,但是當(dāng)我們采用普通的冒泡排序的時(shí)候,算法仍然會(huì)繼續(xù)向下進(jìn)行。

第四遍循環(huán)

  第四遍排序的初始狀態(tài)是第三遍排序的最終狀態(tài),即5,4,3,2,1。

  這個(gè)時(shí)候就可以看出,排序?qū)嶋H上在第三遍已經(jīng)完成了,但是算法還是會(huì)繼續(xù)向下進(jìn)行,下面就進(jìn)行代碼實(shí)現(xiàn),看一下究竟是什么情況。。

冒泡排序性能
算法 最好時(shí)間 最壞時(shí)間 平均時(shí)間 額外空間 穩(wěn)定性
冒泡 O(n) O(n2) O(n2) 1 穩(wěn)定

  關(guān)于穩(wěn)定性:因?yàn)樵诒容^的過(guò)程中,當(dāng)兩個(gè)相同大小的元素相鄰,只比較大或者小,所以相等的時(shí)候是不會(huì)交換位置的。而當(dāng)兩個(gè)相等元素離著比較遠(yuǎn)的時(shí)候,也只是會(huì)把他們交換到相鄰的位置。他們的位置前后關(guān)系不會(huì)發(fā)生任何變化,所以算法是穩(wěn)定的。

  關(guān)于最優(yōu)時(shí)間復(fù)雜度為什么是O(n),當(dāng)然是優(yōu)化過(guò)算法之后了!大家繼續(xù)向下看就知道了!。

冒泡排序常規(guī)版-代碼實(shí)現(xiàn)

  下面詳細(xì)分析一下常規(guī)版的冒泡排序,整個(gè)算法流程其實(shí)就是上面實(shí)例所分析的過(guò)程。可以看出,我們?cè)谶M(jìn)行每一次大循環(huán)的時(shí)候,還要進(jìn)行一個(gè)小循環(huán)來(lái)遍歷相鄰元素并交換。所以我們的代碼中首先要有兩層循環(huán)。

  外層循環(huán):即主循環(huán),需要輔助我們找到當(dāng)前第 i 小的元素來(lái)讓它歸位。所以我們會(huì)一直遍歷 n-2 次,這樣可以保證前 n-1 個(gè)元素都在正確的位置上,那么最后一個(gè)也可以落在正確的位置上了。

  內(nèi)層循環(huán):即副循環(huán),需要輔助我們進(jìn)行相鄰元素之間的比較和換位,把大的或者小的浮到水面上。所以我們會(huì)一直遍歷 n-1-i 次這樣可以保證沒(méi)有歸位的盡量歸位,而歸位的就不用再比較了。

  而上面的問(wèn)題,出現(xiàn)的原因也來(lái)源于這兩次無(wú)腦的循環(huán),正是因?yàn)檠h(huán)不顧一切的向下執(zhí)行,所以會(huì)導(dǎo)致在一些特殊情況下得多余。例如 5,4,3,1,2 的情況下,常規(guī)版會(huì)進(jìn)行四次循環(huán),但實(shí)際上第一次就已經(jīng)完成排序了。

/**
 * @author jyroy
 * 冒泡排序常規(guī)版
 */
public class BubbleSortNormal {
    public static void main(String[] args) {
        int[] list = {3,4,1,5,2};
        int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            System.out.format("第 %d 遍:
", i+1);
            //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上
            for (int j = 0; j < list.length-1-i; j++) {
                // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),就交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                }
                System.out.format("第 %d 遍的第%d 次交換:", i+1,j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");
            }
            System.out.format("第 %d 遍最終結(jié)果:", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("
#########################");
        }
    }
}

  運(yùn)行結(jié)果

算法的第一次優(yōu)化

  經(jīng)過(guò)了上述的討論和編碼,常規(guī)的冒泡排序已經(jīng)被我們實(shí)現(xiàn)了。那么接下來(lái)我們要討論的就是剛剛分析時(shí)候提出的問(wèn)題。

  首先針對(duì)第一個(gè)問(wèn)題,當(dāng)我們進(jìn)行完第三遍的時(shí)候,實(shí)際上整個(gè)排序都已經(jīng)完成了,但是常規(guī)版還是會(huì)繼續(xù)排序。

  可能在上面這個(gè)示例下,可能看不出來(lái)效果,但是當(dāng)數(shù)組是,5,4,3,1,2 的時(shí)候的時(shí)候就非常明顯了,實(shí)際上在第一次循環(huán)的時(shí)候整個(gè)數(shù)組就已經(jīng)完成排序,但是常規(guī)版的算法仍然會(huì)繼續(xù)后面的流程,這就是多余的了。

  為了解決這個(gè)問(wèn)題,我們可以設(shè)置一個(gè)標(biāo)志位,用來(lái)表示當(dāng)前第 i 趟是否有交換,如果有則要進(jìn)行 i+1 趟,如果沒(méi)有,則說(shuō)明當(dāng)前數(shù)組已經(jīng)完成排序。實(shí)現(xiàn)代碼如下:

/**
 * @author jyroy
 * 冒泡排序優(yōu)化第一版
 */
public class BubbleSoerOpt1 {
    public static void main(String[] args) {
        int[] list = {5,4,3,1,2};
        int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設(shè)置一個(gè)標(biāo)志位
            //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上
            for (int j = 0; j < list.length-1-i; j++) {
                // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發(fā)生交換,標(biāo)志位置0
                }
            }
            System.out.format("第 %d 遍最終結(jié)果:", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒(méi)有交換過(guò)元素,則已經(jīng)有序
                return;
            }
                   
        }
    }
}

  運(yùn)行結(jié)果:可以看到優(yōu)化效果非常明顯,比正常情況下少了兩次的循環(huán)。

  這個(gè)時(shí)候我們就來(lái)討論一下上面留下的一個(gè)小地方!沒(méi)錯(cuò)就是最優(yōu)時(shí)間復(fù)雜度為O(n)的問(wèn)題,我們?cè)谶M(jìn)行了這一次算法優(yōu)化之后,就可以做到了。

  當(dāng)給我們一個(gè)數(shù)列,5,4,3,2,1,讓我們從大到小排序。沒(méi)錯(cuò),這是已經(jīng)排好序的啊,也就是說(shuō)因?yàn)闃?biāo)志位的存在,上面的循環(huán)只會(huì)進(jìn)行一遍,flag沒(méi)有變成1,整個(gè)算法就結(jié)束了,這也就是 O(n) 的來(lái)歷了!

算法的第二次優(yōu)化

   除了上面這個(gè)問(wèn)題,在冒泡排序中還有一個(gè)問(wèn)題存在,就是第 i 趟排的第 i 小或者大的元素已經(jīng)在第 i 位上了,甚至可能第 i-1 位也已經(jīng)歸位了,那么在內(nèi)層循環(huán)的時(shí)候,有這種情況出現(xiàn)就會(huì)導(dǎo)致多余的比較出現(xiàn)。例如:6,4,7,5,1,3,2,當(dāng)我們進(jìn)行第一次排序的時(shí)候,結(jié)果為6,7,5,4,3,2,1,實(shí)際上后面有很多次交換比較都是多余的,因?yàn)闆](méi)有產(chǎn)生交換操作。

  我們用剛剛優(yōu)化過(guò)一次的算法,跑一下這個(gè)數(shù)組。

/**
 * @author jyroy
 * 冒泡排序優(yōu)化第一版
 */
public class BubbleSoerOpt1 {
    public static void main(String[] args) {
        int[] list = {6,4,7,5,1,3,2};
        int len = list.length-1;
        int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設(shè)置一個(gè)標(biāo)志位
            //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上
            for (int j = 0; j < len-i; j++) {
                // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發(fā)生交換,標(biāo)志位置0

                }
                System.out.format("第 %d 遍第%d 趟結(jié)果:", i+1, j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");     
            }

            System.out.format("第 %d 遍最終結(jié)果:", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒(méi)有交換過(guò)元素,則已經(jīng)有序
                return;
            }
                   
        }
    }
}

  運(yùn)行結(jié)果:可以看出,第三趟的多次比較實(shí)際上可以沒(méi)有,因?yàn)橹虚g幾個(gè)位置在第二趟就沒(méi)有過(guò)交換。

  針對(duì)上述的問(wèn)題,我們可以想到,利用一個(gè)標(biāo)志位,記錄一下當(dāng)前第 i 趟所交換的最后一個(gè)位置的下標(biāo),在進(jìn)行第 i+1 趟的時(shí)候,只需要內(nèi)循環(huán)到這個(gè)下標(biāo)的位置就可以了,因?yàn)楹竺嫖恢蒙系脑卦谏弦惶酥袥](méi)有換位,這一次也不可能會(huì)換位置了。基于這個(gè)原因,我們可以進(jìn)一步優(yōu)化我們的代碼。

/**
 * @author jyroy
 * 冒泡排序優(yōu)化第二版
 */
public class BubbleSoerOpt2 {
    public static void main(String[] args) {
        int[] list = {6,4,7,5,1,3,2};
        int len = list.length-1;
        int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值
        int tempPostion = 0;  // 記錄最后一次交換的位置
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設(shè)置一個(gè)標(biāo)志位
            //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上
            for (int j = 0; j < len; j++) {
                // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發(fā)生交換,標(biāo)志位置0
                    tempPostion = j;  //記錄交換的位置
                }
                System.out.format("第 %d 遍第%d 趟結(jié)果:", i+1, j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");     
            }
            len = tempPostion; //把最后一次交換的位置給len,來(lái)縮減內(nèi)循環(huán)的次數(shù)
            System.out.format("第 %d 遍最終結(jié)果:", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒(méi)有交換過(guò)元素,則已經(jīng)有序
                return;
            }
                   
        }
    }
}

  運(yùn)行結(jié)果:

  可以清楚的看到,部分內(nèi)循環(huán)多余的比較已經(jīng)被去掉了,算法得到了進(jìn)一步的優(yōu)化

  因?yàn)樗接邢蓿詫?duì)算法的描述和分析存在一些缺陷,而且選取的例子可能有些不恰當(dāng),大家可以多試一些數(shù)列。

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/75727.html

相關(guān)文章

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

    摘要:之所以把冒泡排序選擇排序插入排序放在一起比較,是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中,冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類(lèi)似插入排序,也分已排序區(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)java版之冒泡排序優(yōu)化

    摘要:外層循環(huán)讓內(nèi)層循環(huán)繼續(xù)排沒(méi)有排序過(guò)的數(shù)組,排序過(guò)的不用再排。那么優(yōu)化后的算法能快多少呢。我們都以數(shù)組長(zhǎng)度為來(lái)計(jì)算傳統(tǒng)冒泡排序步,優(yōu)化后的冒泡排序步。因?yàn)閮?yōu)化后的冒泡排序,每排完一次,最后一個(gè)數(shù)已經(jīng)是最大的,就不需要再比較了。 冒泡排序的時(shí)間用大O表示法是O(N^2). 傳統(tǒng)的冒泡排序: /** * @param total 要排序的數(shù)組長(zhǎng)度 */ public void sort(in...

    xiaoqibTn 評(píng)論0 收藏0
  • qsort()函數(shù)詳解

    摘要:函數(shù)詳解函數(shù)原型函數(shù)的作用及用法函數(shù)的參數(shù)函數(shù)實(shí)例排序一個(gè)整型數(shù)組排序一個(gè)結(jié)構(gòu)體用冒泡排序模擬一個(gè)函數(shù)函數(shù)原型函數(shù)的作用及用法函數(shù)的功能是對(duì)數(shù)組進(jìn)行排序,數(shù)組有個(gè)元素,每個(gè)元素大小為可以排序數(shù)字,字符,結(jié)構(gòu)體等多種類(lèi)型 ...

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

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

0條評(píng)論

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