2014.06.17 01:04
简介：
冒泡排序是O(n^2)级别的交换排序算法，原理简单，属于必知必会的基础算法之一。
思路：
排序要进行N轮，每一轮从尾部逐个向前扫描，遇到逆序对就进行交换。确保每一轮把最小的元素交换到前面去。这个过程好比水中的气泡向上飘，所以叫冒泡排序。代码非常简单，所以语言描述反而显得麻烦了。
实现：
1 // My implementation for bubble sort. 2 #include <iostream> 3 #include <vector> 4 using namespace std; 5 6 void bubbleSort(vector<int> &v) 7 { 8 int n, i, j; 9 int val; 10 11 n = (int)v.size(); 12 for (i = 0; i < n; ++i) { 13 for (j = n - 1; j > i; --j) { 14 if (v[j - 1] > v[j]) { 15 val = v[j - 1]; 16 v[j - 1] = v[j]; 17 v[j] = val; 18 } 19 } 20 } 21 } 22 23 int main() 24 { 25 vector<int> v; 26 int n, i; 27 28 while (cin >> n && n > 0) { 29 v.resize(n); 30 for (i = 0; i < n; ++i) { 31 cin >> v[i]; 32 } 33 bubbleSort(v); 34 for (i = 0; i < n; ++i) { 35 cout << v[i] << ‘ ‘; 36 } 37 cout << endl; 38 } 39 40 return 0; 41 }