冒泡排序算法之二
版权所有，转载请注明：本文出自学与思编程网
在前篇冒泡排序的文章中，我们分析了冒泡排序的基本思想，也用C语言实现了该排序算法，但那个代码没有做任何优化处理，本文就来分析一下如何优化它。
从前篇文章的分析我们可以看到，在冒泡排序过程中，每一轮排序都可以把其中一个元素正确的放在其最终所在的位置上，所以我们要对n个元素排序的话，我们最多只需n轮处理（其实是n-1轮，因为既然n-1轮可以找到n-1个元素的正确位置，那么最后那个元素的位置也就唯一确定了）。既然最多只需n轮处理，那么有时是否可以减少几轮处理呢，答案是肯定的。我们可以想象一个极端的例子，比如，待排序的元素本身就已经是按正序排列好了的，这时很显然我们在第一轮处理完成后，就应该发现所有的元素就已经排好序了，我们不必要再进行更多轮的处理了。那么我们怎么才能让代码在一轮处理完成后检查是否已经完成排序了呢？其实很简单，我们只需在代码中添加一个标志变量，让它记录这一轮处理是否发生了元素交换，如果整个一轮都没有交换过元素，也就是没有发现反序的元素，那么当然所有的元素都已经排序好了塞。下面看看改进后的代码，加粗字体为改进部分：
void bubblesort(int a[], int count) //升序
{
int i, j;
int tmp;
int exchanged;
for (i = 0; i < count – 1; i++) {
exchanged = 0;
for (j = 0; j < count – 1; j++) {
if (a[j] > a[j + 1]) {
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
exchanged = 1;
}
}
if (exchanged == 0) { //no exchange
break;
}
}
return;
}
优化后的代码从平均上来说要优于没有优化的，因为在很多情况下，它可以减少外循环的次数，这样算法的平均效率得到了提高。
下面我们再来看看另外一个优化，这次我们来优化内循环，也就是减少每一轮处理的元素个数。
认真看前面的代码，就会发现每一轮我们都处理了n-1个元素，但从冒泡排序基本过程中我们可以看到，每进行一轮处理就多一个已经排序好了的元素，即多一个已经找到正确位置的元素，而且在我们这个整数升序排序的例子中这些已经排好序的元素一定位于数组的尾巴上，那么我们在下一轮处理时就应该可以不管已经找到正确位置的元素了，这样就不用处理它们了，达到了优化目的。看看下面的代码比看文字更容易理解，加粗字体为改动部分，只需改动一行！
void bubblesort(int a[], int count) //升序
{
int i, j;
int tmp;
int exchanged;
for (i = 0; i < count – 1; i++) {
exchanged = 0;
for (j = 0; j < count – 1 – i; j++) {
if (a[j] > a[j + 1]) {
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
exchanged = 1;
}
}
if (exchanged == 0) { //no exchange
break;
}
}
return;
}
冒泡排序的优化我们就分析到这里。顺便提醒一下的是学算法就要多思考，要理解其基本思想而不是把代码背下来。还要多实践，虽然很多东西看起来很简单，但自己做起来就有可能出错，所以没事的时候多在电脑写写代码，多调试调试些程序，这样会学得比较快，掌握得比较牢。
下篇我们将讨论一下冒泡排序的一个扩展，双向冒泡排序。
版权所有，转载请注明：本文出自学与思编程网
