圖解嵌入式系統開發之演算法篇：冒泡排序

開始之前，先重申一下本專欄的立場。首先，本專欄討論內容將涉及到C語言基礎，數據結構，演算法，嵌入式系統底層驅動，內核，系統等多個方面，由於要考慮到不同人群接受程度的問題，初期階段，我們並不打算太糾結細節，主要是要把基本原理講清楚，帶領剛入門或者正打算入門的同志們更輕鬆的進入嵌入式開發的殿堂。比如，有些朋友說，之前發的演算法不是最優的， 執行效率不高。我想說的是，基礎的才是最本質的，便於大家理解原理，至於更加優化的演算法，那就等同志們入了門之後自己去探索吧，或者等待後續的升級版本。 但是，畢竟師傅領進門，修行在個人嘛！祝好。

大神請自動忽略本文章，謝謝。

好了，開始主題，本節講解一種更加基礎的入門式排序演算法-冒泡排序。

顧名思義，冒泡排序的思路就像是水中上竄的泡泡一樣，大的先出來，小的後出來。

實際排序的關鍵總結就是：

從剩下的數列裡面選出最大的，往後移，再從剩下的裡面找最大的。。。如此不斷找下去，直到剩下一個數，排序結束。

怎樣從數列中找到最大的？

這可以類比「聰明的狗熊掰玉米」。他先從地頭掰一個，並始終認為手裡的就是最大的，然後繼續往下掰，如果掰的下一個玉米比手裡的大，就留下大的，然後把手裡原來的玉米放下。。。掰到最後，聰明的狗熊手裡拿到的玉米一定是最大的。

具體的實現步驟見下圖。紅色表示本次要比較的兩個數，灰色表示已經排在正確位置。箭頭表示比較過程中臨時最大值的

假設有n個數。兩兩比較，第一輪就有n-1對，所以要比較n-1次，第二輪剩下n-1數，需要比較(n-1) -1 次，如此。。。。第i次需要比較(n-1)-i次, 總共需要比較n-1輪。

比較次數：（n-1）(n-1)/2，所以時間複雜度就是O（n^2）.

代碼實現如下：

#include <stdio.h>/* micro definition to calculate the length of array */#define LENTH_ARRAY(array) sizeof(array)/sizeof(array[0])/** swap function: swap value of the two input parameter* @a: pointer to the first input value* @b: pointer to the second input value*/void swap(int *a, int *b){ int tmp; tmp = *a; *a = *b; *b = tmp; }/** bsort function: sort all elements in order.* @array[]: element that will be sort* @len: the element quantity */void bsort(int array[], int len){ int i,j; for (i = len; i >= 2; i--) for(j = 0; j < i - 1; j++) if(array[j + 1] < array[j]) swap(&array[j + 1], &array[j]);}int main(void){ int i; int array[] = {5,2,1,6,9,3,7,5,3,6,8,2,5,7,9,0}; bsort(array, LENTH_ARRAY(array)); for (i = 0; i < LENTH_ARRAY(array); i++){ printf("%d
",array[i]); } return 0;}

推薦閱讀：