C语言：数组长度与数组排序

1、数组长度

在实际编程中，有时数组的长度不能提前确定，如果这个变化范围小，那么使用常量表达式定义一个足够大的数组就可以，如果这个变化范围很大，就可能会浪费内存，这时就可以使用变长数组。请看下面的代码：

1. #include <stdio.h>
2. int main()
3. {
4. int n;
5. printf("Input string length: ");
6. scanf("%d", &n);
7. scanf("%*[^\\n]"); scanf("%*c"); //清空输入缓冲区
8. char str[n];
9. printf("Input a string: ");
10. gets(str);
11. puts(str);
12.
13. return 0;
14. }

变量的值在编译期间并不能确定，只有等到程序运行后，根据计算结果才能知道它的值到底是什么，所以数组长度中一旦包含了变量，那么数组长度在编译期间就不能确定了，也就不能为数组分配内存了，只有等到程序运行后，得到了变量的值，确定了具体的长度，才能给数组分配内存，我们将这样的数组称为变长数组(VLA, Variable Length Array)。

普通数组（固定长度的数组）是在编译期间分配内存的，而变长数组是在运行期间分配内存的。

变长数组仍然是静态数组

注意，变长数组是说数组的长度在定义之前可以改变，一旦定义了，就不能再改变了，所以变长数组的容量也是不能扩大或缩小的，它仍然是静态数组。以上面的代码为例，第 8 行代码是数组定义，此时就确定了数组的长度，在此之前长度可以随意改变，在此之后长度就固定了。

一种“自欺欺人”的写法

有些初学者在使用变长数组时会像下面一样书写代码：

1. int n;
2. int arr[n];
3. scanf("%d", &n);

先定义一个变量 n 和一个数组 arr，然后用 scanf() 读入 n 的值。有些初学者认为，scanf() 输入结束后，n 的值就确认下来了，数组 arr 的长度也随即确定了。这种想法看似合理，其实是蛮不讲理，毫无根据。

从你定义数组的那一刻起（也就是第二行代码），数组的长度就确定下来了，以后再也不会改变了；改变 n 的值并不会影响数组长度，它们之间没有任何“联动”关系。用 scanf() 读入 n 的值，影响的也仅仅是 n 本身，不会影响数组。 那么，上面代码中数组的长度究竟是什么呢？鬼知道！n 是未初始化的局部变量，它的值是未知的。 修改上面的代码，将数组的定义放到最后就没问题了：

1. int n;
2. scanf("%d", &n);
3. int arr[n];

在定义数组之前就输入 n 的值，这样输入的值才有用武之地。

2、数组排序

在实际开发中，有很多场景需要我们将数组元素按照从大到小（或者从小到大）的顺序排列，这 样在查阅数据时会 更加直观，例如：

 一个保存了班级学号的数组，排序后更容易分区好学生和坏学生；

 一个保存了商品单价的数组，排序后更容易看出它们的性价比。

对数组元素进行排序的方法有很多种，比如冒泡排序、归并排序、选择排序、插入排序、快速排 序等，其中最经典 最需要掌握的是「冒泡排序」。

以从小到大排序为例，冒泡排序的整体思想是这样的：

 从数组头部开始，不断比较相邻的两个元素的大小，让较大的元素逐渐往后移动（交换两个 元素的值），直到 数组的末尾。经过第一轮的比较，就可以找到最大的元素，并将它移动到最 后一个位置。

 第一轮结束后，继续第二轮。仍然从数组头部开始比较，让较大的元素逐渐往后移动，直到数组的倒数第二个元素为止。经过第二轮的比较，就可以找到次大的元素，并将它放到倒数第二个位置。  以此类推，进行 n-1（n 为数组长度）轮“冒泡”后，就可以将所有的元素都排列好。

整个排序过程就好像气泡不断从水里冒出来，最大的先出来，次大的第二出来，最小的最后出来，所以将这种排序方式称为冒泡排序（Bubble Sort）。

下面我们以“3 2 4 1”为例对冒泡排序进行说明。

