排序算法(3)——冒泡排序

1、冒泡排序的思想

依次比较相邻的两个数，将大数放在前面，小数放在后面。 具体的步骤： 首先从数列开头比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续完成第一趟，最小数将沉到底部。 重复以上过程直至最终完成排序。

2、冒泡排序的实现

void bubble_sort(int *a, int size) { int i, j, t; for(i = 1; i < size; ++i)//n-1次（后n-1个元素排好序，第1个自然就是最小的） { for(j = 0; j < size -i; ++j)//每有一个元素排好序，比较次数就少1 { if(a[j] > a[j+1]){ t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } // end for j }// end for i }

对于上边的bubble_sort(),我们发现当第一次外层循环完成后，排序就完成了，后面的循环只有比较，而没有交换。这样，我们可以设置一个布尔变量，记录一次外层循环中是否发生交换，如果未发生交换，算法就返回。改进后的代码如下bubble_sort_enhanced()所示。

void bubble_sort_enhanced(int *a, int size) { int i, j, t; unsigned char swapped; for(i = 1; i < size; ++i) { swapped = 0; for(j = 0; j < size - i; ++j) { if(a[j] > a[j+1]){ t = a[j]; a[j] = a[j+1]; a[j+1] = t; swapped = 1; } } if(!swapped) break; } }

3、冒泡排序的性能

1）、时间复杂度 平均时间复杂度接近于最差时间复杂度，是O(n^2)。因为逆序情况下比较和交换次数均为(n-1)+(n-2)+…+i+…1,即n*(n-1)/2。 最好的情况下，该算法复杂度是O(n)。因为按照改进的算法，对于一个已经有序的数组，算法完成第一次外层循环后就会返回。实际上只发生了 N - 1次比较。

2）、稳定性 冒泡排序是稳定的。

和其它层算法的比较： 快速排序和冒泡排序都是基于比较的排序。