内部排序之冒泡排序

一、算法思想：
<1>，扫描待排序的记录，在扫描过程中，不断地将相邻两个记录中关键字大的记录后移
 最后必然将序列中最大关键字换到记录序列的末尾。
<2>,进行下一次的扫描，对前n-1个记录进行同样的操作。其结果是使次大的记录被放在第
 n-1大的记录位置。然后转到<1>,直到n-1=1，算法结束。

算法分析：
算法共需要n-1趟。2个数需要1趟，3个数需要2趟。4个数需要3趟。...
每趟都是相邻两个数进行比较，前面的那个数的下标为[0,n-2-i],后面那个数[1,n-1-i] 其中i取值范围
[0,n-2]。
-----------------------------------------------------------------------------------------------------------
二、算法的基本实现。

#define swap(a, b) \
    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)

void bubble_sort(int a[], int left, int right)
{
     int i = 0, j = 0;
     int len = right - left + 1;
     int tmp = 0;

     for (i=0;i<=len-2;i++) {          //[0,n-2]共n-1趟
            for (j=0;j<len-1-i;j++) {  //每一趟比较的范围[0,len-1-i]
                if (a[j] > a[j+1])
                  swap(a[j],a[j+1]);
            }
     }
}

---------------------------------------------------------------------------------------------------------
二，算法改进：减少不必要的趟数。
可以设置一个标志，如果在某一趟中没有出现交换，则说明前面的数据已经是顺序的了。
不需要以后的“趟”了，所以就可以结束算法了，这样可以减少不必要的趟数而提高算法的
性能。

#define swap(a, b) \
    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)

void bubble_sort(int a[], int left, int right)
{
     int i = 0, j = 0;
     int len = right - left + 1;
     int tmp = 0;
     int change = 1;

     for (i=0;i<=len-2 && change;i++) {//[0,n-2]共n-1趟
            change = 0;
            for (j=0;j<len-1-i;j++) {//每一趟比较的范围[0,len-1-i]
                if (a[j] > a[j+1]) {
                  swap(a[j],a[j+1]);
                  change = 1;
                 }
            }
     }
}

----------------------------------------------------------------------------------------------
算法时间复杂度：
        O（n^2）

---------------------------------------------------------------------------------------------