冒泡排序(Bubble sort)

gaunthan Posted on Aug 7 2016

? Sorting ? ? Algorithm ?

> **冒泡排序**(Bubble sort)是排序算法的一种，它是蛮力思想的一个体现。

## 思想
重复地走访要排序的数列，一次比较相邻的两个元素，如果它们的顺序不符合要求就交换它们的位置。$n$个数需要$n-1$趟排序，每一趟排序使得最大数冒出（升序）或最小数冒出（降序）。

为什么是$n-1$趟呢？因为最后一个数已经没有数需要和它比较了，因此最后一个数的这一趟比较可以省去。

## 示意
你可以通过查看下面的动态图来获得直观的感受：
![](https://leanote.com/api/file/getImage?fileId=59451ef8ab64415ebc001c04)

## 实现
传统冒泡排序的实现如下：
```c
//升序方式
void BubbleSort(int a[], int n)
{
    int i, j;
    for(i = 0; i < n - 1; ++i) {
        for(j = 0; j < n - 1 - i; ++j) {
            if(a[j] > a[j + 1])
                Swap(a + j, a + j + 1);
        }
    }
}
```

## 改进
### 设比较标志法
普通的冒泡排序，即使原数列已经有序，仍然会进行$n-1$趟排序。可以加入一标志性变量，用于标志某一趟排序过程中是否有数据交换。如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。如对序列`3 1 4 5 6`进行排序时，只进行2趟算法就结束了（第二趟没有发生交换使得排序提前结束）。注意，当输入序列是逆序的，该算法和传统冒泡排序进行了一样多次比较。

实现代码如下：
```c
void FlagedBubbleSort(int a[], int n)
{
    int i, j, swaped;
    
    for(i = 0; i < n - 1; ++i) {
        swaped = 0;
        for(j = 0; j < n - 1 - i; ++j) {
            if(a[j] > a[j + 1]) {
                Swap(a + j, a + j + 1);
                swaped = 1;
            }
        }
        // 该趟没有执行过交换操作，序列已有序，因此可提前结束
        if(!swaped) break;
    }
}
```

### 剔除法
假设某一位置pos后的元素都已排序，而pos前的元素未排序完，那么上述算法仍然会扫描pos位置后的元素。因此，可设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置后的元素均已排序完，故在进行下一趟排序时只要扫描到pos位置即可。可形象地认为pos位置后的 n-pos+1 个元素都被从待排序列中剔除了。

实现代码如下：
```c
void RejectBubbleSort(int a[], int n)
{
    int i, high, rpos;
    high = n - 1;       
    while(high > 0) {
        rpos = 0;
        for(i = 0; i < high; ++i)
            if(a[i] > a[i + 1]) {
                rpos = i;   //记录交换位置
                Swap(a + i, a + i + 1);
            }
        high = rpos;    //下一趟应该扫描到达的位置
    }
}
```

### 双向剔除法
上面的**剔除法**只能处理某一方向上的已排序子序列，使用双向的扫描可进一步优化冒泡排序。

实现代码如下：
```c
void DoubleBubbleSort(int a[], int n)
{
    int i, j;
    int low = 0, high = n - 1;
	int lpos, rpos;
    while(low < high)
    {
        rpos = low;
        for(i = low; i < high; ++i) //正向冒泡
            if(a[i] > a[i + 1]) {
                Swap(a + i, a + i + 1);
                rpos = i;
            }
        high = rpos;
        
        lpos = high;
        for(j = high; j > low; --j) //反向冒泡
            if(a[j] < a[j - 1]) {
                Swap(a + j, a + j - 1);
                lpos = j;
            }
        low = lpos;
    }
}
```

## References

- MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010.
- ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013.