我们总是有这种想法：当碰到一组数据时，我们总喜欢对这组数据进行排序。因为排好序后，我们可以轻松的进行分析。
今天，我们来学习的排序算法是最简单的一种：冒泡排序。
为什么叫冒泡排序呢？因为这种排序算法的每一个元素都可以像小气泡一样，根据自身的大小，一步步向数组的一侧移动。
我们可以看到，这第一轮中的9，一直慢慢的“飘到”数组的最后，这就是为什么这种算法被称为的冒泡排序的原因之一。同时，我们观察到，他是两两逐个比较的，一旦一个元素比他的右边的元素要大，就交换两者的位置，如果是小于或者等于就不做变动。
下面是从网络上找到的一个冒泡排序的完整图：
既然知道了冒泡排序的过程，我们来看看冒泡排序的代码实现：
void BubbleSort1(int array[], int len)
{
int i, j;
for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - i - 1; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
因为冒泡排序是两两相互比较，所以对于有n个元素的数组，我们只需要进行n-1次循环，就可以把他排好序。然后我们每一轮排序都可以找到一个最大的数，把他“归位”，所以在下一次比较中，我们只需比较元素个数减去轮次即可，即代码中的 j < len - i - 1。
就这样，冒泡排序就完成了，他是一个很简单的排序算法，可以说其他的很多算法都是由冒泡排序演变过来的，比如快速排序，归并排序，堆排序。
但是，不知道你发现了没有，当数组其实已经排好序了，但是我们的程序还不知道，所以他还是进行了两两比较的过程。
为了解决这一点，我们可以设置一个标志符号，用来判断，这一轮的排序是否继续了交换，代码如下：
void BubbleSort2(int array[], int len)
{
int i, j;
for (i = 0; i < len - 1; i++) {
int isChange = 1;
for (j = 0; j < len - i - 1; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
isChange = 0;
}
}
if (isChange) break;
}
}
但是，我们还发现了一个问题，什么问题呢？看下图：
元素44，46，47明明已经排好序了，而冒泡排序还是傻傻的将他们进行了比较。我们思考一下，该如何解决这个问题呢？
其实，我们可以记录最后一次发生交换的位置，然后下一轮排序的边界就是这个最后一次发生交换的下标。为什么呢？因为只要这一轮排序还没有到达这一轮排序的末尾边界，他又从这一轮排序中某个位置后，没有发生交换的过程。等到下一次排序碰到这个位置后的数字的时候，是不会发生交换的。这就说明这个最后一次发生交换的元素后面的其他所有元素，都是已经排好序的了。
看起来有点复杂，我们不妨想一想，这一次我们遇到44、46、47的时候我们是没有发生交换的过程的。等这一轮排序结束后，47就已经归位了。下一轮，到44、46的时候，我们又比较了一次，但是他们没有发生交换，也就是说，我们在这里多比较了几次。我们优化的思路就是来源于这。
试思考代码：
void BubbleSort3(int array[], int len)
{
int i, j;
int lastChangIndex = 0;
int sortBorder = len - 1;
for (i = 0; i < len - 1; i++) {
int isChange = 1;
for (j = 0; j < sortBorder; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
isChange = 0;
lastChangIndex = j;
}
}
sortBorder = lastChangIndex;
if (isChange) break;
}
}
这里我们记录每轮排序最后一次发生交换的位置sortBorder，因为我们的算法是，每次找到最大的元素，然后把他“固定”好，所以，在sortBorder后面的元素一定是排好序的了。
本文到这里就结束了，希望对你有帮助，谢谢！
