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

喀什大學 司長安 付珊

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

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

1 排序算法原理

1.1 冒泡排序

假設對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）設置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ù)進行比較，在原來的程序基礎上，在元素交換完成之后，進行r累加，記錄元素交換次數(shù)。

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

int n;

scanf("%d",&n);

int a[n];

這種定義數(shù)組（企圖在程序中途臨時輸入數(shù)組大?。┦遣徽_的[5]140，但是在經(jīng)過多次實踐后發(fā)現(xiàn)，只要是在實際應用中，對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ù)進行排序時，原本的對應關系不能改變，對于這種排序問題生活中需求相對較多，例如學生姓名、成績、學號的排序。

例：對數(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}}排序。要求：每一行元素對應關系不變，第二列由小到大排序，同時當?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ù)應該是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ō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程序設計教程(第二版)[M].北京:清華大學出版社, 2017:117-119.

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

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

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