冒泡排序是一种交换排序，实现比较简单，其原始版本如下

void bubsort(int a[], int n) { int temp; for (int i=0; i<n-1; i++) { for (int j=0; j<n-i; j++) if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } }

而我们讨论的重点是它的优化。

概念

有序数组：指按一定顺序排列的数组； 无序数组：指不满足一定排列顺序的数组；

对于冒泡排序，本文默认为前小后大排序方式， 也就是在排序过程中被操作数组的前面是无序的，后面逐渐变成有序，直到整个数组有序。

优化一 插旗优化

插旗优化思路很简单明了，就是在数据排序完成后插个旗，表明数据是否已经有序，进而避免多余的循环。例如有数组12354 显然，第二次的时候就可以结束循环了。

void bubsort(int a[], int n) { int temp, flag; for (int i=0; i<n-1; i++) { flag = 0;//设置旗子 for (int j=0; j<n-i; j++) if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; flag = 1;//插上旗子 } if (flag==0)//判断有无旗子 break;//终止循环 } }

优化二 封顶优化

排序的时候，发生数组无序但数组后半部分有序的情况，这时后面有序部分可封起来，作为下一轮循环的顶，否则每次循环会多浪费时间去扫描这些有序部分。例如 数组32145.

一 3 2 1 4 5 二 2 1 3 4 5 三 1 2 3 4 5 四 1 2 3 4 5

显然，45重复扫描了多次。

void bubsort(int a[], int n) { int temp, p, last = n - 1;//last是后半有序部分最小值的位置 //，即无序部分的顶。 for (int i = 0; i < last; i++) { for (int j = 0; j < last; j++) if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; p = j;//通过每次数据交换更新顶部，直到数据不交换就 //意味着有序，此时p即为无序数组顶部。 } last = p;//封顶。 } }

# 优化三

冒泡小变体-双向冒泡

对于双向冒泡的原理也容易理解，就是同时从两边对数组进行扫描和交换，一次找出最大值和最小值。

void bubsort(int a[], int n) { int hi, lo， top; hi = n-1;//设置哨兵-最大 lo = 0;//设置哨兵-最小 while (lo<hi) { for (int i=lo; i<hi; i++)//从前到后扫描 if (a[i]>a[i+1]) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; top = i;//标记顶 } hi = top;//封顶 for (int j=hi; j>lo; j--)//从后到前扫描 if (a[hi]<a[hi-1]) { int temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; top = j;//标记底 } lo = top;//封底 } }

等等，分析一下时间复杂度，虽然双向冒泡的外部循环少了执行次数，但内部变成两次循环，和单向冒泡都是O（n^2），到底在什么地方优化呢？

我们再看看我做的简单的对照表

Column 1Column 20.21926.2460.1921.1060.1618.413

依次为单向冒泡，单向冒泡（插旗+封顶），双向冒泡在数组大小分别为10000,100000时运行的时间。

注：表格时间均为三次运行的中值，使用rand()，数据从实验方面来说不严谨，但这里只为说明双向冒泡确实做到了优化。

为什么双向能做到优化呢？

很简单

双向冒泡排序自带了封顶优化（封底从另一方面也可以看作封顶）。也就是说双向的优化和封顶优化的原理相同，甚至双向不仅封顶，而且还封底，比单向封顶还要好一点。

双向冒泡（插旗优化）

相信看到题目，大家马上就能想到原理，这里就不赘述了。

void bubsort(int a[], int n) { int hi, lo, flag, top; hi = n-1; lo = 0; while (lo<hi) { flag = 0; for (int i=lo; i<hi; i++) if (a[i]>a[i+1]) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; flag=1; top = i; } hi = top; if (flag==0) break; flag = 0; for (int j=hi; j>lo; j--) if (a[j]<a[j-1]) { int temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; flag = 1; top = j; } lo = top; if (flag==0) break; flag = 0; } }

这就是冒泡排序最终优化版本（双向插旗）了。 ———————————————— 注意！原版冒泡排序的时间是稳定的，但我们所做的优化是对数据有点敏感的，所以优化后的版本虽然时间复杂度还是O（n^2），但如果用测试的时候，运行时长会随着数据的变化而变化。

我的个人hexo博客.