目录
问题:
回顾:
给出两种做法:
解法一:调用qsort 函数进行排序
代码:
运行结果:
解法二:冒泡排序
代码:
运行结果:
回顾里的4种方法的模板参考:
1.冒泡排序法:
2. 选择排序法:
3.插入排序法:
4.快速排序法:
问题:
定义一个二维数组并输入数据,将二维数组元素的值按升序排列,并输出排序后的二维数组。
回顾:
可以使用多种方法来实现将二维数组元素按升序排列的算法。以下是几种常见的做法:
-
冒泡排序法:对二维数组进行冒泡排序,每次比较相邻元素并交换位置,直到整个数组有序。
-
选择排序法:在二维数组中选择最小元素,与当前位置的元素交换,并依次向后遍历和选择最小元素,直到整个数组有序。
-
插入排序法:将未排序的元素逐个插入到已排序的部分中,类似于打扑克牌时的排序过程。
-
快速排序法:选择基准元素,将数组划分为左右两个子数组,使得左边的元素都小于等于基准元素,右边的元素都大于等于基准元素,然后递归地对子数组进行快速排序。
给出两种做法:
解法一:调用qsort 函数
进行排序
代码:
#include <stdio.h>// 定义比较函数,用于qsort排序
int compare(const void *a, const void *b) {return (*(int*)a - *(int*)b);
}int main() {int m, n;printf("请输入二维数组的行数和列数:");scanf("%d %d", &m, &n);int arr[m][n];printf("请输入二维数组的元素值:\n");for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &arr[i][j]);}}printf("输入的二维数组为:\n");for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {printf("%d ", arr[i][j]);}printf("\n");}// 将二维数组展开成一维数组int temp[m * n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {temp[i * n + j] = arr[i][j];}}// 使用标准库函数qsort对一维数组进行排序qsort(temp, m * n, sizeof(int), compare);// 将排序后的一维数组重新填充回二维数组for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {arr[i][j] = temp[i * n + j];}}printf("排序后的二维数组为:\n");for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {printf("%d ", arr[i][j]);}printf("\n");}return 0;
}
// 定义比较函数,用于qsort排序
int compare(const void *a, const void *b) {return (*(int*)a - *(int*)b);
}
compare函数是用作
qsort
函数的比较函数。在C语言中,qsort
函数是一个标准库函数,用于对数组进行排序。它接受一个数组、数组中元素的数量、每个元素的大小以及一个比较函数作为参数,然后使用指定的比较函数对数组进行排序。比较函数的作用是定义元素之间的顺序关系。在这个示例中,比较函数
compare
用于升序排序。它的参数类型是
const void*
,这是因为qsort
函数需要一个通用的比较函数,能够处理任意类型的元素。函数内部通过将参数转换成int*
类型,并取值进行比较,返回一个整数来表示两个元素的相对顺序。比较函数的返回值有以下规定:
- 如果返回值小于0,表示第一个元素应该排在前面;
- 如果返回值等于0,表示两个元素相等,顺序不变;
- 如果返回值大于0,表示第二个元素应该排在前面。
通过定义不同的比较函数,我们可以实现不同的排序方式,例如降序排序或者按照其他自定义规则进行排序。
qsort函数是C语言中的一个库函数,主要用于对数组进行排序。它包含四个参数:数组名,元素个数(从前往后计算),数组元素所占字节(如int,double,char等所占字节)以及排序原则(递增,递减,奇偶交叉等)。此外,为了实现特定的排序规则,我们需要提供一个比较函数。
例如,如果我们想按照升序排列一个整数数组,我们可以定义一个比较函数如下:
int cmp(const void *a,const void *b) {
return * ( int *)a-* ( int *)b;
}
然后调用
qsort (num, n, sizeof ( int ), cmp);
进行排序。需要注意的是,qsort函数是一个不稳定的排序算法,也就是说,相等元素的相对位置可能会在排序后改变。同时,qsort函数可以对任意类型的数组进行排序,只需自定义相应的比较函数即可。
运行结果:
解法二:冒泡排序
代码:
#include <stdio.h>int main() {int m, n;printf("请输入二维数组的行数和列数:");scanf("%d %d", &m, &n);int arr[m][n];printf("请输入二维数组的元素值:\n");for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &arr[i][j]);}}// 将二维数组展开成一维数组int temp[m * n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {temp[i * n + j] = arr[i][j];}}// 冒泡排序对一维数组进行升序排序for (int i = 0; i < m * n - 1; i++) {for (int j = 0; j < m * n - 1 - i; j++) {if (temp[j] > temp[j + 1]) {int tempValue = temp[j];temp[j] = temp[j + 1];temp[j + 1] = tempValue;}}}// 将排序后的一维数组重新填充回二维数组for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {arr[i][j] = temp[i * n + j];}}// 输出排序后的二维数组printf("排序后的二维数组为:\n");for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {printf("%d ", arr[i][j]);}printf("\n");}return 0;
}
首先在主函数中,通过用户输入获取二维数组的行数和列数,然后根据用户输入的行数和列数定义一个二维数组arr[m][n]。
接着,用户被提示输入二维数组的元素值,通过两重循环遍历用户输入的元素,并将其存储在arr数组中。
接下来,利用一个临时的一维数组temp[m*n]来存储二维数组arr中的所有元素。通过两重循环将二维数组展开成一维数组,展开的方式是按照行优先的顺序,即先将第一行的元素存入一维数组,再存储第二行的元素,依次类推。
之后,使用冒泡排序法对一维数组temp进行升序排序。冒泡排序法是通过相邻元素的比较和交换来实现排序的。
排序完成后,再次利用两重循环将排序后的一维数组temp重新填充回二维数组arr中,还是按照行优先的顺序进行填充。
最后,输出排序后的二维数组arr,同样通过两重循环逐行逐列地输出数组的元素。
运行结果:
回顾里的4种方法的模板参考:
1.冒泡排序法:
#include <stdio.h>void bubbleSort(int arr[][N], int m, int n) {for (int k = 0; k < m * n - 1; k++) {for (int i = 0; i < m; i++) {for (int j = 0; j < n - 1; j++) {if (arr[i][j] > arr[i][j + 1]) {// 交换相邻元素int temp = arr[i][j];arr[i][j] = arr[i][j + 1];arr[i][j + 1] = temp;}}}}
}int main() {// 输入二维数组和行列数省略bubbleSort(arr, m, n);// 输出排序后的二维数组省略return 0;
}
2. 选择排序法:
#include <stdio.h>void selectionSort(int arr[][N], int m, int n) {for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int minIndex = j;for (int k = j + 1; k < n; k++) {if (arr[i][k] < arr[i][minIndex]) {minIndex = k;}}if (minIndex != j) {// 交换元素int temp = arr[i][j];arr[i][j] = arr[i][minIndex];arr[i][minIndex] = temp;}}}
}int main() {// 输入二维数组和行列数省略selectionSort(arr, m, n);// 输出排序后的二维数组省略return 0;
}
3.插入排序法:
#include <stdio.h>void insertionSort(int arr[][N], int m, int n) {for (int i = 0; i < m; i++) {for (int j = 1; j < n; j++) {int key = arr[i][j];int k = j - 1;while (k >= 0 && arr[i][k] > key) {arr[i][k + 1] = arr[i][k];k--;}arr[i][k + 1] = key;}}
}int main() {// 输入二维数组和行列数省略insertionSort(arr, m, n);// 输出排序后的二维数组省略return 0;
}
4.快速排序法:
#include <stdio.h>void quickSort(int arr[][N], int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}
}int partition(int arr[][N], int low, int high) {int pivot = arr[high][N-1];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j][N-1] <= pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return i + 1;
}void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}int main() {// 输入二维数组和行列数省略quickSort(arr, 0, m - 1);// 输出排序后的二维数组省略return 0;
}