[数据结构与算法]java基础之数组

1.数组的概述

1.1概念

数组(Array)，是多个相同类型数据按一定顺序排列的集合，并使用一个名字命名，并通过编号的方式对这些数据进行统一管理。

1.2 常见概念

• 数组名
• 索引（下标）
• 元素
• 数组长度

注：
数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括基本数据类型和引用数据类型。
创建数组对象会在内存中开辟一整块连续的空间，而数组名中引用的是这块连续空间的首地址。
数组的长度一旦确定，就不能修改。
我们可以直接通过下标(或索引)的方式调用指定位置的元素，速度很快。 ? 数组的分类：
按照维度：

• 一维数组
• 二维数组
• 三维数组

按照元素的数据类型分：

• 基本数据类型元素的数组
• 引用数据类型元素的数组(即对象数组)

1.3数据结构

1. 数据与数据之间的逻辑关系： 集合、 一对一、多对一、 多对多

2. 数据的存储结构：线性表（顺序表、链表、栈、队列），树形结构（二叉树），图形结构

2.二维数组常见的算法

2.1二分查找

介绍
当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。

它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。

如果一个序列是无序的或者是链表，那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件，是由二分查找算法的原理决定的。
原理
二分查找算法的原理如下：

1. 如果待查序列为空，那么就返回-1，并退出算法；这表示查找不到目标元素。

2. 如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。

3. 如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。

4. 如果不相等，就再比较这两个元素的大小。

5. 如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

6. 如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。

7. 在新的待查序列上重新开始第1步的工作。

二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。

本文就来探究几个最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。

而且，我们就是要深入细节，比如while循环中的不等号是否应该带等号，mid 是否应该加一等等。分析这些细节的差异以及出现这些差异的原因，保证你能灵活准确地写出正确的二分查找算法。

代码展示

package com.blb.com;

import java.util.Scanner;
public class demo3 {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int [] a=new int[10];
        for(int j=0;j<10;j++)
        {
            a[j]=(j+1)*10;
        }
        int l=0,r=a.length-1;
        System.out.println("请输入您要查找的值");
        int x=scanner.nextInt();
        Boolean ju=true;
        while (l<=r)
        {
            int index=(l+r)/2;
            if(x==a[index])
            {
                System.out.println("找到了"+index);
                ju=false;
                break;
            }
            if(x<a[index])
            {
                r=index-1;
            }
            if(x>a[index])
            {
                l=index+1;
            }
        }
        if(ju)
            System.out.println("不找意思值未找到");
    }
}

2.2排序算法

2.2.1 概述

假设含有n个记录的序列为{R1，R2，…,Rn},其相应的关键字序列为{K1，K2，…,Kn}。将这些记录重新排序为{Ri1,Ri2,…,Rin},使得相应的关键字值满足条Ki1<=Ki2<=…<=Kin,这样的一种操作称为排序。
通常来说，排序的目的是快速查找。

2.2.2衡量排序算法的优劣

1. 时间复杂度：分析关键字的比较次数和记录的移动次数
2. 空间复杂度：分析排序算法中需要多少辅助内存
3. 稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

2.2.3排序算法的分类

1. 内部排序

• 整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。

2. 外部排序

• 参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

2.2.4冒泡排序

介绍
冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
原理

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

public class demo4 {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] < a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
}

3.数组中常用的工具类

java.util.Arrays类即为操作数组的工具类，包含了用来操作数组（比如排序和搜索）的各种方法