冒泡排序

思想

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

实现

/** * @brief 交换两指针指向的对象的值 */
void Swap(int *a, int *b);

传统冒泡排序的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趟算法就结束了（第二趟没有发生交换使得排序提前结束）。注意，当输入序列是逆序的，该算法和传统冒泡排序进行了一样多次比较。

• 算法实现

  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])
          {
              swaped = 1;
              Swap(a + j, a + j + 1);
          }
      if(!swaped)
          break;
  }
  }

剔除法

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

• 算法实现

  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;                     //下一趟应该扫描到达的位置
  }
  }

双向剔除法

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

• 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;
  }
  }