5.6 按引用调用的冒泡排序

优质

小牛编辑

129浏览

2023-12-01

下面将图 4.16 的冒泡排序程序修改成用两个函数 bubbleSort 和 swap（如图 5.15）。函数 bubbleSort 进行数组排序，它调用函数 swap，变换数组元素 array[j) 和 array[j+1] 记住，C++ 强制函数之间的信息隐藏，因此 swap 并不能访问 bubbleSort 中的各个元素。由于 bubbleSort 要求 swap 访问交换的数组元素，因此 bubbleSort 要将这些元素按引用调用传递给 swap，每个数组元素的地址显式传递。

尽管整个数组自动按引用调用传递，但各个数组元素是标量，通常按值调用传递。因此，bubbleSort 对 swap 调用中的每个数组元素使用地址运算符(&)，如下所示的语句：

swap( &array[ j ], array[j+ 1]);

实现按引用调用。函数 swap 用指针变量 element1Ptr 接收 &array[j] 。由于信息隐藏，swap 并不知道名称 &array[j] ，但 swap 可以用 *element1Ptr 作为 &array[j] 的同义词。这样，swap 引用 *element1Ptr 时，实际上是引用 bubbleSort 中的 &array[j] 。同样，swap 引用 *element2Ptr 时，实际上是引用 bubbleSort 中的 array[j+1] 。虽然 swap 不能用：

hold = array [ j ];
array[ j ] = array[ j + 1 ];
array[ j + 1 ] = hold;

但图 5.15 中的 swaP 函数用

hold = * element1Ptr;
*element1Ptr = *element2Ptr;
*element2Ptr = hold;

达到相同的效果。

1 // Fig. 5.15: fig05_15.cpp
2 // This program puts values into an array, sorts the values into
3 // ascending order, and prints the resulting array.
4 #include <iostream.h>
5 #include <iomanip.h>
6
7 void bubbleSort{ int *, const int );
8
D int main(}
l0 {
11 const int arraySize = 10;
12 int a[ arraySize ) = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
13 int i;
14
15 cout << "Data items in original order\n";
16
17 for ( i = 0; t < arraySize; i++ )
18 cout << setw( 4 ) << a[ i ];
19
20 bubbleSort( a, arraySize ); // sort the array
21 cout << "\nData items inascending order\n";
22
23 for ( i = 0; i < arraySize; i++ )
24 cout << setw( 4 ) << a[ i ];
25
26 cout << endl;
27 return 0;
28 }
29
30 void bubbleSort( int *array, const int size )
31 {
32 void swap( int *, iht * );
33
34 for (int pass = 0; pass < size - 1; pass++ )
35
36 for (int j = 0; j < size - 1; j++ )
37
38 if ( array[ j ] > array[ j + 1 ] )
39 swap( &array[ j ], &arra[ j + 1 ] );
4O }
41
42 void swap( int *element1Ptr, int *element2Ptr )
43 {
44 int hold = *elementlPtr;
45 *element1Ptr = *element2Ptr;
46 *element2Ptr = hold;
47 }

输出结果：

Data item： in Original Order
2 6 4 8 10 12 89 68 45 37
Data items in ascendinq Order
2 4 6 8 lO 12 37 45 68 89

图 5.15 按引用调用的冒泡排序

注意函数 bubbleSort 中的几个特性。函数首部中将 array 声明为 int* array 而不是 int array[] ，表示 bubbleSort 接收单下标数组作为参数(这些符号是可以互换的)。参数size声明为 const 以保证最低权限原则。尽管参数 size 接收 main 中数值的副本，且修改该副本并不改变 main 中的值，但是 bubbleSort 不必改变 size 即可完成任务。bubbleSort 执行期间数组的长度保持不变，因此，size 声明为 const 以保证不被修改。如果排序过程中修改数组长度，则排序算法无法正确执行。

bubbleSort 函数体中包括了函数swap的原型，因为它是调用 swap 的惟一函数。将原型放在 bubbleSort 中，使得只能从 bubbleSort 正确地调用 swap。其他函数要调用 swap 时无法访问正确的函数原型，这通常会造成语法错误，因为 C++ 需要函数原型。

软件工程视点 5.4
将函数原型放在其他函数中能保证最低权限原则，只能从该原型所在函数中正确地调用。

注意函数 bubbleSort 接收数组长度参数。函数必须知道数组长度才能排序数组。数组传递到函数时，函数接收数组第一个元素的内存地址。数组长度要单独传递给函数。
通过将函数 bubbleSort 定义成接收数组长度作为参数，可以让函数在排序任何长度单下标整型数组的程序中使用。

软件工程视点 5.5
向函数传递数组时，同时传递数组长度（而不是在函数中建立数组长度信息），这样能使函数更加一般化，以便在许多程序中复用。

