冒泡排序是一種最簡單的排序算法。顧名思義郑现，就是每次排序之后，最大的元素會(huì)像氣泡浮出水面一樣移動(dòng)到最后的位置辛友，每一次循環(huán)都能確定一個(gè)序列中的最大元素邓梅。
算法思想：
- 比較相鄰的兩個(gè)元素，如果第一個(gè)比第二個(gè)大殿遂，就交換
- 對每一對相鄰的兩個(gè)元素執(zhí)行同樣的操作幢竹，從開始執(zhí)行到最后，這一步做完之后循签，最后的元素將是最大的元素
- 對前面n-1個(gè)元素執(zhí)行1，2兩步
- 重復(fù)執(zhí)行前面步驟，直到?jīng)]有一對元素需要比較交換
算法代碼
void bubbleSort(int array[], int length)
{
int i, j, tmp;
if (1 >= length)
return;
for (i = length-1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
算法分析
- 最好情況下兰粉，即一開始就是有序的，那么就不用執(zhí)行交換操作了，只需要執(zhí)行1+2+3+…+n次比較舔琅，時(shí)間花銷為n(n-1)/2课蔬，因此，最優(yōu)復(fù)雜度為O(n^2)
- 最差情況下扎即，也就是開始逆序，那么每一次排序都要比較和交換兩個(gè)元素，時(shí)間花銷為3n(n-1)/2傻盟，因此，最差時(shí)間復(fù)雜度為O(n^2)诽表，相比于上面的最優(yōu)情況，就是多了上面代碼中的交換操作。
- 平均情況下平痰，時(shí)間復(fù)雜度為O(n^2)。
- 空間復(fù)雜度為交換過程中申請的額外空間，顯然舞虱，我們只需要一個(gè)變量，因此復(fù)雜度為O(1)浑槽。
- 很多地方認(rèn)為冒泡排序的最優(yōu)復(fù)雜度為O(n)畸冲，這是另一種優(yōu)化方法算行，就是引入一個(gè)標(biāo)志位儡陨，用于判斷是否已經(jīng)有序了呀枢，當(dāng)?shù)谝惶吮闅v，全部元素?zé)o需交換进宝，那么標(biāo)志位置位未玻，無需后續(xù)的操作绰疤，排序結(jié)束，只進(jìn)行了一趟遍歷，因此為O(n)蛾方。
- 有些地方認(rèn)為最好的空間復(fù)雜度為O(0)释簿，因?yàn)榻粨Q無需引入變量，當(dāng)然這也是可行的，但是最好不要這樣做夺巩，因?yàn)檫@樣容易復(fù)雜化程序的理解征绎。
過程展示
bubble-sort.gif
