• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 有意思的算法(一)----冒泡排序

        冒泡排序的基本思想是:每次比較兩個相鄰的元素,如果它們的順序錯誤就把他們交換過來。

        下面舉一個具體的例子來介紹一下冒泡排序。

    這里寫圖片描述

        有12,35,99,18,76五個數進行從大到小的排序,既然是從大到小排序,也就是說越小的越靠后,可不要把這句當成廢話,這可是最關鍵的地方!

        首先比較第1位和第2位的數字,第1位是12,第2位是35,12<35,根據越小的越靠后的原則,交換兩個數,交換之后的順序是:35,12,99,18,76。

        按照剛才的說法,依次比較第2位和第3位,第3位和第4位,第4位和第5位,結果分別如下:

    12,35,99,18,76
    35,12,99,18,76
    35,99,12,18,76
    35,99,18,12,76
    35,99,18,76,12

        經過4次比較,最小的一個數已經就位了(注意12的移動過程),很有意思,咱們這么來看12的移動過程,看了下面的圖片你就會更明白:

    這里寫圖片描述

        整個過程就如同是一個氣泡,一步一步往后“翻滾”,直到最后一位,所以這個排序有一個很好聽的名字“冒泡排序”

        可以這么說,我們的排序只將5個書中最小的一個歸位了,沒將一個數歸位我們稱其為“一趟”

        下面接著上面的“第一趟”,開始“第二趟”,在第二趟中有一點需要注意的是,由于最小的一位已經歸位了,我們只需要找出第二小的數來就可以了,也就是說在本趟中,只需比較到第3位和第4位就可以了,第5位已經是最小的了,就不需要比較了。

        “第三趟”的結果是:

    99,76,35,18,12

        到了最后一趟“第四趟”。有的人就要問了,這還用比較么,這結果不已經出來了么?當然,這里純屬巧合,要是用別的數試一試可能就不是了。

    冒泡排序的原理:每一趟只能確定將一個數歸位。即第一趟只能將第末位(第5位)上的數歸位,第二趟只能將倒數第2位上的數(第4位)歸位,第三趟只能將倒數第3位上的數(第3位)歸位,可是現在前面還有兩個位置上的數沒有歸位,所以依然要進行“第四趟”

        下面咱們總結一下:如果有n個數進行排序,只需將n-1個數歸位,也就是說要進行n-1趟操作。而“每一趟”都需要從第一位開始進行相鄰的兩個數的比較,將較小的一個數放在后面,比較完畢后諾以為繼續比較下面兩個相鄰數的大小,重復此步驟,知道最后一個尚未歸位的數,已經歸位的書就不需要在進行比較了。

        下面是具體的實現代碼:

    #include <stdio.h>
    int main()
    {
        int a[100],i,j,t,n;
        scanf("%d",&n);  '''輸入一個數n,表示接下來又n個數'''
        for(i=1;i<=n;i++)  '''循環讀入n個數到數組a中'''
            scanf("%d",&a[i]);
    
        '''冒泡排序的核心部分'''
        for(i=1;i<=n-1;i++)    '''n個數排序,只用進行n-1趟'''
        {
            for(j=1;j<=n-i;j++)  '''從第1位開始比較知道最有一個尚未歸位的數,想一想為什么到n-i就可以了'''
            {
                if(a[j]<a[j+1])   '''比較兩個數的大小'''
                {t=a[j];a[j]=a[j+i];a[j+i]=t;}
            }
        }
    
        for(i=1;i<=n;i++)  '''輸出結果'''
            printf("%d ",a[i]);
    
        getchar();getchar();
        return 0;
    }

        冒泡排序的核心部分是雙重嵌套循環。不難看出冒泡排序的時間復雜度是O(N2)

    轉載請注明出處:http://blog.csdn.net/zlts000/article/details/49515505

    版權聲明:本文為weixin_34296641原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/weixin_34296641/article/details/90630218

    智能推薦

    有意思的編程思考題

    1.有5個人坐在一起,問第五個人多少歲?他說比第4個人大2歲。問第4個人歲數,他說比第3個人大2歲。問第三個人,又說比第2人大兩歲。問第2個人,說比第一個人大兩歲。最后問第一個人,他說是10歲。請問第五個人多大? (用編程實現并說出思路) 思路:不知道第五個人多少歲,但從第五個人到第一個人之間都有聯系,知道其中一個人的年齡,便知道所有人的年齡,根據規律,每個人相差2歲,可以用for循環來簡單的編程...

    非常有意思的Flowlet

    周五了解到一個叫做Flowlet的東西,比較有意思。大體上說來,它是由一個問題而引出的一個解決方案,由于理解還不夠深入,所以也暫時只能這么說。   我先從問題說起。 ISP的動態負載均衡 由于公共骨干網上流量的不確定性,每一條鏈路的負載不盡相同,為了保證總帶寬的最佳利用率,ISP往往會做一些動態負載均衡的策略。如下圖所示: 時刻1: 時刻2: packet負載均衡和flow負載...

    HashMap中有意思的方法!

    關于HashMap的源碼,網上文章多如沙海,本文只關注其中幾個有意思的地方! JDK版本: 1.8.0_151 知識點盤點 1.  的二進制表示,只有最高位是1,其余的都是0,而 則全部二進制位都是1,如下圖所示   2.  Java中的位運算符: &: 位與操作,全1則1,有0則0 | : 位或操作, 有1則1,全0則0 ^:&...

    數組刪除其中某個對象的方法

    數組刪除其中的對象或元素,在前端是比較常見的需求。 我現在比較常用的方法如下: 這種方法只適合刪除具有唯一標識的對象。 有沒有想要脫單的小伙伴,加入我們的脫單星球,認識更多優秀的小哥哥小姐姐 特此聲明,星球是免費的,但是創建星球的時候說是必須輸入金額,所以只能先私聊,我再加你免費加入!...

    圖床搭建以及圖床工具的使用

    為什么要用圖床和圖床工具? 比較下面三種md中的圖片url地址(均免費),你會使用哪一種? 選1?由于是本地路徑,文檔分享后給其他人打開后很可能顯示圖片加載失敗。 選2?雖然分享后可以顯示圖片,但能保證加載速度? 選3?我肯定選這種,即兼容2的瀏覽器訪問,又能保證訪問速度。 這樣就可以回答上面的問題了!保證瀏覽器訪問要用圖床,保證加載速度要用圖床工具,又不花錢想想就開心。 除此之外本篇博客還會講解...

    猜你喜歡

    并發編程理論篇

    一、必備知識回顧 計算機又叫電腦,即通電的大腦,發明計算機是為了讓他通電之后能夠像人一樣去工作,并且它比人的工作效率更高,因為可以24小時不間斷 計算機五大組成部分 控制器 運算器 存儲器 輸入設備 輸出設備 計算機的核心真正干活的是CPU(控制器+運算器=中央處理器) 程序要想被計算機運行,它的代碼必須要先由硬盤讀到內存,之后cpu取指再執行 并發 看起來像同時運行的就可以稱之為并發 并行 真正...

    Java LinkedHashMap

    Java LinkedHashMap 前言 Map是我們在實際使用過程中常用的集合,HashMap在Java的實際開發中出鏡率很高,它通過hash算法實現了高效的非線程安全的集合,它有一個缺點就是,用戶插入集合的數據時無序,在我們需要一些有序的map的時候,我們就需要引入另外一個集合:LinkedHashMap。 LinkedHashMap是一個有序的非線程安全的集合,它是HashMap的子類,基...

    Spark Streaming處理文件(本地文件以及hdfs上面的文件)

    標題介紹文件流之前先介紹一下Dstream 下面是來自官網一段的說明,Discretized Streams或DStream是Spark Streaming提供的基本抽象。它表示連續的數據流,可以是從源接收的輸入數據流,也可以是通過轉換輸入流生成的已處理數據流。在內部,DStream由一系列連續的RDD表示,這是Spark對不可變的分布式數據集的抽象(有關更多詳細信息,請參見Spark編程指南)。...

    《痞子衡嵌入式半月刊》 第 8 期

    痞子衡嵌入式半月刊: 第 8 期 這里分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農歷年分二十四節氣,希望在每個交節之日準時發布一期。 本期刊是開源項目(GitHub: JayHeng/pzh-mcu-bi-weekly),歡迎提交 issue,投稿或推薦你知道的嵌入式那些事兒。 上期回顧 :《痞子衡嵌入式半月刊: 第 7 期》 嘮兩句 今天是小滿,小滿節氣意味著進入了大幅降水的雨季。痞子...

    (C++)二叉樹的線索化 / 線索二叉樹

    好久不見,朋友們!雖然我知道沒人看我的博客,但我還是想叨逼叨一下。啊,好久沒編程了(其實也就一周沒編),但你們知道,程序員一天不編程那能叫程序員么???雖然我不是程序員哈哈哈哈哈,但還是要有基本素養嘛。 繼續寫二叉樹,給自己立一個flag,就是這幾天要寫完之前沒做完的幾道題,和二叉樹紅黑樹各種樹之類的~~雖然有這個flag,但我還是很實誠地遵從自己的內心,買了一張明天的電影票,等我回來告訴你們好不...

    精品国产乱码久久久久久蜜桃不卡