07-数组的高级操作

教程 阿布都的都 ⋅ 于 2023-01-06 10:32:26 ⋅ 737 阅读

数组的高级操作

1. 查找

1.1 普通查找

需求:定义方法实现,查找某元素在数组中第一次出现的位置(索引),如果没有,返回-1。

分析:

​ 参数列表:需要查找的数组 和 元素

​ 返回值类型:找到的位置 int

​ 遍历数组,依次查找即可

代码:

public static int search(int[] arr, int value) {
    if (arr == null) {
        throw new RuntimeException("数组为空");
    }
    // 定义变量表示查找的索引
    int index = -1;
    // 遍历查询
    for (int i = 0; i < arr.length; i++) {
        if (value == arr[i]) {
            index = i;
            // 如果找到,结束循环,不再查找后续元素
            break;
        }
    }
    return index;
}

1.2 二分查找

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

二分查找前提:

1.必须采用顺序存储结构。

2.必须按关键字大小有序排列。

查找过程:

1、首先,假设表中元素是按升序排列,将表中间位置记录关键字与查找关键字比较,如果两者相等,则查找成功;

2、否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。

3、重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

代码示例:

public static int binarySearch(int[] arr, int value) {
    // 查找的范围
    int start = 0;
    int end = arr.length - 1;
    // 循环查找
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] < value) {
            // 如果值大,查询的起始索引改变
            start = mid + 1;
        } else if (value < arr[mid]) {
            // 如果值小,查询的结束索引改变
            end = mid - 1;
        } else {
            // 找到了 返回索引
            return mid;
        }
    }
    // 循环结束没有return,没找到,返回 负的插入点-1
    return -(start + 1);
}

2. 排序

2.1 冒泡排序

冒泡排序(Bubble Sort),是一种比较简单的排序算法。原理如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

对数组{5, 1, 4, 2, 8}进行冒泡排序的过程如下图所示:

第一轮排序:

file

第二轮排序:

file

第三轮排序:

file

第四轮排序:

file

代码:

public static void bubbleSort(int[] arr) {
    // 外循环控制需要多少轮的比较
    for (int i = 0; i < arr.length - 1; i++) {
        // 内循环控制每轮比较中的交换过程
        for (int j = 0; j < arr.length - 1 - i; j++) {
            // 如果前面的元素大于后面的
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2.2 选择排序

选择排序(Selection sort)的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。

排序过程如下图所示:

image-20221013194737948

代码:

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // 记录最小值出现的位置
        int mark = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[mark]) {
                mark = j;
            }
        }
        if (mark != i) {
            // 交换
            int temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
        }
    }
}
版权声明:原创作品,允许转载,转载时务必以超链接的形式表明出处和作者信息。否则将追究法律责任。来自海汼部落-阿布都的都,http://hainiubl.com/topics/75987
回复数量: 0
    暂无评论~~
    • 请注意单词拼写,以及中英文排版,参考此页
    • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
    • 支持表情,可用Emoji的自动补全, 在输入的时候只需要 ":" 就可以自动提示了 :metal: :point_right: 表情列表 :star: :sparkles:
    • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif,教程
    • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
    Ctrl+Enter