1、概述

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。冒泡排序分為很多輪，每一輪都會將當前比較的最大的數放在右側，不停地自右向左堆積。

2、算法原理

附圖：

3、算法分析

①時間復雜度

若文件的初始狀態是正序的（如：1，2，3，4，5），一趟掃描即可完成排序。所需的關鍵字比較次數C和記錄移動次數M均達到最小值，即：Cmin = n - 1（至少要進行n - 1次比較，n為元素的個數），Mmin = 0。

因此，冒泡排序最好的時間復雜度為O(n)。

若初始文件是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：O(n2)

冒泡排序的最壞時間復雜度為：O(n2)

冒泡排序的平均時間復雜度為：O(n2)

這在所有排序算法中算是效率較低的排序算法。

②算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。

4、實例（java）