C語言基礎排序算法-冒泡排序

什么是冒泡排序？

顧名思義，這種排序方法就像水中的氣泡一樣，從底逐漸往上冒，一次前進一步。我們來看一個例子，看看到底是怎么冒泡的。假設有一個數(shù)組3,2,5,4,1，我們希望按照從小到大的順序排序，最后的結(jié)果為1,2,3,4,5。記住冒泡算法的關鍵一點是每次相鄰的兩個元素進行比較，如果不滿足排序的要求（比如后面的一個元素大于前面的元素），則進行交換。基本原理如下：

（1） 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。?

（2）針對所有的元素重復以上的步驟，除了最后一個。

（3）持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

冒泡排序一般要用兩層循環(huán)，所以冒泡排序的時間復雜度為O(n2),n2代表n的平方。很多初學者朋友想用一層循環(huán)就來冒泡排序，這是做不到的。

冒泡排序的代碼如下：

void bubble_sort(int arr[],int size) {int i=0;int j=0;int temp = 0;for(i=0;i<size - 1;i++){for(j=0;j<size - 1 -i;j++){if(arr[j] > arr[j+1]){temp = arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}} }

?下面對代碼的執(zhí)行過程進行詳細解釋。

?

?

開始的數(shù)組狀態(tài)為：

經(jīng)過第一次比較之后，由于3大于2，所以2和3交換，如圖所示。

第二次比較，3小于5，所以不用交換，結(jié)果不變，如圖所示。

第三次比較，5大于4，所以交換，結(jié)果如圖所示。

第四次比較，5大于1，所以仍然要交換，結(jié)果如圖所示。

?

經(jīng)過4次比較，就完成了第一輪的排序，也就把最大的值排到了最后，因此，第二輪的比較，就不用比較到最后了，只比較到1就可以了。

第二輪第一次比較，由于2小于3，所以第二輪第一次結(jié)果不變，結(jié)果如圖所示。

?

?第二輪第二次比較，由于3還是小于4，所以結(jié)果不變，如圖所示。

?第二輪第三次比較，由于4大于1，所以4和1交換，結(jié)果如圖所示。

這樣，第二輪就比較完了，比較了3次。下面進行第三輪比較。

第三輪第一次，由于2小于3，所以不用交換，不變，結(jié)果如圖所示。

?第三輪第二次，由于3大于1，所以要交換，結(jié)果如圖所示。

?

?

第三輪就比較結(jié)束了，共比較2次。再進行最后一輪的比較，第四輪比較。

第四輪，也就是最后一輪，只需要比較一次。

第四輪第一次比較，由于2大于1，所以2和1進行交換，交換后的結(jié)果如圖所示。

這樣經(jīng)過四輪比較，具有5個元素的數(shù)組就排序完成了，總共比較了4+3+2+1次，一共10次比較。

我們對代碼進行稍微改變一下，統(tǒng)計一下比較的次數(shù)和交換的次數(shù)，最后打印一下，代碼如下：

#include <stdio.h>void bubble_sort(int arr[],int size) {int i=0;int j=0;int temp = 0;int compare_times = 0;int swap_times = 0;for(i=0;i<size - 1;i++){for(j=0;j<size - 1 -i;j++){compare_times++;if(arr[j] > arr[j+1]){temp = arr[j];arr[j]=arr[j+1];arr[j+1]=temp;swap_times++;}}}printf("比較的次數(shù)為:%d,交換次數(shù)為:%d\n",compare_times,swap_times); } int main() {int i=0;int arr[]={3,2,5,4,1};int count = sizeof(arr)/sizeof(int);bubble_sort(arr,count);printf("sorted\n");for(i=0;i<count;i++){printf("%d ",arr[i]);}printf("\n");return 0; }

?

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

冒泡排序?qū)嶋H的比較次數(shù)和交換次數(shù)最多為：

n(n+1)/2，所以復雜度是n的平方。

?

總結(jié)

以上是生活随笔為你收集整理的C语言基础排序算法-冒泡排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。