冒泡排序和選擇排序效率及穩定性分析＊

喀什大學 司長安 付珊

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

在C語言程序設計中，排序是相對重要的一項內容，在相關領域對排序算法的研究，有對冒泡排序算法的改進提升了效率[1]，以及對冒泡排序、選擇排序工作原理的說明[2]。在學習過程中發現了排序算法冒泡排序和選擇排序效率及穩定性的差異，但目前對此并未進一步分析。依據排序算法原理，通過比較交換次數來比較排序算法的效率，通過對一組具有相關性的數據進行排序，以此來分析穩定性，并對此作出分析，得出選擇排序效率更高，冒泡排序穩定性更強，方便在編寫程序的過程中快速選擇一種合適的排序算法。

1 排序算法原理

1.1 冒泡排序

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

1.2 選擇排序

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

2 一維數組排序

2.1 冒泡排序實現

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

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

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

（3）第n-1輪：第一個數和第二個數進行比較，如果第一個數大于第二個數，那么這兩個數進行交換并終止冒泡排序，如果第一個數小于第二個數則直接終止冒泡排序。

（4）依次打印出數組元素[4]。

2.2 選擇排序實現

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

（1）設置k=0，儲存第一個數a[0]的下標，默認為最小值。

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

（3）把a[0]與a[k]元素值進行交換，完成第一次比較。

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

（5）直到k=n-2，進行n-1輪比較之后，完成排序。

（6）依次打印出數組元素[3]。

例：對數組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

利用兩個循環嵌套，完成上述過程[5]143-145核心代碼如下。

for(j=0; j<9; j++)//進行9次循環，實現9趟比較

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

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

{

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

}

運行結果如下。

由小到大的順序為：

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;

}

運行結果如下。

由小到大的順序為：

1 2 3 15 16 21 23 25 26 32

2.3 小結

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

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

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

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

int n;

scanf("%d",&n);

int a[n];

這種定義數組（企圖在程序中途臨時輸入數組大小）是不正確的[5]140，但是在經過多次實踐后發現，只要是在實際應用中，對n賦予一個確定的整型數值，那么就可以正常使用這段代碼。運行結果如下。

請輸入數組元素個n=5

請輸入n個元素：

1 6 8 5 7

8 7 6 5 1

選擇排序交換次數為：4次

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

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

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

3 二維數組排序

3.1 多列數據無捆綁排序

要求：多列數據每一列都按照一定順序排列，生活中這種排序需求相對較少。

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

首先連續運用兩次冒泡排序解決該問題，核心程序如下。

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;

}

運行結果如下。

排序后順序為：

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

連續運用兩次選擇排序解決該問題，核心程序如下。

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;

}

運行結果如下。

排序后順序為：

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

3.2 小結

由此可見不論是連續使用冒泡排序還是連續使用選擇排序，都可以實現二維數組無捆綁排序。

3.3 部分列數據捆綁排序

要求：多列數據中部分列的數據進行排序時，原本的對應關系不能改變，對于這種排序問題生活中需求相對較多，例如學生姓名、成績、學號的排序。

例：對數組int a[10][2]={{1,95},{2,85},{25,80},{3,75},{15,85},{11,95},{12,95},{23,85},{21,60},{6,70}}排序。要求：每一行元素對應關系不變，第二列由小到大排序，同時當第二列數據相同時，第一列也要按照由小到大排序。

首先連續運用兩次冒泡排序解決該問題，核心程序如下。

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;

}

運行結果如圖2所示。

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

在這里我們可以看到，連續運用兩次冒泡排序，第二列按照由小到大排序，當第二列數據相等時，第一列數據也是按照由小到大順序排列的，結果是正確的。

連續運用兩次選擇排序來解決該問題，核心程序如下。

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;

}

運行結果如圖3所示。

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

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

3.4 小結

當進行二維數組的部分列數據捆綁排序時，冒泡排序可以得出正確的結果，而選擇排序則不能得出正確的結果，其原因在于兩種排序算法的穩定性不同。

4 冒泡排序和選擇排序穩定性比較

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

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

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

表2 選擇排序第一輪比較結果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}后面了，產生這樣的原因是，選擇排序進行比較時，先進行下標的記錄，最后最前面的元素只和記錄下標的元素進行交換。但是這樣交換就很容易出現，把原本在前面的元素交換到后面，從而導致選擇排序的穩定性低。

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

…………證了冒泡排序的穩定性。

5 結語

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

引用

[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.