1.6冒泡——一点新的感悟

其实我是没打算写这个算法的，你也看出来了，不是吗。
不过我今天看到了一个实现，觉得很有意思，不妨讨论一下。
冒泡排序的核心就是：假设需要非降序排列，然后相邻元素比较，若左大于右，就交换。写出来就是：

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

之所以叫冒泡排序，就是因为每执行一次排序，就把一个最大的元素浮出去。
不过我今天看了一个实现，就很有意思。我写一下：

void bsort(int a[], int n)
{
  for (bool sorted = false; sorted = !sorted; --n)
    for (int i = 1; i < n; ++i)
    {
      if (a[i-1] > a[i])
      {
        swap(a[i-1], a[i]);
        sorted = false;
      }
    }
}

这段代码就很有意思，尽管道理上没有什么改变，不过它却削弱了冒泡的含义，相反，它的想法是，消除每一个逆序对，我之前的文章也写过什么是逆序对，就不说了。而代码停下的依据也是整个序列中不存在逆序对，这是标志着排序的sorted就是true了。
而外层for循环的判断结构上也很巧妙，我们知道继续循环的条件是满足条件，就是“条件为真”，所以当序列中有逆序对的时候，sorted == false，而进入循环后，因为sorted = !sorted，sorted就被设为了true，只有排列中不存在逆序时，sorted才会保留true，进而在外层判断时被赋值为false，不满足条件，结束循环。
本文没有什么特殊含义，就是看到了一个不错的实现，想分享一下。