例题 图4.7是用C语言写出的交换排序的例子。

  void sorting( int X[ ], int n )
{
int i, j, temp;
if ( n < 2 ) return;
for ( i = 1; i < n; i++ )
for ( j = n-1; j >= i; j-- )
if ( X[j-1] > X[j] )
{ temp = X[j-1]; X[j-1] = X[j]; X[j] = temp; }
}

操作数

计数

操作符

计数

X

6

;

8

n

3

数组下标

6

i

4

for ( )

2

j

9

if ( )

2

temp

2

=

5

2

1

{  }

1

1

5

<

2

n2 = 7

N2 = 30

>=

1

   

>

1

   

++

1

   

--

1

   

-

4

   

缺";"的表达式结束

4

   

Return

1

   

程序结束

1

   

n1 = 15

N1 = 40


图4.7 一个交换排序程序的例子
　　　
  因此有预测的词汇量
H = n1 * log2n1 + n2 * log2n2 = 15 * log215 + 7 * log27 = 78.25
实际的词汇量 N = N1 + N2 = 40 + 30 = 70
程序的词汇表 n = n1 + n2 = 15 + 7 = 22
