5.2 冒泡排序（bubble sort）

      冒泡排序法是一种经典的、入门级的排序算法。它重复地遍历整个数组，对数组的元素进行两两比较，如果两数的顺序有误，则将两数字交换。

      由于在比较的过程中，最小的数先变换到数列的顶端，其次是第二小的数……直至所有数字完成排序，因而得名冒泡排序。

      冒泡排序的具体运算如下：

      首先，从子数列的最后一位开始，比较相邻两元素，如果第一个比第二个大，则交换两元素。直至比较直子数列的开头。

      其次，将第一个元素剔除出子数列（此时第一个元素已经为最小值）。

      再次，对剩余的子数列重复第一步、第二步，直至剩余最后一个元素。

      以数列{8,9,1,2,7}为例，冒泡排序法的排序过程如图5-2所示。其中，绿色的元素表示正在进行比较的元素，蓝色的元素表示已经完成排序的元素。

      好了，冒泡排序原理相对简单，就不多解释了，直接上代码。

C代码实现为：

#include <time.h>
#include <stdio.h>
#include <random>

void exchange(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
void bubble_sort(int a[], int length) {
	for(int i=0; i<length; i++) {
		for(int j=0; j<length-i; j++) {
			if( a[length-j-2]>a[length-j-1] ) {
				exchange( a[length-j-2], a[length-j-1] );
			}
		}
	}
}

int main(int argc, char** argv) {
	const int length = 25;
	int a[length];
	//告诉rand方法以time为种子去生成随机数
	srand( (unsigned)time( NULL ) );
	for(int i=0; i<length; i++) {
		a[i] = rand()%100;
		printf("%d ", a[i]);
	}
	printf("\n");
	bubble_sort(a, length);
	for(int i=0; i<length; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

C++代码实现为：

#include<iostream>
#include<vector>
#include<time.h>
#include<random>
using namespace std;

void exchange(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}
void bubble_sort(vector<int> &aVec) {
	vector<int>::iterator itStart = aVec.begin();
	vector<int>::iterator itEnd = aVec.end()-1;
	for(vector<int>::iterator it=itStart; it<itEnd; it++) {
		for(vector<int>::iterator jt=it; jt<itEnd; jt++) {
			int index =jt-it;
			if( *(itEnd-index-1) > *(itEnd-index) ) {
				exchange(*(itEnd-jt+it-1), *(itEnd-jt+it));
			}
		}
	}
}

int main() {
	const int length = 25;
	int a[length];
	//告诉rand方法以time为种子去生成随机数
	srand( (unsigned)time( NULL ) );
	for(int i=0; i<length; i++) {
		a[i] = rand()%100;
	}
	vector<int> aVec(a, a+length);
	vector<int>::iterator itStart = aVec.begin();
	vector<int>::iterator itEnd = aVec.end()-1;
	for(vector<int>::iterator it=itStart; it<=itEnd; it++) {
		cout<<*(it)<<" ";
	}
	cout<<endl;
	bubble_sort(aVec);
	for(vector<int>::iterator it=itStart; it<=itEnd; it++) {
		cout<<*(it)<<" ";
	}
	cout<<endl;
	return 0;
}