数据结构

　1.3.3 算法效率的衡量方法

例1.3 对 n 个整数的序列进行起泡排序。其中序列的"长度" n 为问题的规模。

算法 1.3
　　void bubble_sort(int a[], int n)
　{
　　// 将 a 中整数序列重新排列成自小至大有序的整数序列。
　　for (i=n-1, change=TRUE; i>1 && change; --i) {
　　　change = FALSE;
　　　for (j=0; j<i; ++j)
　　　　if (a[j] > a[j+1])
　　　　　{ w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE }
　　}
　} // bubble_sort

　　算法的时间复杂度为O (n²) 。

　　从这三个例子可见，算法时间复杂度取决于最深循环内包含基本操作的语句的重复执行次数，称语句重复执行的次数为语句的"频度"。

　
　　起泡排序有两个结束条件，或i=1或"一趟起泡" 中没有进行过一次交换操作，后者说明该序列已经有序。因此起泡排序的算法执行时间和序列中整数的初始排列状态有关，它在初始序列本已从小到大有序时达最小值，而在初始序列从大到小逆序时达最大值，在这种情况下，通常以最坏的情况下的时间复杂度为准。

　　起泡排序的两种过程如动画所示。