排序和查找

1. 排序算法介绍

• 排序也称排序算法，排序是将一组数据，依指定的顺序进行排列的过程
• 排序的分类
  • 内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序
  • 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储器进行排序

2. 冒泡排序

2.1 基本介绍

• 冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素从前移向后部，就像水底的气泡一样逐渐向上冒。
• 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较

2.2 案例

• 将五个无序 的数：{3，9，-1，10，-2}使用冒泡排序法将其排成一个从小到大的有序数列

2.3 分析冒泡的过程+代码

//冒泡排序的过程（从小到大）
原始数组{3，9，-1，10，-2}

第一轮
    1.3，9，-1，10，2
    2.3，-1，9，10，2
    3.3，-1，9，10，2
    4.3，-1，9，-2，10
    //第一大的数就移动到最后
第二轮
    1.-1，3，9，-2，10
    2.-1，3，9，-2，10
    3.-1，3，-2，9，10
第三轮
    1.-1，3，-2，9，10
    2.-1,-2,3,9,10
 第四轮
    -2，-1，3，9，10

#include<stdio.h>
//冒泡排序函数
void bubbleSort(int arr[],int arrLen){
    //因为每轮排序几乎一样，因此，可以使用for循环处理
    int i,j;
    int t;//临时变量
    for(i=0;i<arrLen-1;i++){
        for(j=0;j<arrLen-1-i;j++){
        //如果前面的数大于后面的数，就交换
        if(arr[j]>arr[j+1]){
            t=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=t;
        }
        }
    }
}
void main(){
    int arr[]={3,9,-1,10,-2,11};
    int arrLen=sizeof(arr)/sizeof(int);
    int j;
    bubbleSort(arr,arrLen);//数组默认是地址传递
    printf("排序后");
    for(j=0;j<arrLen;j++){
        printf("%d",arr[j]);
    }
    getchar();
}

3. 查找

3.1 介绍

在C中，常用的查找有两种

• 顺序查找
• 二分查找

3.2 案例演示

• 有一个数列{23，1，34，89，101}
• 猜数游戏：从键盘任意输入一个数，判断数列中是否包含该数[顺序查找]
• 要求：如果找到了，就提示找到，并给出下标值，找不到提示没有

#include<stdio.h>
int seqSearch(int arr[],int arrLen,int val){
    int i;
    for(i=0;i<arrLen;i++){
        if(arr[i]==val){
            return i;
        }
    }
    //如果在for循环中，没有执行到return，说明没有找到
    return -1；
}

void main(){
    int arr[]={23,1,34,89,101};
    int arrLen=sizeof(arr)/sizeof(int);
    int index=seqSearch(arr,arrLen,-101);
    if(index != -1){
        printf("找到 下标为%d",index);
    }else{
        printf("没有找到");
    }
    getchar();
}

• 请对一个有序数组进行二分查找{1，8，10，89，100，123}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示“没有这个数”
• 二分查找的前提是该数组是一个有序数组

#include<stdio.h>
//二分查找
int binarySearch(int arr[],int leftIndex,int rightIndex,int findVAL){
    //先找到数组中间这个数midVal
    int midIndex=(leftIndex+rightIndex)/2;
    int midVal=arr[midIndex];
    //如果leftIndex>rightIndex,说明这个数组都比较过，但是没有找到
    if(leftIndex>rightIndex){
        return -1;
    }
    //如果midVal>findVal说明，应该在midVal的左边查找
    if(midVal>findVal){
        binarySearch(arr,leftIndex,midIndex-1,findVal);
    }else if(midVal<findVal){
        //如果midVal<findVal说明，应该在midVal的右边查找
        binarySearch(arr,midIndex+1，rightIndex,findVal);
    }else{
        return midIndex;
    }
}

void main(){
    //分析
    //比如要查找的数是findVal
    //1.先找到数组中间这个数midVal,和findVal比较
    //2.如果midVal>findVal说明，应该在midVal的左边查找
    //3.如果midVal<findVal说明，应该在midVal的右边查找
    //4.如果midVal==findVal,说明找到
    int arr[]={1,8,10,89,1000,1234};
    int arrLen=sizeof(arr)/sizeof(int);
    int index=binarySearch(arr,0,arrLen-1,-1000);
    if(index!=-1){
        printf("找到index=%d",index);
    }else{
        printf("没有找到");
    }
    getchar();
}

4.多维数组和二维数组

多维数组主要介绍二维数组

5. 二维数组的应用场景

比如开发一个五子棋游戏，棋盘就是需要二维数组来表示

6.二维数组的使用

6.1 快速入门

请用二维数组输出如下图形

0 0 0 0 0 0

0 0 1 0 0 0

0 2 0 3 0 0

0 0 0 0 0 0

6.2 使用方式1：先定义再初始化

语法：类型 数组名[大小 ] [大小]

比如：int a[2] [3]

6.3 使用演示

二维数组在内存的存在形式，各个元素的地址是连续分布的，即在前一个元素基础上加+4

