喀什大學(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ò)程中快速選擇一種合適的排序算法。

1 排序算法原理

1.1 冒泡排序

假設(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]。

1.2 選擇排序

首先記錄最前面的數(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]。

2 一維數(shù)組排序

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

以由小到大排列順序進(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]。

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

以由小到大排列順序進(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

2.3 小結(jié)

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

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

對(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

3 二維數(shù)組排序

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

要求：多列數(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}

3.2 小結(jié)

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

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

要求：多列數(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ò)誤的。

3.4 小結(jié)

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

4 冒泡排序和選擇排序穩(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)定性。

5 結(jié)語(yǔ)

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.