算法思想

冒泡排序分为趟数和交换次数。

外层循环为趟数，如果有n个元素则要循环n-1趟。

内层循环主要做每一趟的交换，从第0个元素开始如果发现当前元素大于它的后一个元素，将其交换，每一趟下来，最后一个元素都是最大的，所以每次循环只要循环到0~n-1-i即可，因为后面的元素就是有序的了。

算法代码

void BubbleSort(int* arr,int size){	int k=size-1;	//k用来记录每趟排序的最大的交换位置    int pos=0;	//pos记录最后一次交换的位置	//排序的趟数，共size-1次 	for(int i=0;i
    
     arr[j+1])			{				int temp=arr[j];				arr[j]=arr[j+1];				arr[j+1]=temp;				flag=1;	//元素发生了交换，flag置为1 				pos=j;	//pos存放循环里最后一次交换的位置j 			}		}		k=pos;	//下一内层循环仅循环到0到这次得到的k之间 		//如果一趟下来flag没有变化，即元素本来就是有序，就直接return 		if(flag==0)		{			return;		}	}}
    

此算法是冒泡排序的优化版算法，优化点：

1.如果本来就有序，第一趟就直接判断然后return。

2.每一趟都是从0~k，可以记住上一趟排序时最后一次交换的位置k值，下一次的k值会更新，如果中间有几个元素本来就有序，则k值记录的是有序的前一个位置，则下一次循环就不用再循环这几个元素，直接循环到记录的k值那里即可，可以减少循环次数。

算法分析

最好的情况（关键字在记录序列中正序）：只需进行一趟冒泡

比较的次数：n-1

移动的次数：0

最坏的情况（关键字在记录序列中反序）：需进行n-1趟冒泡

比较的次数：

移动的次数：

所以冒泡排序最好时间复杂度为O(n),最坏和平均为O(n^2)。