这篇复习冒泡排序。
冒泡排序也是一种稳定排序、内排序。 冒泡排序的基本思想：对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。插入排序比冒泡排序快！
上面说的是普通的冒泡排序算法，时间复杂度是O(n^2)，这种方法只能一趟排序操作只能找到一个最大值或最小值，消耗时间太多。
改进方法1：我们可以让每趟排序中进行正向和反向两遍冒泡的方法，一次就可以同时得到最大值和最小值，这样一来排序的趟数减少了一半。这种方法形象来说就像振荡小球，如果两端已经选择出来最大值和最小值，那么下一趟排序的时候就会缩小排序的距离，后面振荡的幅度就会减小，一直当幅度为0，是不是很像振荡小球由于阻尼的存在，不断减少幅度，直至停止。
改进方法2：在每趟排序过程中，用标记位记录每趟排序中最后一次交换的位置，如果最后一次交换的位置在0，那么就说明整个数组排序完毕。这种改进的思想是把先前排序的先验信息使用上，，减少排序的次数。
实现代码：
#include<iostream>using namespace std; void BubbleSort(int a[], int n){for(int i = 0; i < n-1; i++){for(int j = 0; j < n-i-1; j++){if(a[j] > a[j+1])swap(a[j], a[j+1]); }}}void BubbleSort_2(int a[], int n){int low = 0; int high = n-1; int j; while(low < high){for(j = low; j < high; j++){if(a[j] > a[j+1])swap(a[j], a[j+1]); }high–;for(j = high; j > low; j–){if(a[j] < a[j-1])swap(a[j], a[j-1]); }low++; }}void BubbleSort_3(int a[], int n){int i = n-1; // 初始时的最后交换位置while(i > 0) // 直到交换位置为0{int pos = 0; for(int j = 0; j < i; j++) // 每趟排序只进行到上次最后交换的位置{if(a[j] > a[j+1]){pos = j;swap(a[j], a[j+1]);}}i = pos; }}int main(){int a[] = {1, 4, 8, 6, 2, 7}; BubbleSort_3(a, 6); for(int i = 0; i< 6; i++)cout<<a[i]<<' '; cout<<endl; return 0; }
其实生命无论长短，只要我们能努力绽放出生命的光彩，便会拥有精彩的人生。
