c语言知识点:数组作为函数参数--以冒泡排序为例

1.冒泡排序的错误设计

#include

void bubble_sort(int arr[])
{
	int sz = sizeof(arr) / sizeof(arr[0]);//!!!坑点就在这里
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])//升序
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}


int main()
{
	int arr[] = { 4,3,6,8,1,8,9,5,10,20 };
	bubble_sort(arr);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

通过运行结果可以看到，这个代码并没有将实现排序功能

2.知识点！！！看完就能理解上述代码错误所在

那问题在哪呢，我们调试看看(x86环境)

可以看到，这里的sz是1，不是我们期待的10。难道数组作为函数参数的时候，不是把整个数组的传递过去？
再介绍原因之前，我们先来看一个例子

#include

int main()
{
	int arr[10] = { 1,2,3,4,5 };
	printf("%p\n", arr);
	printf("%p\n", &arr[0]);
	printf("%p\n", *arr);
	printf("%d\n", sizeof(arr));

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

运行结果

这里设计到的知识点：
sizeof(数组名)，计算整个数组的大小，sizeof内部单独放一个数组名，数组名表示整个数组。
&数组名，取出的是数组的地址。&数组名，数组名表示整个数组。

除此1,2两种情况之外，所有的数组名都表示数组首元素的地址。
所以我们看上面那张截图，第一组(arr)和第二组(&arr[0])相差的都是4，因为这个差值就是一个指针的大小。而第三组(&arr)差值就是40，这里是整个数组，40也就是10个int类型的大小

知道这些，我们就可以来解释一下为什么最开始的那个代码是错误的了
原因:当数组传参的时候，实际上只是把数组的首元素的地址传递过去了。所以即使在函数参数部分写成数组的形式： int arr[] 表示的依然是一个指针： int *arr 。那么，函数内部的 sizeof(arr) 结果是4。

3.冒泡排序的正确设计(两种方法哦)

#include

#define SIZE 10 //好处一:方便一键修改整个程序代码用到的有关arr数组长度的地方
				//好处二:避免了上面那个错误写法由于对数组元素个数计算不清造成的错误
void bubble_sort(int arr[])
{
	int i = 0;
	int j = 0;
	for (i = 0; i < SIZE - 1; i++)//SIZE个数总共需要扫描SIZE趟，因为到最后一个数的时候就不需要再扫描了(一趟就是指从当前这个数一直比到最后，这个最后不是整个数组的最后，而是每次j循环到的最后一个数的前一个数)
	{
		for (j = 0; j < SIZE - i - 1; j++)//每一趟扫描到a[SIZE-i-2]与a[SIZE-i-1]比较为止结束，因为SIZE-i这个数已经是按顺序放好了的数
		{
			if (arr[j] > arr[j + 1])//升序用大于，降序用小于
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
	int arr[] = { 4,3,6,8,1,8,9,5,10,20 };
	bubble_sort(arr);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include

void bubble_sort(int arr[],int sz)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)//SIZE个数总共需要扫描SIZE趟，因为到最后一个数的时候就不需要再扫描了(一趟就是指从当前这个数一直比到最后，这个最后不是整个数组的最后，而是每次j循环到的最后一个数的前一个数)
	{
		for (j = 0; j < sz - i - 1; j++)//每一趟扫描到a[SIZE-i-2]与a[SIZE-i-1]比较为止结束，因为SIZE-i这个数已经是按顺序放好了的数
		{
			if (arr[j] > arr[j + 1])//升序用大于，降序用小于
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
	int arr[] = { 4,3,6,8,1,8,9,5,10,20 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr,sz);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

4.补充:冒泡排序的原理

先看左边这个图，从第一个元素9开始，和第二个元素8比较，如果9比8大，那就9和8交换位置，然后就在和第三个元素相比如果比他大，那再交换位置，如果没有他大的话，那就不交换位置，继续和下一个元素比较。一直比到数组的最后一个元素，这就是一趟冒泡排序。
然后在从第二个元素开始第二趟冒泡排序。总共需要进行n-1趟冒泡排序(n为元素个数)，因为n-1趟结束之后，第n个元素不用再进比较了(后面已经没有元素了)

5.心得体会

我们在用二分法的时候，虽然它很高效，但是必须针对的是有序的数组，所以对于无序的数组时，可以先用冒泡排序或者快排（快排我也会单独写一篇文章，可以去主页看看）将其变为有序的数组！