亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        冒泡排序和選擇排序效率及穩(wěn)定性分析*

        2023-01-03 13:37:22喀什大學司長安付珊
        關(guān)鍵詞:數(shù)組個數(shù)排序

        喀什大學 司長安 付珊

        對冒泡排序和選擇排序兩種算法的效率及穩(wěn)定性進行分析。通過交換次數(shù)來比較排序算法的效率。通過對一組具有相關(guān)性數(shù)據(jù)的排序來比較穩(wěn)定性,得出在對一組無序數(shù)據(jù)排序時,選擇法排序次數(shù)少,效率較高,在對一組相關(guān)數(shù)據(jù)排序時,冒泡法能得到正確排序,穩(wěn)定性強,方便在編寫程序的過程中快速選擇一種合適的排序算法。

        在C語言程序設(shè)計中,排序是相對重要的一項內(nèi)容,在相關(guān)領(lǐng)域?qū)ε判蛩惴ǖ难芯?,有對冒泡排序算法的改進提升了效率[1],以及對冒泡排序、選擇排序工作原理的說明[2]。在學習過程中發(fā)現(xiàn)了排序算法冒泡排序和選擇排序效率及穩(wěn)定性的差異,但目前對此并未進一步分析。依據(jù)排序算法原理,通過比較交換次數(shù)來比較排序算法的效率,通過對一組具有相關(guān)性的數(shù)據(jù)進行排序,以此來分析穩(wěn)定性,并對此作出分析,得出選擇排序效率更高,冒泡排序穩(wěn)定性更強,方便在編寫程序的過程中快速選擇一種合適的排序算法。

        1 排序算法原理

        1.1 冒泡排序

        假設(shè)對n個數(shù)進行排序,需要進行n-1輪比較,每一輪進行n-i次比較,在第i輪排序中,從第一個數(shù)開始,相鄰兩個數(shù)進行比較,如果不滿足排序要求則進行數(shù)據(jù)交換。如果滿足排序要求則不進行交換,一直到第n-i個數(shù)與第n+1-i個數(shù)比較完之后結(jié)束本輪比較。主要原理是把滿足排序要求數(shù)據(jù)進行沉底處理,符合排列要求的數(shù)據(jù)沉底之后就不再參與排序[3]。

        1.2 選擇排序

        首先記錄最前面的數(shù)下標,然后用記錄下標數(shù)與后面的數(shù)依次進行比較,若滿足排序條件,則記錄滿足排序條件數(shù)的下標,再用記錄下標的數(shù)與后面所有的數(shù)依次進行比較,當與最后一位數(shù)完成比較,用最前面的數(shù)與最終記錄下標的數(shù)進行交換。主要思想是先通過比較挑選出符合排列要求的數(shù)據(jù),然后把最前面的數(shù)據(jù)和符合要求的數(shù)據(jù)進行交換[1]。

        2 一維數(shù)組排序

        2.1 冒泡排序?qū)崿F(xiàn)

        以由小到大排列順序進行分析:

        (1)第一輪:第一個數(shù)和第二個數(shù)進行比較,如果第一個數(shù)大于第二個數(shù),那么這兩個數(shù)進行交換,緊接著第二個數(shù)在和第三個數(shù)進行比較……第n-1個數(shù)和第n個數(shù)進行比較。一共比較n-1次把最大的數(shù)沉到最后一個位置(第n個位置),它將不再參與之后的排序比較。

        (2)第i輪:第一個數(shù)和第二個數(shù)進行比較,如果第一個數(shù)大于第二個數(shù),那么這兩個數(shù)進行交換,緊接著第二個數(shù)在和第三個數(shù)進行比較……第n-i個數(shù)和第n+1-i個數(shù)進行比較。把這n+1-i個數(shù)中最大的數(shù)沉到最后一個位置(第n+1-i個位置)。

        (3)第n-1輪:第一個數(shù)和第二個數(shù)進行比較,如果第一個數(shù)大于第二個數(shù),那么這兩個數(shù)進行交換并終止冒泡排序,如果第一個數(shù)小于第二個數(shù)則直接終止冒泡排序。

        (4)依次打印出數(shù)組元素[4]。

        2.2 選擇排序?qū)崿F(xiàn)

        以由小到大排列順序進行分析:

        (1)設(shè)置k=0,儲存第一個數(shù)a[0]的下標,默認為最小值。

        (2)用a[k]與后面的數(shù)依次進行比較,如果a[k]大于后面的數(shù),那么就把這個數(shù)的下標賦值給k(記錄最小元素下標)。

        (3)把a[0]與a[k]元素值進行交換,完成第一次比較。

        (4)k=1,重復第2個步驟,把a[1]與a[k]元素值進行交換,完成第二輪比較。

        (5)直到k=n-2,進行n-1輪比較之后,完成排序。

        (6)依次打印出數(shù)組元素[3]。

        例:對數(shù)組a[10]={15,26,3,2,25,16,23,1,21,32}從小到大排序。

        運用冒泡排序解決該問題:

        首先相鄰元素由前至后相互比較,第一輪a[0]與a[1]比較,a[1]與a[2]比較,a[2]與a[3]比較,a[3]與a[4]比較,a[4]與a[5]比較,a[5]與a[6]比較,a[6]與a[7]比較,a[7]與a[8]比較,a[8]與a[9]比較;第二輪a[0]與a[1]比較,a[1]與a[2]比較,a[2]與a[3]比較,a[3]與a[4]比較,a[4]與a[5]比較,a[5]與a[6]比較,a[6]與a[7]比較,a[7]與a[8]比較;第三輪a[0]與a[1]比較,a[1]與a[2]比較,a[2]與a[3]比較,a[3]與a[4]比較,a[4]與a[5]比較,a[5]與a[6]比較,a[6]與a[7]比較……第九輪a[0]與a[1]比較[3],如表1所示。

        表1 冒泡排序相互比較元素Tab.1 Bubble sorting compares elements with each other

        利用兩個循環(huán)嵌套,完成上述過程[5]143-145核心代碼如下。

        for(j=0; j<9; j++)//進行9次循環(huán),實現(xiàn)9趟比較

        for(i=0; i<9-j; i++)//在每一趟中進行9-j次比較

        if(a[i]>a[i+1])//相鄰兩個數(shù)進行比較

        {

        t=a[i];a[i]=a[i+1];a[i+1]=t;

        }

        運行結(jié)果如下。

        由小到大的順序為:

        1 2 3 15 16 21 23 25 26 32

        運用選擇排序解決該問題:選擇排序程序編寫[6]核心程序如下。

        for(i=0; i<9; i++)

        {

        k=i;

        for(j=i+1; j<10; j++)

        if(a[k]>a[j])

        k=j;

        t=a[i];a[i]=a[k];a[k]=t;

        }

        運行結(jié)果如下。

        由小到大的順序為:

        1 2 3 15 16 21 23 25 26 32

        2.3 小結(jié)

        通過上面的示例可以看出,不論是冒泡排序還是選擇排序都可以實現(xiàn)對一維數(shù)組的排序,也就說明在解決一維數(shù)組排序問題時,選擇兩種方法其中之一即可。

        2.4 冒泡排序和選擇排序效率比較

        對冒泡排序和選擇排序運行完成之后元素交換的次數(shù)進行比較,在原來的程序基礎(chǔ)上,在元素交換完成之后,進行r累加,記錄元素交換次數(shù)。

        在參考資料書[5]140上有提到:

        int n;

        scanf("%d",&n);

        int a[n];

        這種定義數(shù)組(企圖在程序中途臨時輸入數(shù)組大?。┦遣徽_的[5]140,但是在經(jīng)過多次實踐后發(fā)現(xiàn),只要是在實際應(yīng)用中,對n賦予一個確定的整型數(shù)值,那么就可以正常使用這段代碼。運行結(jié)果如下。

        請輸入數(shù)組元素個n=5

        請輸入n個元素:

        1 6 8 5 7

        8 7 6 5 1

        選擇排序交換次數(shù)為:4次

        由此可見,我們不能完全依賴書籍,要多進行嘗試,實踐出真知。

        當數(shù)據(jù)個數(shù)分別為5,10,15,20,25,30,35,40,45,50時,需要交換次數(shù)可以大致做成折線圖,如圖1所示,由折線圖可以清晰地看出,隨著數(shù)據(jù)個數(shù)的增多,冒泡排序和選擇排序所需要交換的次數(shù)也就越多,在輸入數(shù)據(jù)為輸出數(shù)據(jù)時冒泡排序交換次數(shù)為折線2,選擇排序交換次數(shù)為折線3,可以看到隨著數(shù)據(jù)的增多選擇排序交換次數(shù)大于冒泡排序,但是相差不是很大。當輸入數(shù)據(jù)是輸出數(shù)據(jù)的逆序時,冒泡排序交換次數(shù)為折線1,選擇排序交換次數(shù)為折線3,可以看到隨著數(shù)據(jù)的增多冒泡排序交換次數(shù)遠大于選擇排序,原因在于冒泡排序在進行排序時都是相鄰元素進行比較,如果不滿足排序要求就進行交換,而選擇排序則不同,選擇排序則是記錄最前面的元素下標,然后用記錄下標的元素和后面的元素進行比較,當遇到滿足條件的元素時只記錄下標,這一輪都比較完之后再去進行元素交換,極大地減少了數(shù)據(jù)所需交換的次數(shù),從而也就提高了算法效率。

        圖1 冒泡排序和選擇排序數(shù)據(jù)交換次數(shù)Fig.1 Number of data exchanges between bubble sorting and select sorting

        3 二維數(shù)組排序

        3.1 多列數(shù)據(jù)無捆綁排序

        要求:多列數(shù)據(jù)每一列都按照一定順序排列,生活中這種排序需求相對較少。

        例:對數(shù)組int a[10][2]={{1,95},{2,85},{25,80},{3,75},{15,85},{11,95},{12,95},{23,85},{21,60},{6,70}}第一列第二列分別排序。

        首先連續(xù)運用兩次冒泡排序解決該問題,核心程序如下。

        for(j=0; j<2; j++)

        for(r=0; r<9; r++)

        for(i=0; i<9-r; i++)

        if(a[i][j]>a[i+1][j])

        {

        t=a[i][j];a[i][j]=a[i+1][j];a[i+1][j]=t;

        }

        運行結(jié)果如下。

        排序后順序為:

        {1,60},{2,70},{3,75},{6,80},{11,85},{12,85},{15,85},{21,95},{23,95},{25,95}

        連續(xù)運用兩次選擇排序解決該問題,核心程序如下。

        for(j=0; j<2; j++)

        for(i=0; i<9; i++)

        {

        k=i;

        for(r=i+1; r<10; r++)

        if(a[k][j]>a[r][j])

        k=r;

        t=a[i][j];a[i][j]=a[k][j];a[k][j]=t;

        }

        運行結(jié)果如下。

        排序后順序為:

        {1,60},{2,70},{3,75},{6,80},{11,85},{12,85},{15,85},{21,95},{23,95},{25,95}

        3.2 小結(jié)

        由此可見不論是連續(xù)使用冒泡排序還是連續(xù)使用選擇排序,都可以實現(xiàn)二維數(shù)組無捆綁排序。

        3.3 部分列數(shù)據(jù)捆綁排序

        要求:多列數(shù)據(jù)中部分列的數(shù)據(jù)進行排序時,原本的對應(yīng)關(guān)系不能改變,對于這種排序問題生活中需求相對較多,例如學生姓名、成績、學號的排序。

        例:對數(shù)組int a[10][2]={{1,95},{2,85},{25,80},{3,75},{15,85},{11,95},{12,95},{23,85},{21,60},{6,70}}排序。要求:每一行元素對應(yīng)關(guān)系不變,第二列由小到大排序,同時當?shù)诙袛?shù)據(jù)相同時,第一列也要按照由小到大排序。

        首先連續(xù)運用兩次冒泡排序解決該問題,核心程序如下。

        for(j=0; j<2; j++)

        for(r=0; r<9; r++)

        for(i=0; i<9-r; i++)

        if(a[i][j]>a[i+1][j])

        {

        t=a[i][0];a[i][0]=a[i+1][0];a[i+1][0]=t;

        t=a[i][1];a[i][1]=a[i+1][1];a[i+1][1]=t;

        }

        運行結(jié)果如圖2所示。

        圖2 連續(xù)運用兩次冒泡排序運行結(jié)果Fig.2 Results of two consecutive bubble sorting runs

        在這里我們可以看到,連續(xù)運用兩次冒泡排序,第二列按照由小到大排序,當?shù)诙袛?shù)據(jù)相等時,第一列數(shù)據(jù)也是按照由小到大順序排列的,結(jié)果是正確的。

        連續(xù)運用兩次選擇排序來解決該問題,核心程序如下。

        for(j=0; j<2; j++)

        for(i=0; i<9; i++)

        {

        k=i;

        for(r=i+1; r<10; r++)

        if(a[k][j]>a[r][j])

        k=r;

        t=a[i][0];a[i][0]=a[k][0];a[k][0]=t;

        t=a[i][1];a[i][1]=a[k][1];a[k][1]=t;

        }

        運行結(jié)果如圖3所示。

        圖3 連續(xù)運用兩次選擇排序運行結(jié)果Fig.3 Results of two consecutive selection sorting runs

        在這里我們可以看到連續(xù)用兩次選擇排序第二列數(shù)據(jù)由小到大排序,但是第二列三行連續(xù)85和95正確的第一列數(shù)據(jù)應(yīng)該是2、15、23、1、11、12,顯然選擇排序輸出的數(shù)據(jù)是錯誤的。

        3.4 小結(jié)

        當進行二維數(shù)組的部分列數(shù)據(jù)捆綁排序時,冒泡排序可以得出正確的結(jié)果,而選擇排序則不能得出正確的結(jié)果,其原因在于兩種排序算法的穩(wěn)定性不同。

        4 冒泡排序和選擇排序穩(wěn)定性比較

        冒泡排序進行比較時是相鄰兩項進行比較,不符合排序要求就進行交換,保證了原先在前面的元素交換之后仍然在前面。而選擇排序則只是記錄下標,在一輪比較完之后再進行數(shù)值交換,這樣就有可能會導致原先在前面的元素被交換到了后面。在這里用上面的例子進行分析:

        上面通過對二維數(shù)組無捆綁排序,我們了解了不論是選擇排序還是冒泡排序都可以完成對數(shù)據(jù)第一列的正確排序,這里直接從第二列的排序開始分析。

        首先,我們先對選擇排序錯誤原因進行分析,第一輪排序如表2所示。

        表2 選擇排序第一輪比較結(jié)果Tab.2 Comparison results of the first round of selection ranking

        第一輪比較最終確定a[7][1]是最小值,之后把a[0][0]與a[7][0]、a[0][1]與a[7][1]進行對換,如表3所示。

        表3 第一輪交換后元素位置Tab.3 Element positions after the first round of swapping

        這里可以看出第一次交換之后原本在前面的{1,95}被交換到{11,95}{12,95}后面了,產(chǎn)生這樣的原因是,選擇排序進行比較時,先進行下標的記錄,最后最前面的元素只和記錄下標的元素進行交換。但是這樣交換就很容易出現(xiàn),把原本在前面的元素交換到后面,從而導致選擇排序的穩(wěn)定性低。

        但冒泡排序則與選擇排序不同,冒泡排序是每一輪比較排序時,都是相鄰兩個元素進行得比較,如果不滿足排序條件,進行元素交換,即使當冒泡排序遇到連續(xù)相同元素時,也是先相鄰項兩兩比較,比較之后相同元素中最后一個元素再與后面的元素進行比較,極大地保

        …………證了冒泡排序的穩(wěn)定性。

        5 結(jié)語

        C語言中排序方法多種多樣,選擇排序和冒泡排序都有著上手難度低和應(yīng)用相對廣泛的特點,比較適合初學者進行學習,在解決一些相對簡單的排序問題也相對實用,但是每一種排序方法都有著不同的優(yōu)缺點,當我們在解決實際性問題時,就需要根據(jù)這些排序算法的優(yōu)缺點來合理地運用排序算法。以上是對于冒泡排序和選擇排序的效率和穩(wěn)定性差別比較,是經(jīng)過多次實踐而來的,今后也會繼續(xù)思考如何對選擇排序進行改進,使其既能保證效率又可以保證穩(wěn)定性。

        引用

        [1]陳穎頻,王靈芝,吳金鋒,等.基于選擇思想和反序標識的改進冒泡排序算法[J].泉州師范學院學報,2014,32(6):89-93.

        [2]毛廣敏.常用C語言排序算法解析[J].軟件導刊,2012,11(11): 51-54.

        [3]王娟勤.C程序設(shè)計教程(第二版)[M].北京:清華大學出版社, 2017:117-119.

        [4]王一萍,李長榮,梁偉.C語言編程從入門到實踐[M].北京:中國水利水電出版社,2021:154-156+252-257.

        [5]譚浩強.C程序設(shè)計(第五版)[M].北京:清華大學出版社,2017.

        [6]明日科技.C語言從入門到精通(第三版)[M].北京:清華大學出版社,2017:160-164.

        猜你喜歡
        數(shù)組個數(shù)排序
        JAVA稀疏矩陣算法
        電腦報(2022年13期)2022-04-12 00:32:38
        排序不等式
        怎樣數(shù)出小正方體的個數(shù)
        JAVA玩轉(zhuǎn)數(shù)學之二維數(shù)組排序
        電腦報(2020年24期)2020-07-15 06:12:41
        恐怖排序
        等腰三角形個數(shù)探索
        怎樣數(shù)出小木塊的個數(shù)
        節(jié)日排序
        怎樣數(shù)出小正方體的個數(shù)
        刻舟求劍
        兒童繪本(2018年5期)2018-04-12 16:45:32
        国产亚洲av另类一区二区三区| 精品午夜一区二区三区久久| 亚洲香蕉av一区二区蜜桃| 成人性生交大全免费看| 无码人妻一区二区三区免费视频 | 国产自拍精品视频免费观看| 亚洲字幕中文综合久久| 无人高清电视剧在线观看| 亚洲人成综合网站在线| 国产高清精品在线二区| 亚洲精选自偷拍一区二| 美女张开腿让男人桶爽| 亚洲国产成人久久一区www妖精 | 亚洲一区二区三区在线最新 | 国产av一卡二卡日韩av| 人妻无码一区二区不卡无码av| 香蕉久久夜色精品国产2020| 精品国产亚洲av成人一区| 精品国产亚洲av高清大片| 97人人模人人爽人人少妇| 国产免费专区| 最新中文字幕乱码在线| 久久久精品中文字幕麻豆发布| 欧美日韩一区二区三区自拍| 亚洲成aⅴ人片在线观看天堂无码| 日本女优久久精品久久| av狠狠色丁香婷婷综合久久| 欧美另类视频在线| 午夜精品一区二区三区av免费| 亚洲中文字幕人妻av在线| 婷婷久久久亚洲欧洲日产国码av| 丝袜美腿网站一区二区| 国产一区二区三区免费视| 亚洲av无码久久精品色欲| 少妇三级欧美久久| 粗大挺进孕妇人妻在线| 日韩精品无码熟人妻视频| 国产亚洲精品第一综合麻豆| 中文字幕一区二区三区.| 一二三区无线乱码中文在线| 一本一道av无码中文字幕|