数组长度可以直接编程到函数内，这样会把函数的使用限制在特定长度的数组并减少其复用性。程序中只有处理特定长度的单下标整型数组时才能使用这个函数。

C++提供一元运算符 sizeof，确定程序执行期间的数组长度或其他数据类型长度(字节数)。采用数组名时(如图5.16所示)，sizeof 算符返回数组中的总字节数为 size_t 类型的值，通常是 unsigned int 类型。这里使用的计算机将 float 类型的变量存放在4字节内存中，array 声明为20个元素，因此 array 使用 80 字节内存空间。在接收数组参数的函数中采用指针参数时，sizeof 运算符返回指针长度的字节数（4）而不是数组长度。

常见编程错误 5.7
在函数中用 sizeof 运算符寻找数组参数长度的字节数时返回指针长度的字节数而不是数组长度的字节数。

1 // Fig. 5.16: fig05_16.cpp
2 // Sizeof operator when used on an array name
3 // returns the number of bytes in the array.
4 #include <iostream.h>
5
6 size_t getSize( float * );
7
8 int main()
9 {
10 float array[ 20 ];
11
12 cout << "The number of bytes in the array is"
13 << sizeof( array )
14 << "\nThe number of bytes returned by getSize is"
15 << getSize( array ) << endl;
16
17 return 0;
18 }
19
20 size_t getSize( float *ptr )
21 {
22 return sizeof( ptr );
23 }

输出结果：

The number of bytes in the array is 80
The number of bytes returned by getSize is 4

图 5.16 采用数组名时，sizeof 运算符返回数组中的总字节数

数组中的元素个数也可以用两个 sizeof 操作的结果来确定。例如，考虑下列数组声明：

double realArray[ 22 ]；

如果 double 数据类型的变量存放在8个字节的内存中，则数组 realArray 总共包含176个字节。要确定数组中的元素个数，可以用下列表达式：

sizeof realArray/sizeof(double)

这个表达式确定 realArray 数组中的字节数．并将这个值除以内存中存放—个 double 值的字节数，图 5.17 的程序用 size 运算符计算我们所用的个人计算机上存放每种标准数据类型时使用的字节数。

可移植性提示 5.3
存放特定数据类型时使用的字节数随系统的不同而不同。编写的程序依赖于数据类型长度而且要在几个计算机系统上运行时，用sizeof确定存放这种数椐类型时使用的宇节数。

1 // Fig. 5.17:fig05 17.cpp
2 // Demonstrating the sizeof operator
3 ~include <iostream.h>
4 ~include <iomanip.h>
5
76 ~nt main(}
8 char c;
9 short s;
10 iht i;
11 long 1;
12 float f;
13 double d;
14 long double ld;
15 int arras 20 ], *ptr = array;
16
17 cout << "sizeof c = " << sizeof c
18 << "\tsizeof(char) =" << sizeof( char )
19 << "\nsizeof s = "<< sizeof s
20 << "\tsizeof(short) = "<< sizeof( short )
2I "\nsizeof i = " << sizeof i
22 << "\tsizeof(int) =" << sizeof (int )
23 "\nsizeof 1 = "<<sizeof 1
24 << "\tsizeof(long) =" << sizeof( long )
25 << "\nsizeof f = "<< sizeof f
27 "\nsizeof d =" << sizof d
28 << "\tsizeof(double) =" << sizeof( double )
29 << "\nsizeof ld =" << sizeof ld
30 << "\tsizeof(long double) = "<< sizeof( long double )
31 << "\nsizeof array = "<< sizeof array
32 << "\nsizeof ptr = "<< sizeof ptr
33 << endl;
34 return 0;
35 }

输出结果:

sizeof c = 1 sizeof(char) = 1
sizeof s = 2 sizeof(short) = 2
sizeof i = 4 sizeof(int) = 4
sizeof l = 4 sizeof(long) = 4
sizeof f = 4 sizeof(float) = 4
sizeof d = 8 sizeof(double) = 8
sizeof ld = 8 sizeof(long double) = 8
sizeof array =
sizeof ptr = 4

图 5.17 用 sizeof 运算符计算存放每种标准数据类型时使用的字节数

sizeof 运算符可以用于任何变量名、类型名或常量值。用于变量名（不是数组名）和常量值时，返回存放特定变量或常量类型所用的字节数。注意，如果提供类型名操作数，则 sizeof 使用的括号是必需的；如果提供变量名操作数，则 sizeof 使用的括号不是必需的。记住，sizeof是个运算符而不是个函数。

常见编程错误 5.8
如果提供类型名操作数，而不在sizeof操作中使用括号则是个语法错误。

性能提示 5.2
sizeof 属于编译时的一元运算符，而不是个执行时函数。这样，使用 sizeof 并不对执行性能遣成不良影响。