数组的常见算法（查找与排序）

8.1 查找算法

七种算法：

基本查找
二分查找
插值查找
分块查找
哈希查找
树表查找
斐波那契查找

8.1.1 基本查找

又称顺序查找

思路：

从数组的0索引开始，依次往后查找。
若找到，返回相应索引，否则返回-1

#include<stdio.h>
int order(int arr[], int len, int num);

int main(){
    //基本查找

    //定义数组
    int arr[] = {11,22,33,44,55,66,77,88,99};

    //定义要查找的元素
    int num = 88;

    //使用基本查找算法
    int index = order(arr, sizeof(arr)/sizeof(int), num);

    //打印结果
    printf("index = %d\n", index);
  
    return 0;
  
}


//作用：查找数组中的数据
//返回值，数据所在的索引
int order(int arr[], int len, int num){
    for(int i = 0; i < len; i++){
        if(arr[i] == num){
            return i;
        }
    }
    return -1;
}

8.1.2 二分查找

又称折半查找

前提条件：数组中的数据必须是有序的（从小到大，从大到小）
核心思想：每次排除一半的查找范围
具体步骤：

分别用两个变量min, max记录数组的最大索引和最小索引
用(min+max)/2，得出来的数用变量mid记录
将mid索引的值与要查找的值A进行比较
若mid值大于A，将(mid-1)赋给max；若mid值小于A，将(mid+1)**赋给min
重复2~4步骤，直到mid索引的值等于A，或min>max

#include<stdio.h>

int main(){
    //二分查找
  
    //定义数组
    int arr[] = {12,23,34,45,56,68,90,123,345};

    //定义查找的数字
    int num = 23;

    //定义数组的长度
    int len = sizeof(arr)/sizeof(arr[0]);

    //调用二分查找函数
    int index = binarySearch(arr, len, num);

    //输出结果
    if(index == -1){
        printf("Not find\n");
    }
    else{
        printf("index = %d\n", index);
    }

    return 0;
}

//二分查找
//返回值：数据在数组中的索引
//若未找到：返回-1
int binarySearch(int arr[], int len, int num){
  
    //1.确定查找的范围
    int min = 0;
    int max = len - 1;

    //2.循环查找
    while(min <= max){

        //2.1计算中间位置
        int mid = (min + max) / 2;

        //2.2判断中间位置的元素是否等于num
        if(arr[mid] == num){
            return mid;
        }
        else if(arr[mid] < num){
            //2.3如果中间位置的元素小于num，说明num在mid的右边
            min = mid + 1;
        }
        else{
            //2.4如果中间位置的元素大于num，说明num在mid的左边
            max = mid - 1;
        }
    }
    //3.如果min大于max，说明未找到，返回-1
    return -1;
}

二分查找的优势：提高效率

8.1.3插值查找

对二分查找的改进，使mid值在一开始就更接近num(要查找的值)

公式：

mid = min + {num-arr[min] \over arr[max]-arr[min]} *(max-min)

代码：

mid = min + ((key -arr[min]) / (arr[max] - arr[min])) * (max - min);

其他代码与二分查找相同

要求：数组顺序排列且尽可能均匀分布，否则效率可能比二分查找更慢

8.1.4 分块查找

将数组分为几个块

分块的原则

每一个块的数字范围不能有交集
块的数量一般等于数字的个数开根号（效率较高）

查找思路：先确定要查找的元素在哪一块，然后在块内挨个查找

8.1.5 哈希查找

利用链表

8.2 排序算法

把无序的数据排成有序的数据（以从小到大为例）

8.2.1 冒泡排序

核心思想：找到最大值

相邻的数据两两比较，小的放前面，大的放后面
第一轮循环结束，最大值找到，在数组的最右边
继续循环，每轮少比较一次，直到所有数确定

#include <stdio.h>
//冒泡排序
int main(){
    //1.定义数组存储数据和长度变量
    int arr[] = {23,43,1,67,23,45,23,67,34,56,78,23,45,67,89,12,34,56,78,90};
    int len = sizeof(arr) / sizeof(int);

    //2.利用冒泡排序对数组进行升序排列
    for(int i = 0; i < len - 1; i++){		//每下一个循环比较少一个
        for(int j = 0; j < len - 1 - i; j++){		//一轮循环
            if(arr[j] > arr[j + 1]){
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for(int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }  

    return 0;
}

8.2.2 选择排序

核心思想：找到最小值

从0索引开始，将0索引上的数与后面的数依次比较
若后面的数小于前面的数，则交换数字
0索引与后面的数比较完后，以1索引继续1~2步

#include <stdio.h>
//冒泡排序
int main(){
    //1.定义数组存储数据和长度变量
    int arr[] = {23,43,1,67,23,45,23,67,34,56,78,23,45,67,89,12,34,56,78,90};
    int len = sizeof(arr) / sizeof(int);

    //2.利用选择排序对数组进行升序排列
    for(int i = 0; i < len - 1; i++){
        for(int j = i + 1; j < len; j++){
            if(arr[i] > arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    for(int i = 0; i < len; i++){
        printf("%d,",arr[i]);
    }

    return 0;
}