/*-------------------------------------------------------------------------------------------
Bubble_sort.h
冒泡排序： 時(shí)間復(fù)雜度為O(N^2)
改進(jìn)的冒泡排序： 時(shí)間復(fù)雜度仍為O(N^2)
  一般的冒泡排序方法有可能會(huì)在已經(jīng)排好序的情況下繼續(xù)比較，改進(jìn)的冒泡排序
  設(shè)置了一個(gè)哨兵flag，如果一次for循環(huán)沒(méi)有進(jìn)行交換，則元素已經(jīng)排好序，由哨兵控制退出循環(huán)。
-------------------------------------------------------------------------------------------*/
#ifndef BUBBLE_SORT_H
#define BUBBLE_SORT_H
#include "typedef.h"
#include "swap.h"
//冒泡排序
void Bubble_sort(T *a, int n)
{
  for(int i=n-1; i != 0; --i)
    for(int j=0; j != i; ++j)
      if(a[j+1] < a[j]) swap(a[j+1],a[j]);
}
//改進(jìn)的冒泡排序
void Improved_Bubble_sort(T *a, int n)
{
  for(int i=n-1; i != 0; --i)
  {
    bool flag = true;
    for(int j=0; j != i; ++j) //這一趟遍歷如果沒(méi)有交換，則已完成排序
      if(a[j+1] < a[j]) { swap(a[j+1],a[j]); flag = false; }
    if(flag == true) break;
  }
}
#endif