void BubbleSort(int a[],int left,int right); //对a[left]到a[right]由小到大排序
void BubbleSort(int a[],int left,int right) { int i,j; int flag; //当一次循环中未发生交换，0标记排序结束
int temp; for(i=right;i>=left+1;i--){ //冒len-1个泡
flag = 0; for(j=left+1;j<=i;j++) //相邻元素两两比较
if(a[j-1]>a[j]){ temp = a[j-1]; a[j-1] = a[j]; a[j] = temp; flag = 1; } if(flag==0) //没有交换原序列已然有序，就不会再冒泡，排序结束
return; } } /*算法分析: time-complexity: 选取内层循环中关键字交换操作为基本操作,最坏情况下，待排序列逆序,i{a[1]-->a[n-1]},step{1,2,3,...,n-1}， 等差数列求和 total steps = (n-1)(1+n-1)/2 = n(n-1)/2,所以时间复杂度为O(n2); 最好情况下，序列有序只循环一次，时间复杂度为O(n); 平均情况下为O(n2); space-complexity: 空间复杂度为O(1); 算法稳定. */
