从排序开始（一）冒泡排序、插入排序与选择排序
学习算法，怎么可以不懂排序？但很多时候，我们习惯了用 sort 和 qsort，对于具体排序，我们也许真忘光了。我们先从O(n^2)的常用排序开始。
冒泡排序（Bubble Sort）：
说起排序就不能不说冒泡（Bubble Sort），它非常简单，维基中这样解释“重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢‘浮’到数列的顶端。”
复杂度：
最差时间复杂度：O(n^2)
最优时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
稳定性：稳定
我写冒泡通常这样写：
算法步骤为：
1、从有序数列 { a[0] } 和无序数列 { a[1],a[2],a[3]，…，a[n-1] }开始进行排序；
2、处理第i个元素时（i=1,2,3,…,n-1），数列 { a[0],a[1],a[2]，…，a[i-1] }是已有序的，而数列{ a[i],a[i+1]，…，a[n-1] }是无序的。用a[i]与a[i-1]，a[ i-2]，…，a[0]进行比较，找出合适的位置将a[i]插入；
3、重复第二步，共进行n-i次插入处理，数列全部有序。
复杂度：
最差时间复杂度：O(n^2)
最优时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
稳定性：稳定
实现：
void selectionSort(int arr[], int n){for (int i = 0; i < n; i++){int index = i;//找出最小元素的索引for(int j = i+1;j < n;++j){if(arr[index] > arr[j])index = j;}//把找到的最小元素和 arr[i] 交换if(index != i){int t = arr[index];arr[index] = arr[i];arr[i] = t;}}}
