3.4.3 一维数组的排序
在操作数组时，经常需要对数组中的元素进行排序。
3.4.3.1 冒泡排序法
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
3.4.3.1.1 初级 - 揭秘冒泡排序原生模样
在冒泡排序的过程中，不断地比较数组中相邻的两个元素，较小者向上浮，较大者往下沉，整个过程和水中气泡上升的原理相似，接下来，分步骤讲解冒泡排序的整个过程，具体如下：
- 第一步，从第一个元素开始，将相邻的两个元素依次进行比较，直到最后两个元素完成比较。如果前一个元素比后一个元素大，则交换它们的位置。整个过程完成后，数组中最后一个元素自然就是最大值，这样也就完成了第一轮的比较。
- 第二步，除了最后一个元素，将剩余的元素继续进行两两比较，过程与第一步相似，这样就可以将数组中第二大的数放在倒数第二个位置。
- 第三步，依次类推，持续对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较为止。
#include <stdio.h> int main() { /* 要求：将arr数组的元素排列顺序变为由小到大排序 */ //定义一个数组并初始化 int arr[5] = { 8,9,6,7,5 }; int temp; /* 第一轮排序：将最大的元素值放到arr[4]即最后一个位置上 涉及到比较的是该数组前五个元素 */ for (int i = 0; i < 4; i++) { //发现下标小的元素值大于下标大的元素值 if (arr[i] > arr[i + 1]) { //则交换两个元素位置 temp = arr[i]; arr[i] = arr[i+1]; arr[i + 1] = temp; } } //打印第一轮排序后的结果 printf("第一轮排序后的结果："); for (int j = 0; j < 5; j++) { printf("%d ", arr[j]); } //第一轮排序后的结果：8 6 7 5 9 printf("\n\n"); /* 第二轮排序：将第二大的元素值放到arr[3]即倒数第二个位置上 涉及到比较的是该数组前四个元素 */ for (int i = 0; i < 3; i++) { //发现下标小的元素值大于下标大的元素值 if (arr[i] > arr[i + 1]) { //则交换两个元素位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } //打印第二轮排序后的结果 printf("第二轮排序后的结果："); for (int j = 0; j < 5; j++) { printf("%d ", arr[j]); } //第二轮排序后的结果：6 7 5 8 9 printf("\n\n"); /* 第三轮排序：将第三大的元素值放到arr[2]即倒数第三个位置上 涉及到比较的是该数组前三个元素 */ for (int i = 0; i < 2; i++) { //发现下标小的元素值大于下标大的元素值 if (arr[i] > arr[i + 1]) { //则交换两个元素位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } //打印第三轮排序后的结果 printf("第三轮排序后的结果："); for (int j = 0; j < 5; j++) { printf("%d ", arr[j]); } //第三轮排序后的结果：6 5 7 8 9 printf("\n\n"); /* 第四轮排序：将第四大的元素值放到arr[1]即倒数第四个位置上 涉及到比较的是该数组前两个元素 */ for (int i = 0; i < 1; i++) { //发现下标小的元素值大于下标大的元素值 if (arr[i] > arr[i + 1]) { //则交换两个元素位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } //打印第四轮排序后的结果 printf("第四轮排序后的结果："); for (int j = 0; j < 5; j++) { printf("%d ", arr[j]); } //第四轮排序后的结果：5 6 7 8 9 printf("\n\n"); //到这里其实就结束了，因为一共只有五个元素，我们已经对四个大的元素进行了排序，那最小的肯定也就在arr[0]的位置上了 return 0; }
3.4.3.1.2 中级 - 原生模样合并
原生模样的代码，我们一共进行了四轮排序，而该数组一共有五个元素，因此 排序轮数 = 数组元素个数 - 1
仔细看原生模样的代码，其实可以发现，每一次for循环排序的结构都是差不多的，只不过是在for循环的循环条件判断 上是递减趋势，即：
- 第一轮排序：i < 4
- 第二轮排序：i < 3
- 第三轮排序：i < 2
- 第四轮排序：i < 1
这个 i 需要小于的数我们设为 num ，分别取了4、3、2、1。
这也很容易可以出来，num = 数组元素个数 - 当前轮数
因此我们可以：
- 以 排序轮数 作为 外层循环，循环
数组元素个数 - 1次 - 以 相邻元素比较 内层循环，循环
数组元素个数 - 当前轮次次
综上，总结一下：通过嵌套for循环实现了冒泡排序。其中，外层循环用来控制进行多少轮比较，每一轮比较都可以确定一个元素的位置，由于最后一个元素不需要进行比较，因此，外层循环的次数为数组的长度-1，内层循环的循环变量用于控制每轮比较的次数，在每次比较时，如果前者小于后者，就交换两个元素的位置。
#include <stdio.h> int main() { /* 要求：将arr数组的元素排列顺序变为由小到大排序 */ //定义一个数组并初始化 int arr[5] = { 8,9,6,7,5 }; int temp; //数组长度 int length = sizeof(arr) / sizeof(arr[0]); // j+1 表示当前排序轮数 // j < length-1 说明会循环 (数组元素个数 - 1) 次 for (int j = 0; j < length - 1; j++) { // j+1 表示当前排序轮数 // i < length - (j+1) 说明会 相邻元素比较 循环 （数组元素个数-当前排序轮数） 次 for (int i = 0; i < length - (j+1); i++) { //发现下标小的元素值大于下标大的元素值 if (arr[i] > arr[i + 1]) { //则交换两个元素位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } //打印结果 for (int t = 0; t < 5; t++) { printf("%d ", arr[t]); } return 0; }
3.4.3.1.3 高级 - 冒泡排序优化
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，
因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。
#include <stdio.h> int main() { /* 要求：将arr数组的元素排列顺序变为由小到大排序 */ //定义一个数组并初始化 int arr[5] = { 8,9,6,7,5 }; int temp; //设置一个标志 flag 判断元素是否进行过交换 //0表示没有交换，1表示发生交换 //默认为没有交换 int flag; //数组长度 int length = sizeof(arr) / sizeof(arr[0]); // j+1 表示当前排序轮数 // j < length-1 说明会循环 (数组元素个数 - 1) 次 for (int j = 0; j < length - 1; j++) { //在每一轮排序，即元素比较前，默认为没有交换 flag = 0; // j+1 表示当前排序轮数 // i < length - (j+1) 说明会 相邻元素比较 循环 （数组元素个数-当前排序轮数） 次 for (int i = 0; i < length - (j+1); i++) { //发现下标小的元素值大于下标大的元素值 if (arr[i] > arr[i + 1]) { //说明是发生交换的，则设置flag为1 flag = 1; //则交换两个元素位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } /* 该轮排序完毕，判断是否发生过交换 如果该轮发生过交换，则说明我们还需要进行下一轮排序 如果该轮没有发生过交换，则说明全部元素已经按照从小到大排列好了，那我们就不进行下轮排序了 */ if (!flag) { //说明没有发生过交换，则直接跳出外层循环即不进行下轮排序 break; } } //打印结果 for (int t = 0; t < 5; t++) { printf("%d ", arr[t]); } return 0; }
3.4.3.2 选择排序法
3.4.3.2.1 基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到 排序的目的。
3.4.3.2.2 选择排序思想
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值， 与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2] 交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值， 与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。
3.4.3.2.3 思路分析
3.4.3.2.4 代码实现
3.4.3.2.4.1 揭秘选择排序原生模样
#include<stdio.h> int main() { //不指定长度的初始化赋值 --> 数组长度由参与赋值的元素个数决定 int arr[] = { 101,115,119,1 }; //最小值 int minValue; //最小值的那个元素的索引/下标 int minValueIndex; //数组的长度 int length = sizeof(arr) / sizeof(arr[0]); /* 第一轮循环：搜索索引在[0,length-1]即[0,3]内的最小元素值及其索引 */ //假定最小值为 arr[0] minValue = arr[0]; //并标记一下当前索引 - 0 minValueIndex = 0; //将minValue与该索引后面的元素进行遍历比较 for (int j = 0 + 1; j < length; j++) { //发现更小的元素值 if (arr[j] < minValue) { //则将当前最小值minValue设置为该元素值 minValue = arr[j]; //并标记好改元素的索引值 minValueIndex = j; } } //遍历完毕，如果当前最小值标记的索引不是 0 //则将索引为 0 的元素与当前最小值的索引的元素值进行交换 //将最小值放到了 索引为 0 的位置上 if (minValueIndex != 0) { arr[minValueIndex] = arr[0]; arr[0] = minValue; } //打印结果 printf("第一轮循环的结果："); for (int t = 0; t < length; t++) { printf("%d ", arr[t]); } //第一轮排序后的结果：1 115 119 101 printf("\n\n"); /* 第二轮循环：搜索索引在[1,length-1]即[1,3]内的最小元素值及其索引 */ //假定最小值为 arr[1] minValue = arr[1]; //并标记一下当前索引 - 1 minValueIndex = 1; //将minValue与该索引后面的元素进行遍历比较 for (int j = 1 + 1; j < length; j++) { //发现更小的元素值 if (arr[j] < minValue) { //则将当前最小值minValue设置为该元素值 minValue = arr[j]; //并标记好改元素的索引值 minValueIndex = j; } } //遍历完毕，如果当前最小值标记的索引不是 1 //则将索引为 1 的元素与当前最小值的索引的元素值进行交换 //将最小值放到了 索引为 1 的位置上 if (minValueIndex != 1) { arr[minValueIndex] = arr[1]; arr[1] = minValue; } //打印结果 printf("第二轮循环的结果："); for (int t = 0; t < length; t++) { printf("%d ", arr[t]); } //第二轮排序后的结果：1 101 119 115 printf("\n\n"); /* 第三轮循环：搜索索引在[2,length-1]即[2,3]内的最小元素值及其索引 */ //假定最小值为 arr[2] minValue = arr[2]; //并标记一下当前索引 - 2 minValueIndex = 2; //将minValue与该索引后面的元素进行遍历比较 for (int j = 2 + 1; j < length; j++) { //发现更小的元素值 if (arr[j] < minValue) { //则将当前最小值minValue设置为该元素值 minValue = arr[j]; //并标记好改元素的索引值 minValueIndex = j; } } //遍历完毕，如果当前最小值标记的索引不是 2 //则将索引为 2 的元素与当前最小值的索引的元素值进行交换 //将最小值放到了 索引为 2 的位置上 if (minValueIndex != 2) { arr[minValueIndex] = arr[2]; arr[2] = minValue; } //打印结果 printf("第三轮循环的结果："); for (int t = 0; t < length; t++) { printf("%d ", arr[t]); } //第三轮排序后的结果：1 101 115 119 printf("\n\n"); //这里就没必要进行第四次循环了， //因为一共四个元素，我们通过三次循环求出了三个对应范围内的最小值 //因此第四个元素也就到了应到的位置了 return 0; }
3.4.3.2.4.2 合并原生模样代码
原生模样的代码，我们一共进行了三轮排序，而该数组一共有四个元素，因此 排序轮数 = 数组元素个数 - 1
仔细看原生模样的代码，其实可以发现，每一次for循环排序的结构都是差不多的，只不过是比较范围在缩小，即：
- 第一轮排序：起始假定 minIndex = 0 ，与索引范围在[1,3]的元素比较
- 第二轮排序：起始假定 minIndex = 1 ，与索引范围在[2,3]的元素比较
- 第三轮排序：起始假定 minIndex = 2 ，与索引范围在[3,3]的元素比较
这也很容易可以出来：
- minIndex = 当前轮数 - 1
- 比较索引开始值 = minIndex + 1
#include<stdio.h> int main() { //不指定长度的初始化赋值 --> 数组长度由参与赋值的元素个数决定 int arr[] = { 101,34,119,1 }; //最小值 int minValue; //最小值的那个元素的索引/下标 int minValueIndex; //数组的长度 int length = sizeof(arr) / sizeof(arr[0]); //循环 length-1 次，对应 (length-1) 个不同范围的最小值 for (int i = 0; i < length - 1; i++) { //最小值为当前索引的值 minValue = arr[i]; //并标记一下当前索引 minValueIndex = i; //将minValue与该索引后面的元素进行遍历比较 for (int j = i + 1; j < length; j++) { //发现更小的元素值 if (arr[j] < minValue) { //则将当前最小值minValue设置为该元素值 minValue = arr[j]; //并标记好改元素的索引值 minValueIndex = j; } } //遍历完毕，如果当前最小值标记的索引不是i //则将索引为 i 的元素与当前最小值的索引的元素值进行交换 if (minValueIndex != i) { arr[minValueIndex] = arr[i]; arr[i] = minValue; } } //打印结果 for (int t = 0; t < length; t++) { printf("%d ", arr[t]); } return 0; }
4.二维数组
4.1 二维数组的定义
在实际的工作中，仅仅使用一维数组是远远不够的，例如，一个学习小组有5个人，每个人有三门课的考试成绩，如果使用一维数组解决是很麻烦的。又比如说你有三个女朋友，每个女朋友有自己的三维，如果使用一维数组解决也很麻烦。这时，可以使用二维数组，二维数组的定义方式与一维数组类似，其语法格式如下：
类型说明符 数组名[常量表达式1][常量表达式2];
- 类型说明符：数组中每一个元素的数据类型
- 常量表达式1：被称为行下标
- 常量表达式2：被称为列下标。
📝 定义一个3行4列的二维数组：
int a[3][4];
在上述定义的二维数组中，共包含3*4个元素，即12个元素。接下来，通过一张图来描述二维数组a的元素分布情况：
可以看出，二维数组a是按行进行存放的，先存放a[0]行，再存放a[1]行、a[2]行，并且每行有四个元素，也是依次存放的。
