起泡排序是交换类排序方法中的一种简单排序方法。其基本思想为：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。如右图所示，在第i趟起泡排序之前，区段 R[n-i+2..n] 中的记录已按关键字从小到大有序排列，而区段 R[1..n-i+1] 中的记录不一定有序，但该区段中所有记录的关键字均不大于有序序列中记录的关键字(即小于或等于R[n-i+2].key)，则第i趟起泡排序的操作为，从第1个记录起，逐个和相邻记录的关键字进行比较，若第j(1≤j≤n-i)个记录的关键字大于第j+1个记录的关键字，则互换记录，由此可将区段 R[1..n-i+1] 中关键字最大的记录"交换"到 R[n-i+1] 的位置上，从而使有序序列的长度增1。显然，如果第i趟起泡排序的过程中，没有进行任何记录的交换，则表明区段 R[1..n-i+1] 中的记录已经按关键字从小到大有序排列，由此不再需要进行下一趟的起泡，即起泡排序已经完成，可见排序结束的条件是(i=n-1)或者（第i趟的起泡中没有进行记录交换），如算法10.7所示。
算法 10.7void BubbleSort(SqList &L)
{
// 对顺序表L作起泡排序
for (i=L.length, change=TRUE; i>1 && change; --i) {
change = FALSE;
for (j=1; j<i; ++j)
if (L.r[j].key > L.r[j+1].key)
{ L.r[j]←→L.r[j+1]; change = TRUE }
}// for i
} // BubbleSort
分析起泡排序的时间复杂度：和直接插入相似，排序过程中所进行的"比较" 和 "移动" 操作的次数取决于待排记录序列的状态，在待排记录处于"正序"时取最小值，此时只需进行一趟起泡排序，反之，在待排记录处于"逆序"时取最大值，此时需进行 n-1趟起泡，列表如下：
| 待排记录状态 |
"比较"次数 |
"移动"次数 |
| 正序 |
n-1 | 0 |
| 逆序 |
 |
 |
当待排序列中的记录已按关键字有序排列时，显然，在进行n-1次关键字的比较，而不需要交换记录；然而，当待排序列中的记录按关键字逆序排列时，需进行
n-1 趟起泡，并且每一趟起泡都需进行所有记录的互换，因此进行的关键字比较的总数为：
，
进行的记录移动的总数为：
。