数组
概念：用来连续存储多个同类型元素。
- 相同类型
- 在内存中连续存储
- 多个数据
对数组的理解：定义个数组相当于一次定义多个变量
数组元素
构成一个数组的每一个数据称为数组元素。
数组下标
下标是数组元素在数组中的位置。在一个数组中，数组下标是用整数表示的，从0开始，依次累加1。下表也叫索引 （ index），下标的界限 0 到 数组长度-1，下表如果位负数，或者下标超过了数组大小-1，此时会发生数组下标越界。（ArrayIndexOutOfbounds）
数组长度
数组中元素的个数，数组的长度也叫数组的大小。
获取数组长度的方法：数组名.length
注意：数据大小是在为数组元素分配内存时确定的大小，大小不可改变。
数组适用于哪些使用场景
- 班级学生成绩等等需要多个同类型的数据时。
使用数组
使用数组分四步：
- 定义数组
- 为数组元素分配内存
- 为数组元素初始化
- 使用数组
在java中是[]表示数组
案例：班级5个学生，求成绩的平均分
ublic static void main(String[] args) {
//第一步：定义数组，数组的名称是score
int []score;//或者 int score[],java中更为推荐第一种
//第二步：为数组元素分配内存
score = new int[5];//内存大小一旦确定不能更改
//第三步：为数组元素初始化
Random random = new Random();
for (int i = 0; i <score.length ; i++) {
score[i] = random.nextInt(40)+60;
}
//第四步：使用数组元素
int sum =0 ;
for (int i = 0; i < score.length; i++) {
sum += score[i];
}
System.out.println(sum / score.length);
}
数组的数据结构（线性表）
数组在内存空间中使用线性表存储，线性表全名为线性存储结构。使用线性表存储数据的方式可以这样理解，数据为一段连续的有一定次序的同类型的数据串表。如图：
数组存储
数组为引用类型数据，其值为地址编号（16进制编号），地址编号指向其他值的存储位置。数组的值是存储多个连续同类型的值的首地址来表示该数组，以数组名[下标]使用元素。
数组的基本存储如图：
数组常用算法
1. 最大值，最小值，平均值，求和
示例:创建一个成绩的数据，统计最大值，最小值，平均值，求和
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int []score = new int[5];
//成绩初始化
for (int i = 0; i < score.length; i++) {
System.out.println("请输入第"+(i+1)+"个学生的成绩");
score[i]= s.nextInt();
}
//求最高分，求最低分
int max = score[0];
int min = score[0];
for (int i = 1; i < score.length; i++) {
if(max<score[i]){
max = score[i];
}
if(min>score[i]){
min = score[i];
}
}
System.out.println("最高分为"+max);
System.out.println("最低分为"+min);
//总分
int sum = 0;
for (int i = 0; i < score.length; i++) {
sum += score[i];
}
System.out.println("班级总分："+sum);
System.out.println("班级平均分"+sum/score.length);
}
2.常见排序与了解
冒泡排序
基本思想是：对比相邻的元素值，如果满足条件就交换元素值，把较小的元素值移动到数组前面，把大的元素值移动到数组后面（也就是交换两个元素的位置），这样数组元素就像气泡一样从底部上升到顶部。
代码案例：
package day0515;
public class demo_sort {
public static void main(String[] args) {
//冒泡排序算法
int[] numbers=new int[]{1,5,8,2,3,9,4};
//需进行length-1次冒泡
for(int i=0;i<numbers.length-1;i++)
{
for(int j=0;j<numbers.length-1-i;j++)
{
if(numbers[j]>numbers[j+1])
{
int temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;
}
}
}
System.out.println("从小到大排序后的结果是:");
for(int i=0;i<numbers.length;i++)
System.out.print(numbers[i]+" ");
}
}
选择排序
基本思想：遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。
代码案例:
public static void algorithm4(){
int[] array={3,5,1,2,4};
int length = array.length;
for (int i = 0; i < length; i++) {
//初始化变量，记录最小数字的下标。初始默认假设第一个数字就是最小数字
int minIndex = i;
//内循环，通过比较获取数组中最小的数字的下标。
for (int j = i+1; j < length ; j++) {
//如果找到更小的数字，
if (array[minIndex]>=array[j]) {
//将minIndex变量的值修改为新的最小数字的下标。
minIndex = j;
}
}
//所有数字一个个比较结束之后，就能确认那个数字最小了。
//将最小的数字替换到第一个位置，将第一个位置的数字放到最小数字原来的位置，就是一次交换。
int temp=array[i];
array[i]=array[minIndex];
array[minIndex]=temp;
}
//将排序之后的数组打印出来。
for (int i = 0; i < length; i++) {
System.out.print(array[i]+"，");
}
}
插入排序
基本思想是：把待排序的记录按其值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
代码案例:
public static void insertionSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
// 要插入的数
int insertNum;
for (int i = 1; i < length; i++) {
insertNum = array[i];
// 已经排序好的元素个数
int j = i - 1;
while (j >= 0 && array[j] > insertNum) {
// 从后到前循环，将大于insertNum的数向后移动一格
array[j + 1] = array[j];
j--;
}
// 将需要插入的数放在要插入的位置
array[j + 1] = insertNum;
}
}
快速排序
基本思想：选择序列中的某个数作为基准值 通过一趟排序将要排序的数据分割成独立的两部分，其中左边的数据都比基准值小,右边的数据都比基准值大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码案例:
public static void quickSort(int[] arr,int first,int last){
if (first >= last) {
return;
}
int low = first;
int high = last;
int mid_value = arr[first];
while (low < high){
while (low < high && arr[high] >= mid_value){
high-=1;
}
arr[low] = arr[high];
while (low < high && arr[low] < mid_value){
low +=1;
}
arr[high] = arr[low];
}
arr[high] = mid_value;
//递归对左右两边的数据排序
quickSort(arr,first,low-1);
quickSort(arr,low+1,last);
}
其他排序
(1)冒泡排序；
(2)选择排序；
(3)插入排序；
(4)希尔排序；
(5)归并排序；
(6)快速排序；
(7)基数排序；
(8)堆排序；
(9)计数排序；
(10)桶排序
(11)二叉树排序
二分查找
算法思想是将数列排序，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小 于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 二分（折半）查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
代码案例:
public static int search(int []arr,int num){
int s=0;
int h=arr.length-1;
while (s<=h){
int m=(s+h)/2;
if (num==arr[m]){
return m;
}else if(num>arr[m]){
s=m+1;
}else {
h=m-1;
}
}
return -1;
}
数组的工具类java.util.Arrays类
Arrays 类是一个工具类，其中包含了数组操作的很多方法，通过Arrays.xxx(xxx) 的形式调用方法。
比较两个数组是否相等equals()
public static void main(String[] args) {
int []arr1 = {10,50,40,30};
int []arr2 = {10,50,40,30};
int []arr3 = {60,50,85};
System.out.println(Arrays.equals(arr1, arr2));//判断arr1与arr2的长度及元素是否相等
System.out.println(Arrays.equals(arr1, arr3));//判断arr1与arr3的长度及元素是否相等
}
对数组元素进行升序排序sort()
数组全部排序
public static void main(String[] args){
int []arr1 = {10,50,40,30};
Arrays.sort(arr1);
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
}
数组指定下标范围排序
public static void main(String[] args){
int []arr1 = {10,50,40,30,89,67,4,678};
Arrays.sort(arr1,3,arr1.length-1);
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
}
将数组转换成字符串toString()
public static void main(String[] args){
int []arr1 = {10,50,40,30,89,67,4,678};
Arrays.sort(arr1);
System.out.println( Arrays.toString(arr1));
}
将数组所有元素赋值为相同的值fill()
public static void main(String[] args){
int []arr1 = {10,50,40,30,89,67,4,678};
Arrays.fill(arr1,30);
System.out.println( Arrays.toString(arr1));
}
将数组赋值成一个长度为设定值的新数组copyof()
public static void main(String[] args){
int []arr1 = new int[] {10,50,40,30 };
//将arr1复制成长度为3的新数组arr2
int []arr2 = Arrays.copyOf(arr1,3);
System.out.println(Arrays.toString(arr2));
}
查询元素在数组中的下标binarySearch()
public static void main(String[] args){
int []arr = new int[] {10,50,40,30 };
Arrays.sort(arr);//排序后 10 30 40 50 90
int index = Arrays.binarySearch(arr, 10);
System.out.println(index);
index = Arrays.binarySearch(arr, 0);
System.out.println(index);
index = Arrays.binarySearch(arr, 45);
System.out.println(index);
index = Arrays.binarySearch(arr, 90);
System.out.println(index);
}
规则：
- 若找到了数据，则返回该数据的下标
- 若找不到数据，则返回负数，其值为该数据在数组中排序的位置
二维数组
在 Java 中二维数组被看作数组的数组，即二维数组为一个特殊的一维数组，其每个元素又是一个一维数组。Java 并不直接支持二维数组，但是允许定义数组元素是一维数组的一维数组，以达到同样的效果。
二维数组数据结构
简单说在Java中二维数组数据结构就是在数组的基础上进行扩展，将数组元素定义为一维数组。
使用二维数组
步骤与一维数组一致1. 定义数组2. 为数组元素分配内存3. 为数组元素初始化4. 使用数组。
总结
1.数组是可以在内存中连续存储多个同类型的引用型数据。
2.数组通过数组下标访问数组元素，下标从0到数组长度-1。
3.Arrays类是Java数组常用工具类，提供了包括但不限于排序、查找等操作。
4.二维数组实际上是一个一维数组，每个元素都为一维数组的一维数组。
