一、简介
冒泡排序法又称为交换排序，其比较方式由第一个元素开始，比较相邻元素大小，若大小顺序有误，则对调后再进行下一个元素的比较。如此扫描过一次后就可确保最后一个元素是位于正确的顺序。接着再进行第二次扫描，直到完成所有元素的排序关系为之。
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
二、步骤
从数组的第一个元素arr[0]开始，两两比较**(arr[n],arr[n+1])，如果前面的数大于后面的数（arr[n] > arr[n+1]）,那么交换两个元素的位置，把大的数往后移动。这样依次经过一轮比较以后，最大的数将会被交换到最后的位置（arr[n-1]）。
三、示例
四、代码实现
template<typename T>
void bubble_sort(T arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
#include <iostream>
#define num 10
using namespace std;
int main()
{
int a[10] = { 1,5,7,4,9,6,3,4,0,10 };
for (int i = 0; i < num; i++) {
for (int j = num-1; j > i; j--) {
if (a[j]<a[j-1]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
for (int i = 0; i < 10; i++) cout << a[i] << " ";
}
template<typename T>
void bubbleSort( T arr[] , int n){
bool swapped;
//int newn; // 理论上,可以使用newn进行优化,但实际优化效果较差
do{
swapped = false;
//newn = 0;
for( int i = 1 ; i < n ; i ++ )
if( arr[i-1] > arr[i] ){
swap( arr[i-1] , arr[i] );
swapped = true;
// 可以记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
// 实际优化效果较差,因为引入了newn这个新的变量
//newn = n;
}
//n = newn;
// 优化,每一趟Bubble Sort都将最大的元素放在了最后的位置
// 所以下一次排序,最后的元素可以不再考虑
// 理论上,newn的优化是这个优化的复杂版本,应该更有效
// 实测,使用这种简单优化,时间性能更好
n --;
}while(swapped);
}
五、评价
时间复杂度：最坏情况及平均情况均需比较n(n-1)/2次；时间复杂度为O(n²)，最好情况只需要完成一次扫描，发现没有做交换的操作则表示排序已经完成，所以只做了n-1次比较，是复杂度为O(n)。
适用范围：冒泡排序法适用于数据量小或者有部分数据已经排序过的情况。