#include<stdio.h>
void main(){
    //a[4][6];表示一个4行6列的二维数组
    int a[4][6];//没有初始化，则是分配的内存垃圾值
    
    int i,j;
    //全部初始化为0
    for(i=0;i<4;i++){
        for(j=0;j<6;j++){
            a[i][j]=0;
        }
    }
    a[1][2]=1;
    a[2][1]=2;
    a[2][3]=3;
    //输出二维数组
    for(i=0;i<4;i++){
        for(j=0;j<6;j++){
            printf("%d",a[i][j]);
        }
        printf("\n");
    }
    //看看二维数组的内存布局
    printf("二维数组a的首地址=%p",a);
    printf("二维数组a[0]的地址=%p",a[0]);
    printf("二维数组a[0][0]的地址=%p",&a[0][0]);
    printf("二维数组a[0][1]的地址=%p",&a[0][1]);
    //将二维数组的各个元素的地址输出
    printf("\n");
    for(i=0;i<4;i++){
        printf("a[%d]的地址=%p",i,a[i]);
        for(j=0;j<6;j++){
            printf("a[%d][%d]的地址=%p",i,j,&a[i][j]);
        }
        printf("\n");
    }
    getchar();
}

6.4 使用方式2：直接初始化

• 定义 类型 数组名【大小】【大小】={{值1，值2....},{值1，值2....}}；
• 或者 类型 数组名 【大小】【大小】 ={值1，值2，值3，值4，值5，值6...}；
  • 会自动匹配到各行各列

7.二维数组应用案例

7.1 案例1

• 请使用灵活的方式遍历如下数组
• int map[3] [3]={{0,0,1},{1,1,1}{1,1,3}};

7.2 案例2

int arr[3] [2]={{4,6},{1,4},{-2,8}};

遍历该二维数组，并得到和

#include <stdio.h>
void main(){
    int map[3][3]={{0,0,1},{1,1,1},{1,1,3}};
    //遍历
    //先得到行
    //1.sizeof(map) 得到这个map数组的大小9*4=36
    //2.sizeof(map[0])得到map中，第一行有多大3*4=12
    int rows=sizeof(map)/sizeof(map[0]);
    //printf("rows=%d",rows);
    //得到列
    int cols=sizeof(map[0])/sizeof(int);
    int i,j,sum=0;
    for(i=0;i<rows;i++){
        for(j=0;j<cols;j++){
            printf("%d",map[i][j]);
            sum+=map[i][j];
        }
        printf("\n");
    }
    printf("sum=%d",sum);
    getchar();
}

7.4 定义二维数组，用于保存三个班，每个班五名同学成绩，并求出每个班级平均分，以及所有班级平均分

#include<stdio.h>
void main(){
    //分析
    //1.创建一个scores[3][5]
    //2.遍历，给复制
    //3.再次遍历，统计总分和平均分
    //4.输出
    double score[3][5];
    int rows=sizeof(score)/sizeof(score[0]),cols=sizeof(score[0])/sizeof(double),i,j;
    //classTotalScore 各个班级总成绩 totalscore 所有学生成绩
    double totalScore=0.0,classTotalScore=0.0;
    for(i=0;i<rows;i++){
        for(j=0;j<rows;j++){
            score[i][j]=0.0;
        }
    }
    //遍历，给每个学生输入成绩
    for(i=0;i<rows;i++){
        for(j=0;j<cols;j++){
            printf("请输入第%d个班的第%d个学生的成绩",i+1,j+1);
            scanf("%lf",&score[i][j]);
        }
    }
    getchar();
    //显示下成绩情况
    for(i=0;i<rows;i++){
        for(j=0;j<cols;j++){
            printf("%.2f",score[i][j]);
        }
        printf("\n");
    }
    //统计各个班的总成绩，和所有学生的成绩
    for(i=0;i<rows;i++){
        classTotalScore=0.0;//每次清零
        for(j=0;j<cols;j++){
            classTotalScore+=score[i][j];//累计每个班的总成绩
        }
        printf("第%d个班的平均成绩是%.2f",i+1.classTotalScore/cols);
        totalScore+=classTotalScore;//将该班的总分，累加到totalScore
    }
    printf("所有学生的总成绩是%.2f 平均成绩是%.2f",totalScore,totalScore/(rows*cols));
    getchar();
    getchar();
}

8.二维数字使用细节和注意事项

• 可以只对部分元素赋值，为赋值的元素自动取零

int main(){
    int a[4][5]={{1},{2},{3},{1}};
    int i,j;
    for(i=0;i<4;i++){
        for(j=0;j<5;j++){
            printf("%d",a[i][j]);
        }
        printf("\n");
    }
    getchar();
}

• 如果对全部元素赋值，那么第一维的长度可以不给出

int a[3][3]={1,2,3,4,5,6,7,8,9};
//可以写为
int a[][3]={1,2,3,4,5,6,7,8,9};

• 二维数组可以看作是由一维数组嵌套而成的；如果一个数组的每个元素又是一个数组，那么它就是二维数组
  • 二维数组a[3] [4]可看成三个一维数组，他们数组名分别为a[0],a[1],a[2]
  • 这三个一维数组都有4个元素，如一维数组a[0]的元素为a[0] [0],a[0] [1],a[0] [2],a[0] [3]

排序和查找

原文：https://www.cnblogs.com/mx-info/p/14383284.html