学习算法，怎么可以不懂排序 但很多时候，我们习惯了用 sort 和 qsort，对于具体排序，我们也许真忘光了。我们先从O(n^2)的常用排序开始。

　　冒泡排序(Bubble Sort)：

　　说起排序就不能不说冒泡(Bubble Sort)，它非常简单，维基中这样解释“重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢‘浮’到数列的顶端。”

　　复杂度：

　　最差时间复杂度：O(n^2)

　　最优时间复杂度：O(n^2)

　　平均时间复杂度：O(n^2)

　　稳定性：稳定

　　我写冒泡通常这样写：

　　[cpp]

　　void bubbleSort(int arr[],int n)

　　{

　　for(int i = 0;i < n;++i)

　　{

　　for(int j = i+1;j < n;++j)

　　{

　　if(arr[i] > arr[j])

　　{

　　int t = arr[j];

　　arr[j] = arr[i];

　　arr[i] = t;

　　}

　　}

　　}

　　}

　　基本思想是从数组中拿出第一个元素，然后开始和它后面的元素比较，只要发现比它轻，就交换两个元素，这样，一遍过后，最轻(最小)的元素就冒到了数列的顶端。然后第二趟把第二轻的元素冒上来，依此类推，到最后数列就是有序的。一句话说，就是每一次都选出最小的数字，让它冒出来。

　　冒泡还可以这样写：

　　[cpp]

　　void bubbleSort(int arr[],int n)

　　{

　　for(int i = 0;i < n-1;++i)

　　{

　　for(int j = 0;j < n-i-1;++j)

　　{

　　if(arr[j] > arr[j+1])

　　{

　　int t = arr[j+1];

　　arr[j+1] = arr[j];

　　arr[j] = t;

　　}

　　}

　　}

　　}

　　这是每一次都把最大的元素沉下去。效果是等价的。

　　冒泡也可以优化，但毕竟是一种效率低下的算法，无法摆平均O(n^2) 的命运。

　　一种常见的优化就是记录每一次遍历的过程是否有交换值，没有的话说明后面已经是有序的，直接跳出循环

　　[cpp]

　　void bubbleSort(int arr[],int n)

　　{

　　for(int i = 0;i < n;++i)

　　{

　　bool flag = false;

　　for(int j = i+1;j < n;++j)

　　{

　　if(arr[i] > arr[j])

　　{

　　int t = arr[j];

　　arr[j] = arr[i];

　　arr[i] = t;

　　flag = true;

　　}

　　if(!flag) break;

　　}

　　}

　　}