第一轮 排序过程 3 2 4 1 （最初） 2 3 4 1 （比较 3 和 2，交换） 2 3 4 1 （比较 3 和 4，不交换） 2 3 1 4 （比较 4 和 1，交换） 第一轮结束，最大的数字 4 已经在最后面，因此第二轮排序只需要对前面三个数进行比较。

第二轮 排序过程 2 3 1 4 （第一轮排序结果） 2 3 1 4 （比较 2 和 3，不交换） 2 1 3 4 （比较 3 和 1，交换） 第二轮结束，次大的数字 3 已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。 第三轮 排序过程 2 1 3 4 （第二轮排序结果） 1 2 3 4 （比较 2 和 1，交换）

至此，排序结束。

算法总结及实现 对拥有 n 个元素的数组 R[n] 进行 n-1 轮比较。 第一轮，逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-1], R[N])，最大的元素被移动到 R[n] 上。 第二轮，逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-2], R[N-1])，次大的元素被移动到 R[n-1] 上。 以此类推，直到整个数组从小到大排序。

具体的代码实现如下所示：

1. #include <stdio.h>
2. int main() {
3. int nums[10] = { 4, 5, 2, 10, 7, 1, 8, 3, 6, 9 };
4. int i, j, temp;
5.
6. //冒泡排序算法：进行 n-1 轮比较
7. for (i = 0; i<10 - 1; i++) {
8. //每一轮比较前 n-1-i 个，也就是说，已经排序好的最后 i 个不用比较
9. for (j = 0; j<10 - 1 - i; j++) {
10. if (nums[j] > nums[j + 1]) {
11. temp = nums[j];
12. nums[j] = nums[j + 1];
13. nums[j + 1] = temp;
14. }
15. }
16. }
17.
18. //输出排序后的数组
19. for (i = 0; i<10; i++) {
20. printf("%d ", nums[i]);
21. }
22. printf("\\n");
23.
24. return 0;
25. }

运行结果： 1 2 3 4 5 6 7 8 9 10

优化算法

上面的算法是大部分教材中提供的算法，其中有一点是可以优化的：当比较到第 i 轮的时候，如果剩下的元素已经排序好了，那么就不用再继续比较了，跳出循环即可，这样就减少了比较的次数，提高了执行效率。

未经优化的算法一定会进行 n-1 轮比较，经过优化的算法最多进行 n-1 轮比较，高下立判。

优化后的算法实现如下所示：

1. #include <stdio.h>
2. int main() {
3. int nums[10] = { 4, 5, 2, 10, 7, 1, 8, 3, 6, 9 };
4. int i, j, temp, isSorted;
5.
6. //优化算法：最多进行 n-1 轮比较
7. for (i = 0; i<10 - 1; i++) {
8. isSorted = 1; //假设剩下的元素已经排序好了
9. for (j = 0; j<10 - 1 - i; j++) {
10. if (nums[j] > nums[j + 1]) {
11. temp = nums[j];
12. nums[j] = nums[j + 1];
13. nums[j + 1] = temp;
14. isSorted = 0; //一旦需要交换数组元素，就说明剩下的元素没有排序好
15. }
16. }
17. if (isSorted) break; //如果没有发生交换，说明剩下的元素已经排序好了
18. }
19.
20. for (i = 0; i<10; i++) {
21. printf("%d ", nums[i]);
22. }
23. printf("\\n");
24.
25. return 0;
26. }

我们额外设置了一个变量 isSorted，用它作为标志，值为“真”表示剩下的元素已经排序好了，值为“假”表示剩下的元素还未排序好。

每一轮比较之前，我们预先假设剩下的元素已经排序好了，并将 isSorted 设置为“真”，一旦在比较过程中需要交换元素，就说明假设是错的，剩下的元素没有排序好，于是将 isSorted 的值更改为“假”。

每一轮循环结束后，通过检测 isSorted 的值就知道剩下的元素是否排序好。

原文地址：https://blog.csdn.net/qq_45398836/article/details/144150500

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！