喀什大學(xué) 司長(zhǎng)安 付珊
對(duì)冒泡排序和選擇排序兩種算法的效率及穩(wěn)定性進(jìn)行分析。通過(guò)交換次數(shù)來(lái)比較排序算法的效率。通過(guò)對(duì)一組具有相關(guān)性數(shù)據(jù)的排序來(lái)比較穩(wěn)定性,得出在對(duì)一組無(wú)序數(shù)據(jù)排序時(shí),選擇法排序次數(shù)少,效率較高,在對(duì)一組相關(guān)數(shù)據(jù)排序時(shí),冒泡法能得到正確排序,穩(wěn)定性強(qiáng),方便在編寫(xiě)程序的過(guò)程中快速選擇一種合適的排序算法。
在C語(yǔ)言程序設(shè)計(jì)中,排序是相對(duì)重要的一項(xiàng)內(nèi)容,在相關(guān)領(lǐng)域?qū)ε判蛩惴ǖ难芯?,有?duì)冒泡排序算法的改進(jìn)提升了效率[1],以及對(duì)冒泡排序、選擇排序工作原理的說(shuō)明[2]。在學(xué)習(xí)過(guò)程中發(fā)現(xiàn)了排序算法冒泡排序和選擇排序效率及穩(wěn)定性的差異,但目前對(duì)此并未進(jìn)一步分析。依據(jù)排序算法原理,通過(guò)比較交換次數(shù)來(lái)比較排序算法的效率,通過(guò)對(duì)一組具有相關(guān)性的數(shù)據(jù)進(jìn)行排序,以此來(lái)分析穩(wěn)定性,并對(duì)此作出分析,得出選擇排序效率更高,冒泡排序穩(wěn)定性更強(qiáng),方便在編寫(xiě)程序的過(guò)程中快速選擇一種合適的排序算法。
假設(shè)對(duì)n個(gè)數(shù)進(jìn)行排序,需要進(jìn)行n-1輪比較,每一輪進(jìn)行n-i次比較,在第i輪排序中,從第一個(gè)數(shù)開(kāi)始,相鄰兩個(gè)數(shù)進(jìn)行比較,如果不滿足排序要求則進(jìn)行數(shù)據(jù)交換。如果滿足排序要求則不進(jìn)行交換,一直到第n-i個(gè)數(shù)與第n+1-i個(gè)數(shù)比較完之后結(jié)束本輪比較。主要原理是把滿足排序要求數(shù)據(jù)進(jìn)行沉底處理,符合排列要求的數(shù)據(jù)沉底之后就不再參與排序[3]。
首先記錄最前面的數(shù)下標(biāo),然后用記錄下標(biāo)數(shù)與后面的數(shù)依次進(jìn)行比較,若滿足排序條件,則記錄滿足排序條件數(shù)的下標(biāo),再用記錄下標(biāo)的數(shù)與后面所有的數(shù)依次進(jìn)行比較,當(dāng)與最后一位數(shù)完成比較,用最前面的數(shù)與最終記錄下標(biāo)的數(shù)進(jìn)行交換。主要思想是先通過(guò)比較挑選出符合排列要求的數(shù)據(jù),然后把最前面的數(shù)據(jù)和符合要求的數(shù)據(jù)進(jìn)行交換[1]。
以由小到大排列順序進(jìn)行分析:
(1)第一輪:第一個(gè)數(shù)和第二個(gè)數(shù)進(jìn)行比較,如果第一個(gè)數(shù)大于第二個(gè)數(shù),那么這兩個(gè)數(shù)進(jìn)行交換,緊接著第二個(gè)數(shù)在和第三個(gè)數(shù)進(jìn)行比較……第n-1個(gè)數(shù)和第n個(gè)數(shù)進(jìn)行比較。一共比較n-1次把最大的數(shù)沉到最后一個(gè)位置(第n個(gè)位置),它將不再參與之后的排序比較。
(2)第i輪:第一個(gè)數(shù)和第二個(gè)數(shù)進(jìn)行比較,如果第一個(gè)數(shù)大于第二個(gè)數(shù),那么這兩個(gè)數(shù)進(jìn)行交換,緊接著第二個(gè)數(shù)在和第三個(gè)數(shù)進(jìn)行比較……第n-i個(gè)數(shù)和第n+1-i個(gè)數(shù)進(jìn)行比較。把這n+1-i個(gè)數(shù)中最大的數(shù)沉到最后一個(gè)位置(第n+1-i個(gè)位置)。
(3)第n-1輪:第一個(gè)數(shù)和第二個(gè)數(shù)進(jìn)行比較,如果第一個(gè)數(shù)大于第二個(gè)數(shù),那么這兩個(gè)數(shù)進(jìn)行交換并終止冒泡排序,如果第一個(gè)數(shù)小于第二個(gè)數(shù)則直接終止冒泡排序。
(4)依次打印出數(shù)組元素[4]。
以由小到大排列順序進(jìn)行分析:
(1)設(shè)置k=0,儲(chǔ)存第一個(gè)數(shù)a[0]的下標(biāo),默認(rèn)為最小值。
(2)用a[k]與后面的數(shù)依次進(jìn)行比較,如果a[k]大于后面的數(shù),那么就把這個(gè)數(shù)的下標(biāo)賦值給k(記錄最小元素下標(biāo))。
(3)把a(bǔ)[0]與a[k]元素值進(jìn)行交換,完成第一次比較。
(4)k=1,重復(fù)第2個(gè)步驟,把a(bǔ)[1]與a[k]元素值進(jìn)行交換,完成第二輪比較。
(5)直到k=n-2,進(jìn)行n-1輪比較之后,完成排序。
(6)依次打印出數(shù)組元素[3]。
例:對(duì)數(shù)組a[10]={15,26,3,2,25,16,23,1,21,32}從小到大排序。
運(yùn)用冒泡排序解決該問(wèn)題:
首先相鄰元素由前至后相互比較,第一輪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
利用兩個(gè)循環(huán)嵌套,完成上述過(guò)程[5]143-145核心代碼如下。
for(j=0; j<9; j++)//進(jìn)行9次循環(huán),實(shí)現(xiàn)9趟比較
for(i=0; i<9-j; i++)//在每一趟中進(jìn)行9-j次比較
if(a[i]>a[i+1])//相鄰兩個(gè)數(shù)進(jìn)行比較
{
t=a[i];a[i]=a[i+1];a[i+1]=t;
}
運(yùn)行結(jié)果如下。
由小到大的順序?yàn)椋?/p>
1 2 3 15 16 21 23 25 26 32
運(yùn)用選擇排序解決該問(wèn)題:選擇排序程序編寫(xiě)[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;
}
運(yùn)行結(jié)果如下。
由小到大的順序?yàn)椋?/p>
1 2 3 15 16 21 23 25 26 32
通過(guò)上面的示例可以看出,不論是冒泡排序還是選擇排序都可以實(shí)現(xiàn)對(duì)一維數(shù)組的排序,也就說(shuō)明在解決一維數(shù)組排序問(wèn)題時(shí),選擇兩種方法其中之一即可。
對(duì)冒泡排序和選擇排序運(yùn)行完成之后元素交換的次數(shù)進(jìn)行比較,在原來(lái)的程序基礎(chǔ)上,在元素交換完成之后,進(jìn)行r累加,記錄元素交換次數(shù)。
在參考資料書(shū)[5]140上有提到:
int n;
scanf("%d",&n);
int a[n];
這種定義數(shù)組(企圖在程序中途臨時(shí)輸入數(shù)組大?。┦遣徽_的[5]140,但是在經(jīng)過(guò)多次實(shí)踐后發(fā)現(xiàn),只要是在實(shí)際應(yīng)用中,對(duì)n賦予一個(gè)確定的整型數(shù)值,那么就可以正常使用這段代碼。運(yùn)行結(jié)果如下。
請(qǐng)輸入數(shù)組元素個(gè)n=5
請(qǐng)輸入n個(gè)元素:
1 6 8 5 7
8 7 6 5 1
選擇排序交換次數(shù)為:4次
由此可見(jiàn),我們不能完全依賴書(shū)籍,要多進(jìn)行嘗試,實(shí)踐出真知。
當(dāng)數(shù)據(jù)個(gè)數(shù)分別為5,10,15,20,25,30,35,40,45,50時(shí),需要交換次數(shù)可以大致做成折線圖,如圖1所示,由折線圖可以清晰地看出,隨著數(shù)據(jù)個(gè)數(shù)的增多,冒泡排序和選擇排序所需要交換的次數(shù)也就越多,在輸入數(shù)據(jù)為輸出數(shù)據(jù)時(shí)冒泡排序交換次數(shù)為折線2,選擇排序交換次數(shù)為折線3,可以看到隨著數(shù)據(jù)的增多選擇排序交換次數(shù)大于冒泡排序,但是相差不是很大。當(dāng)輸入數(shù)據(jù)是輸出數(shù)據(jù)的逆序時(shí),冒泡排序交換次數(shù)為折線1,選擇排序交換次數(shù)為折線3,可以看到隨著數(shù)據(jù)的增多冒泡排序交換次數(shù)遠(yuǎn)大于選擇排序,原因在于冒泡排序在進(jìn)行排序時(shí)都是相鄰元素進(jìn)行比較,如果不滿足排序要求就進(jìn)行交換,而選擇排序則不同,選擇排序則是記錄最前面的元素下標(biāo),然后用記錄下標(biāo)的元素和后面的元素進(jìn)行比較,當(dāng)遇到滿足條件的元素時(shí)只記錄下標(biāo),這一輪都比較完之后再去進(jìn)行元素交換,極大地減少了數(shù)據(jù)所需交換的次數(shù),從而也就提高了算法效率。
圖1 冒泡排序和選擇排序數(shù)據(jù)交換次數(shù)Fig.1 Number of data exchanges between bubble sorting and select sorting
要求:多列數(shù)據(jù)每一列都按照一定順序排列,生活中這種排序需求相對(duì)較少。
例:對(duì)數(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ù)運(yùn)用兩次冒泡排序解決該問(wèn)題,核心程序如下。
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;
}
運(yùn)行結(jié)果如下。
排序后順序?yàn)椋?/p>
{1,60},{2,70},{3,75},{6,80},{11,85},{12,85},{15,85},{21,95},{23,95},{25,95}
連續(xù)運(yùn)用兩次選擇排序解決該問(wèn)題,核心程序如下。
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;
}
運(yùn)行結(jié)果如下。
排序后順序?yàn)椋?/p>
{1,60},{2,70},{3,75},{6,80},{11,85},{12,85},{15,85},{21,95},{23,95},{25,95}
由此可見(jiàn)不論是連續(xù)使用冒泡排序還是連續(xù)使用選擇排序,都可以實(shí)現(xiàn)二維數(shù)組無(wú)捆綁排序。
要求:多列數(shù)據(jù)中部分列的數(shù)據(jù)進(jìn)行排序時(shí),原本的對(duì)應(yīng)關(guān)系不能改變,對(duì)于這種排序問(wèn)題生活中需求相對(duì)較多,例如學(xué)生姓名、成績(jī)、學(xué)號(hào)的排序。
例:對(duì)數(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}}排序。要求:每一行元素對(duì)應(yīng)關(guān)系不變,第二列由小到大排序,同時(shí)當(dāng)?shù)诙袛?shù)據(jù)相同時(shí),第一列也要按照由小到大排序。
首先連續(xù)運(yùn)用兩次冒泡排序解決該問(wèn)題,核心程序如下。
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;
}
運(yùn)行結(jié)果如圖2所示。
圖2 連續(xù)運(yùn)用兩次冒泡排序運(yùn)行結(jié)果Fig.2 Results of two consecutive bubble sorting runs
在這里我們可以看到,連續(xù)運(yùn)用兩次冒泡排序,第二列按照由小到大排序,當(dāng)?shù)诙袛?shù)據(jù)相等時(shí),第一列數(shù)據(jù)也是按照由小到大順序排列的,結(jié)果是正確的。
連續(xù)運(yùn)用兩次選擇排序來(lái)解決該問(wèn)題,核心程序如下。
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;
}
運(yùn)行結(jié)果如圖3所示。
圖3 連續(xù)運(yùn)用兩次選擇排序運(yùn)行結(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ù)是錯(cuò)誤的。
當(dāng)進(jìn)行二維數(shù)組的部分列數(shù)據(jù)捆綁排序時(shí),冒泡排序可以得出正確的結(jié)果,而選擇排序則不能得出正確的結(jié)果,其原因在于兩種排序算法的穩(wěn)定性不同。
冒泡排序進(jìn)行比較時(shí)是相鄰兩項(xiàng)進(jìn)行比較,不符合排序要求就進(jìn)行交換,保證了原先在前面的元素交換之后仍然在前面。而選擇排序則只是記錄下標(biāo),在一輪比較完之后再進(jìn)行數(shù)值交換,這樣就有可能會(huì)導(dǎo)致原先在前面的元素被交換到了后面。在這里用上面的例子進(jìn)行分析:
上面通過(guò)對(duì)二維數(shù)組無(wú)捆綁排序,我們了解了不論是選擇排序還是冒泡排序都可以完成對(duì)數(shù)據(jù)第一列的正確排序,這里直接從第二列的排序開(kāi)始分析。
首先,我們先對(duì)選擇排序錯(cuò)誤原因進(jìn)行分析,第一輪排序如表2所示。
表2 選擇排序第一輪比較結(jié)果Tab.2 Comparison results of the first round of selection ranking
第一輪比較最終確定a[7][1]是最小值,之后把a(bǔ)[0][0]與a[7][0]、a[0][1]與a[7][1]進(jìn)行對(duì)換,如表3所示。
表3 第一輪交換后元素位置Tab.3 Element positions after the first round of swapping
這里可以看出第一次交換之后原本在前面的{1,95}被交換到{11,95}{12,95}后面了,產(chǎn)生這樣的原因是,選擇排序進(jìn)行比較時(shí),先進(jìn)行下標(biāo)的記錄,最后最前面的元素只和記錄下標(biāo)的元素進(jìn)行交換。但是這樣交換就很容易出現(xiàn),把原本在前面的元素交換到后面,從而導(dǎo)致選擇排序的穩(wěn)定性低。
但冒泡排序則與選擇排序不同,冒泡排序是每一輪比較排序時(shí),都是相鄰兩個(gè)元素進(jìn)行得比較,如果不滿足排序條件,進(jìn)行元素交換,即使當(dāng)冒泡排序遇到連續(xù)相同元素時(shí),也是先相鄰項(xiàng)兩兩比較,比較之后相同元素中最后一個(gè)元素再與后面的元素進(jìn)行比較,極大地保
…………證了冒泡排序的穩(wěn)定性。
C語(yǔ)言中排序方法多種多樣,選擇排序和冒泡排序都有著上手難度低和應(yīng)用相對(duì)廣泛的特點(diǎn),比較適合初學(xué)者進(jìn)行學(xué)習(xí),在解決一些相對(duì)簡(jiǎn)單的排序問(wèn)題也相對(duì)實(shí)用,但是每一種排序方法都有著不同的優(yōu)缺點(diǎn),當(dāng)我們?cè)诮鉀Q實(shí)際性問(wèn)題時(shí),就需要根據(jù)這些排序算法的優(yōu)缺點(diǎn)來(lái)合理地運(yùn)用排序算法。以上是對(duì)于冒泡排序和選擇排序的效率和穩(wěn)定性差別比較,是經(jīng)過(guò)多次實(shí)踐而來(lái)的,今后也會(huì)繼續(xù)思考如何對(duì)選擇排序進(jìn)行改進(jìn),使其既能保證效率又可以保證穩(wěn)定性。
引用
[1]陳穎頻,王靈芝,吳金鋒,等.基于選擇思想和反序標(biāo)識(shí)的改進(jìn)冒泡排序算法[J].泉州師范學(xué)院學(xué)報(bào),2014,32(6):89-93.
[2]毛廣敏.常用C語(yǔ)言排序算法解析[J].軟件導(dǎo)刊,2012,11(11): 51-54.
[3]王娟勤.C程序設(shè)計(jì)教程(第二版)[M].北京:清華大學(xué)出版社, 2017:117-119.
[4]王一萍,李長(zhǎng)榮,梁偉.C語(yǔ)言編程從入門(mén)到實(shí)踐[M].北京:中國(guó)水利水電出版社,2021:154-156+252-257.
[5]譚浩強(qiáng).C程序設(shè)計(jì)(第五版)[M].北京:清華大學(xué)出版社,2017.
[6]明日科技.C語(yǔ)言從入門(mén)到精通(第三版)[M].北京:清華大學(xué)出版社,2017:160-164.
數(shù)字技術(shù)與應(yīng)用2022年12期