十大简单排序：冒泡排序

冒泡排序

思想：从第一个位置开始，依次比较大小，若前面的值大，则将前值与后值交换，经过一轮的比较后，最大值就排在了末尾。由此而来，比较N轮，N是数组元素个数，那么整个数组就有序了。

void swap(int arr[],int i,int j)
{int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}void BubbleSort(int arr[],int len)
{for(int i=0;i<len;i++){for(int j=0;j<len-1-i;j++){if(arr[j] > arr[j+1]){swap(arr,j,j+1);}}}
}

复杂度分析：时间复杂度为O(n^2)，冒泡排序是稳定的算法，因为相同的两个元素，靠前的是不会和后面的交换的，这就保证了在前面的排序后依旧在前面。

时间复杂度最好的情况下是O(1)，这需要优化上述算法。

优化后的代码如下：

void BubbleSort(int arr[],int len)
{for(int i=0;i<len;i++){bool swapF = false;for(int j=0;j<len-1-i;j++){if(arr[j] > arr[j+1]){swap(arr,j,j+1);swapF = true;}}if(!swapF)break;}
}

就是添加一个标志位，当一次循环比较后，如果没有交换，那么代表已经排好序，没必要再进行冒泡，直接跳出循环结束冒泡即可。