算法原理：冒泡排序是经过n-1趟子排序完成的，第 i 趟子排序从第1个数至第 n-i+1 个数，若第 i 个数比第 i+1 个数大，则交换这两个数，实际上这样经过 i 次子排序就使得 第1个数至第 n-i +1个数之间最大的数交换到了n-i+1 的位置上了。实际上冒泡排序时可以优化的，那就是当第 i 次子排序并没有发生元素的交换时，就说明数组已经排好序了，以后的子排序就不用做了。
算法代码：
#include <iostream> using namespace std; void swap(int &x,int &y) { x = x^y; y = x^y; x = x^y; } void bubble_sort(int *arr,int n) { int i,j; for(i = n - 1 ; i > 0 ; --i) { bool flag = true; for(j = 0 ; j < i ; ++j) { if(arr[j] > arr[j+1]) { flag = false; swap(arr[j],arr[j+1]); } } if(flag) //数组已经排好序没必要在继续进行其他子排序了 break; } } int main() { int arr[] = {2,1,4,3,8,7,5,6}; bubble_sort(arr,8); for(int i = 0 ; i < 8 ; ++i) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
小结：冒泡排序算法的时间复杂度是O(n^2)，同时冒泡排序也是稳定的，并且属于原地排序，排序的效率取决于逆序对的多少。采用一点小优化也加速了冒泡排序。