数据结构笔记--冒泡排序

关于时间复杂度的内容查考：

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

冒泡排序在最好情况下时间复杂度为o(n),最坏情况时间复杂度为o(n^2),平均时间复杂度为o(n^2)。

为了简单描述，这里只说明数列从小到大排序的例子。在排序过程中，每次遍历都比较相邻两个元素，如果前者比后者大，则交换两者位置，否则不进行操作，这样的结果是，每次遍历都会把最大的那个元素挪到最后面。每一次遍历完后，最后的那个元素就不需要再遍历，代码如下：

int P;int i;
template<class T>
void Bubble_Sort(T arr[],int N)//这里的数据类型T要保证可以排序，如int、double都可以排序，N表示数组元素个数
for(P=N-1;P>=0;P--)
{
	for(i=0;i<P;i++){
    	if(arr[i]>arr[i+1])
    	{
          swap(arr[i],arr[i+1]);
    	}
    }
}

但是，以上的代码有个缺点，就是当数列的顺序已经是排好的情况下，数组仍然会被遍历。下面给出改进后的代码：

int P;int i;
template<class T>
void Bubble_Sort(T arr[],int N)
for(P=N-1;P>=0;P--)
{
  	int flag=0;//加个标志，当遍历一次后没有出现交换，则表示数列已经排好。
	for(i=0;i<P;i++){
    	if(arr[i]>arr[i+1])
    	{
          swap(arr[i],arr[i+1]);
          flag=1;
    	}
    }
  if(flag==0)break;
}