算法学习（四）冒泡排序

冒泡排序的原理是：

1）从0开始，比较相邻两个元素的大小，如果是按从小到大排序的话，则将大的元素往后往，反之，则将小的元素往后放，这样经过一轮的比较，就会将最大或者最小的数放到数组的最后面了。

2）第二轮开始，还是从0开始，但是这一次呢，就不需要比较最后面那个元素了，因为它已经是最大了（这其实跟堆排序，找出最大数或者最小数，放到数组后端是一样的道理），假设数组长度为N，则第二轮只需要比较N-1个元素了。

3）这样，每一轮结束，都会有一个当前最大素放到最后面，那么到第N-1轮的时候，其实就只剩一个元素了，于是，排序就结束了。

其过程如下图：

其对应的代码如下：

void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

void printArray(int a[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
}

void sort1(int a[], int n) {
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 1; j < n - i; j++) {
			if (a[j - 1] > a[j]) {
				swap(a[j - 1], a[j]);
			}
		}
	}
	printArray(a, n);
}

不过，我们从上面的过程图发现，在一轮的比较交换过程中，并不是每一次都会发生交换，那么就很有可能存在一种情况，参与排序的数组在某一位置后面的元素已经是有序的了，如下：

其实这就相当于老天已经先帮我们冒泡了很多轮了，所以我们就不需要再继续傻傻地再冒下去了，我们只需要记住这个位置，下一轮开始，就可以直接只冒泡前面2个元素就好了呀，对吧？嗯，对的。

代码如下：

void sort2(int a[], int n) {
	int i;
	int pos = n;
	while(pos > 0){
		i = pos;
		pos = 0;
		for (int j = 1; j < i; j++) {
			if (a[j - 1] > a[j]) {
				swap(a[j - 1], a[j]);
				pos = j;
			}
		}
	}
	printArray(a, n);
}

冒泡排序是最简单的排序方法，不过其实再复杂的排序方法，也是从最简单开始的，不是吗？

结束。