数组排序
- 排序算法是程序设计中最基本的、最重要的算法之一。
- 排序算法有很多，比较常用的有选择法、冒泡法、比较法和插入法等。
选择排序法
- 1.从n个数中选出最小数的下标,然后将最小数与第一个数交换位置；
- 2.除第1个数外，其余n-1个数再按步骤1的方法选出次小的数，与第2个数交换位置；
- 3.重复步骤n-1遍，最后构成递增序列。
- 排序过程图
- 例如：
#include <stdio.h>
#define N 10
void main()
{
int i,j,x,min,a[N];
printf("随机输入10整数：\n");
for (i = 0; i < N; i++) {
scanf_s("%d", &a[i]);
}
for (i = 0; i < N - 1; i++) {
min = i;
for (j = i+1; j < N; j++){
if (a[j] < a[min]) {
min = j;
x = a[i];
a[i] = a[min];
a[min] = x;
}
}
}
for (i = 0; i < 10; i++) {
printf("%d,", a[i]);
}
}
冒泡排序法
- 1.从第一个数开始，与相邻的数比较,若大于该数，则交换位置。
- 2.一轮排序后,最大数换到了最下面（即小数往上冒,大数往下沉）;
- 3.除最后一个数外,其他n-1个数按步骤:的方法使次大的数下沉;
- 4.重复步骤n-1遍，最后构成递增序列。
- 排序过程图
- 例子
#include <stdio.h>
#define N 10
main(){
int a[10];
int i,j,t;
printf("输入十个整数:\n");
for (i = 0; i<N; i++) {
scanf_s("%d", &a[i]);
}
for (j = 0;j < N-1; j++) {
for (i = 0; i < N -1-j; i++) {
if (a[i] > a[i + 1])
{
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
for (i = 0; i < N; i++) {
printf("%d，", a[i]);
}
}
数组中元素的插入和删除
插入排序子过程的算法(基于有序数组):
- 假设输入的数为 a ；
- 找到 a 应在数组中的位置；
- 从该位置开始将它及其后面的数依次往后移,将位置腾出；
- 将 a 放入该位置。
- 例如
#include <stdio.h>
main(){
int a[11] = {1,3,6,9,14,16,21,33,40,50};
int i,j,x=0;
for (i = 0; i<10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要插入的整数：");
scanf_s("%d", &x);
for (i = 0; i <= 10; i++) {
if (a[i] > x) {
for (j = 10; j > i; j--) {
a[j] = a[j - 1];
}
a[i] = x;
break;
}
}
for (i = 0; i <=10; i++) {
printf("%d ", a[i]);
}
}
删除排序过程的算法:
- 假设删除的数为num
- 找到num应在数组中的位置;
- 从该位置开始将它后面的数依次往前移即可
- 例如：
#include <stdio.h>
main(){
int a[11] = {1,3,6,9,14,16,21,33,40,50};
int i,j,num=0;
for (i = 0; i<10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要删除的整数：");
scanf_s("%d", &num);
for (i = 0; i < 10; i++) {
if (a[i] == num) {
break;
}
}
for (j = i; j <10; j++) {
a[j] = a[j + 1];
}
for (i = 0; i <9; i++) {
printf("%d ", a[i]);
}
}
查找
顺序查找思路:
- 将查找关键值与数组中的元素一一比较，
若相同，则查找成功，否则查找失败。 - 例如
#include <stdio.h>
main() {
int a[11] = { 1,3,6,9,14,16,21,33,40,50 };
int i, j, x = 0,y = 0;
for (i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要查找的整数：");
scanf_s("%d", &x);
for (i = 0; i <11; i++) {
if (a[i] == x) {
y = 1;
printf("找到数字%d,它的下标是%d", x, i);
break;
}
}
if (y == 0) printf("没有找到你输入的数字！");
}
二分法查找(折半查找)
- 可大大提高查找的速度,必须是有序数组。
- 查找过程图
- 例如
#include <stdio.h>
main() {
int a[] = { 1,3,6,9,14,16,21,33,40,50,100};
int i,find=0, mid,x=0, top = 0,bot = 10;
for (i = 0; i <=10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要查找的整数：");
scanf_s("%d", &x);
do {
mid = (top + bot) / 2;
if (x > a[mid]) top = mid + 1;
if (x == a[mid]) find = 1;
if (x < a[mid]) bot = mid - 1;
printf("%d,%d,%d\n", top, mid, bot);
} while (top <= bot && find == 0);
if (find == 1)
printf("找到数字%d\n", x);
else
printf("没有找到你输入的数字！\n");
}
二维数组的鞍点
- 一个元素在该行最大，在该列最小的话,称其为数组的鞍点
思路：
- 按行求出各行最大的元素位置
- 某行最大的元素与该元素所在列的所有元素比较，
判断是否为最小元素，是则是鞍点，否则不是鞍点。
- 例如：
#include<stdio.h>
#define N 3
#define M 3
main(){
int i, j, k, a[N][M], max, maxj, flag;
printf("请输入数组：\n");
for (i = 0; i < N; i++){
for (j = 0; j < M; j++){
scanf_s("%d", &a[i][j]);
}
}
printf("\n");
for (i = 0; i < N; i++){
max = a[i][0]; // 开始时假设a[i][0]最大
maxj = 0; //将列号0赋给maxj保存
for (j = 0; j < M; j++){ // 找出第i行中的最大数
if (a[i][j] > max){
max = a[i][j]; // 将本行最大的数放在max中
maxj = j; // 将最大数所在的列号存放在maxj中
}
}
flag = 1; // 先假设是鞍点，以flag为1代表
for (k = 0; k < N; k++){
if (max > a[k][maxj]){ // 将最大的数和其同列元素相比
flag = 0; // 如果max不是同列最小，表示不是鞍点
continue;
}
}
if (flag){
printf("a[%d][%d]=%d\n", i, maxj, max); //输出鞍点的值和所在行列号
break;
}
}
if (!flag){
printf("鞍点不存在!\n");
}
}
- 改良版(上面的算法无法判断一些特殊的数组矩阵)
#include<stdio.h>
#define N 3
#define M 3
main() {
int i, j, k,p, a[N][M], max, maxj, flag=0;
printf("请输入数组：\n");
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
scanf_s("%d", &a[i][j]);
}
}
printf("\n");
for (i = 0; i < N; i++) {
max = a[i][0]; // 开始时假设a[i][0]最大
maxj = 0; //将列号0赋给maxj保存
for (j = 0; j < M; j++) { // 找出第i行中的最大数
if (a[i][j] > max) {
max = a[i][j]; // 将本行最大的数放在max中
}
}
for (j = 0; j < M; j++) { // 检测最大值是否是鞍点
if (a[i][j] == max) {
k = j;
p = 0;
while (p < N && max <= a[p][k]) {
p++;
}
if (p == N) {
printf("a[%d][%d]=%d\n", i, k, max);
flag = 1;
}
}
}
if (flag == 0) {
printf("鞍点不存在!\n");
}
}
}
数组注意问题
用scanf函数向
字符型数组输入数据char a[20];scanf("%s",&a);错误scanf(%s",a);正确
用scanf函数向
数值型数组输入数据int a[20];scanf("%d",a);错误scanf(%d",&a);正确
引用数组元素要用
[]。int i, a(10);
for (i=0;i<10;i++) scanf(%d",&a(i));错误int i, a(10);
for (i=0;i<10;i++) scanf(%d",&a[i]));正确
数组元素可使用的最大下标
int i,a[10]={1};
for(i=1;i<=10;i++) printf(%d",a[i]);错误int i,a[10]={1};
for(i=1;i<=9;i++) printf(%d",a[i]);或者for(i=1;i<10;i++) printf(%d",a[i]);正确
二维数据或多维数组的定义和引用
int a[4,5]; a[1+2,2+2]=5;错误int[10];正确
误以为数组名代表数组全部元素
int a[4]={1,3,5,7},b[4]; b=a;
char str[4]; str="computer";错误
混淆字符字符串的表示形式
char sex; sex="M";错误char sex; sex= ' M ';正确
评论