转载

冒泡排序及其复杂度分析

  • 问题:给定一个整数序列,按照从小到大的顺序(确切地说,是非递减的顺序)排列序列中的整数。
  • 输入:一个整数序列。
  • 输出:整数序列,其中的整数升序排列。

因为谭浩强的C语言教材,大家最熟悉的可能就是冒泡排序。

下面是冒泡排序的一个C语言实现, a 是数组首地址, size 是数组元素的个数。

冒泡排序的思想,是让最大的数浮动到数组最后的位置,其次大的数浮动到数组倒数第二个位置……当然,你也可以从大到小排序,也可以从后向前冒泡。其特征操作是相邻元素的比较和交换。

void bubble_sort(int *a, int size) {   int i, j, t;   for(i = 1; i < size; ++i){     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;       }     } // end for j   }// end for i }

时间复杂度分析。其外层循环执行 N - 1次。内层循环最多的时候执行N次,最少的时候执行1次,平均执行 (N+1)/2 次。

所以循环体内的比较交换约执行 (N - 1)(N + 1) / 2 = (N^2 - 1)/2 (其中 N^2 是仿照Latex中的记法,表示N的平方)。按照计算复杂度的原则,去掉常数,去掉最高项系数,其复杂度为 O(N^2)

冒泡算法的性能改进。上述算法的性能还有改进的空间。给定一个整数序列 [9, 3, 4, 5, 7] ,每完成一次上述算法的外层循环,整数序列变化为:

9, 3, 4, 5, 7 3, 4, 5, 7, 9 (i = 1) 3, 4, 5, 7, 9 (i = 2) 3, 4, 5, 7, 9 (i = 3) 3, 4, 5, 7, 9 (i = 4)

我们发现当第一次外层循环完成后,排序就完成了。后面的循环只有比较,而没有交换。

当一次外层循环中,相邻的元素没有发生交换,就说明数组已经是有序的了,这时可以跳出循环。

这样,我们可以设置一个布尔变量,记录一次外层循环中是否发生交换,如果未发生交换,算法就返回。

改进的冒泡排序的C语言实现如下:

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;  } } 

按照改进的算法,对于一个已经有序的数组,算法完成第一次外层循环后就会返回。

实际上只发生了 N - 1次比较,所以最好的情况下,该算法复杂度是 O(N)

2015-03-18 Wed

正文到此结束
Loading...